Andrea Marin

We study the Multiserver-Job Queuing Model (MJQM) with general independent arrivals and service times under FCFS scheduling, using stochastic recurrence equations (SREs) and ergodic theory. We prove the monotonicity and separability properties of the MJQM SRE, enabling the application of the monotone-separable extension of Loynes' theorem and the formal definition of the MJQM stability condition. Based on these results, we introduce and implement two algorithms: one for drawing sub-perfect samples (SPS) of the system's workload and the second one to estimate the system's stability condition given the statistics of the jobs' input stream. The SPS algorithm allows for a massive GPU parallelization, greatly improving the efficiency of performance metrics evaluation. We also show that this approach extends to more complex systems, including MJQMs with typed resources.

Cloud computing data centers handle highly variable workloads: job resource requirements can range from just one or few cores to thousands, and job service times can range from milliseconds to hours or days. This variability significantly limits the maximum achievable utilization of infrastructures. Queuing theory has addressed the study of these systems with the definition of the Multiserver-Job Queuing Model (MJQM), where s identical servers are present and job n requires α _n of the s servers for a random amount of time σ _n . The α _n servers are occupied and released simultaneously. Unfortunately, despite its simple formulation, the MJQM remains elusive. For example, the MJQM stability condition has been derived only in particular cases. As a consequence, even applying Discrete-Event Simulation (DES) under high load becomes challenging, because stability cannot be determined a priori. In this paper, we analyze the MJQM with general independent arrival processes and service times under FCFS scheduling, using stochastic recurrence equations (SREs) and ergodic theory. Starting from the definition of the MJQM SRE, we prove the monotonicity and separability properties that allow us to apply an extension of Loynes' theorem, known as the monotone-separable framework, and formally define the MJQM stability condition. From these results, we introduce and implement two algorithms: the first one is used to draw sub-perfect samples (SPS) of the system's workload and the second one estimates the system's stability condition given the statistics of the jobs' input stream. The nature of the SPS algorithm allows for a massive GPU parallelization, thus greatly improving the efficiency in the estimation of performance metrics. The algorithm for the estimation of the stability condition solves an important problem for the analysis of MJQMs. We also define new metrics that capture the synchronization loss in MJQM systems and we show how these metrics can be efficiently evaluated using the SRE approach. Finally, we show that the approach proposed in this paper can be extended to more complicated systems, including MJQMs where resources have types.

The efficient execution of data center jobs that require simultaneous use of different resource types is of critical importance. When processing capacity is the crucial resource for jobs execution, the locution multiserver jobs is used, where the term server indicates processors or CPU cores providing processing capacity. Each multiserver job carries a requirement expressed in number of servers it requires to run, and service duration. Achieving efficient execution of multiserver jobs relies heavily on effective scheduling of jobs on the existing servers. Several schedulers have been proposed, aimed at improving resource utilization, at the cost of increased complexity. Due to the limited availability of theoretical results on scheduler behavior in the case of multiserver jobs, data center schedulers are often designed based only on managers’ experience. In this article, aiming to expand the understanding of the multiserver job schedulers’ performance, we study Small Shuffle (SMASH) schedulers, a class of nonpreemptive, service time oblivious, window-based multiserver job scheduling algorithms that strike a balance between simplicity and efficient resource utilization, while allowing performance evaluation in simpler settings. SMASH implies only a marginal increase in complexity compared to FIFO, yet it delivers substantial performance improvements for multiserver jobs. Depending on the system parameters, SMASH can nearly double the system’s stability region with respect to FIFO, leading to significantly lower response times across a broad region of loads. Moreover, the magnitude of this improvement scales with the chosen window size, allowing performance to be tuned to the system’s operating conditions. We first study the capacity of SMASH with analytical tools in simple settings, then we investigate the performance of SMASH and other schedulers with simulations under more realistic workloads, designed with parameters derived from measurements of real data centers. Results show that SMASH offers a very good compromise between performance and complexity.

In this paper, we present the first remote timing attack based on formal stochastic models. Our attack uses queuing models from the field of performance evaluation to estimate the service times of different classes of network requests. By using Bayesian statistics, we then identify opportunities for remote timing attacks by answering the following inverse question: what is the probability that a given network request belongs to a target class, given an estimate of its service time? Our experimental evaluation on popular web applications and websites shows that our investigation is not just a theoretical exercise, because our attack outperforms existing empirical approaches in terms of standard performance figures. We believe that the formal foundations put forward in this paper can be successfully applied to the creation of principled remote timing attacks which are more effective, because better equipped to deal with the complexity of the problem they are trying to solve.

A blockchain is an immutable ledger driven by a distributed consensus protocol. In public blockchains, such as Bitcoin and Ethereum Classic, consensus is established through a computational effort called Proof-of-Work (PoW). Special users called miners contribute to the PoW in exchange for a fee and also verify the data stored in blocks mined by the other miners. Here is where the Verifier’s Dilemma emerges. Verification of blocks does not receive a reward, and to maximise their profits, miners may be incentivised to forego verifying blocks and to only invest their resources in PoW. In this article, we study the Verifier’s Dilemma and a possible countermeasure consisting of the injection of invalid blocks using a quantitative model based on Markovian process algebra. To avoid the state space explosion problem, we study the underlying Markov chain by using a lumping that allows us to derive closed-form solutions for interesting performance indices. The analysis demonstrates the circumstances under which non-verifying miners gain fees higher than those of verifying miners. The model also allows us to derive the optimal rate at which invalid blocks must be injected so that skipping the verifying phase becomes economically disadvantageous whereas the throughput of the blockchain is only minimally reduced. The impact on miners’ rewards and overall performance is also assessed.

In this paper, we report on the application of resiliency enforcement strategies that were applied to a microservices system running on a real-world deployment of a large cluster of heterogeneous Virtual Machines (VMs). We present the evaluation results obtained from measurement and modeling implementations. The measurement infrastructure was composed of 15 large and 15 extra-large VMs. The modeling approach used Markov Decision Processes (MDP). On the measurement testbed, we implemented three different levels of software rejuvenation granularity to achieve software resiliency. We have discovered two threats to resiliency in this environment. The first threat to resiliency was a memory leak that was part of the underlying open-source infrastructure in each VM. The second threat to resiliency was the result of the contention for resources in the physical host, which is dependent on the number and size of VMs deployed to the physical host. In the MDP modeling approach, we evaluated four strategies for assigning tasks to VMs with different configurations and different levels of parallelism. Using the large cluster under study, we compared our approach of using software aging and rejuvenation with the state-of-the-art approach of using a network of VMs deployed to a private cloud without software aging detection and rejuvenation. In summary, we show that in a private cloud with non-elastic resource allocation in the physical hosts, careful performance engineering needs to be performed to optimize the trade-offs between the number of VMs allocated and the total memory allocated to each VM.