A large proportion of jobs submitted to modern computing clusters and data centers are parallelizable and capable of running on a flexible number of computing cores or servers. Although allocating more servers to such a job results in a higher speed-up in the job’s execution, it reduces the number of servers available to other jobs, which in the worst case, can result in an incoming job not finding any available server to run immediately upon arrival. Hence, a key question to address is: how to optimally allocate servers to jobs such that (i) the average execution time across jobs is minimized and (ii) almost all jobs find at least one server immediately upon arrival. To address this question, we consider a system withnservers, where jobs are parallelizable up to$d^{(n)}$servers and the speed-up function of jobs is concave and increasing. Jobs not finding any available servers upon entry are blocked and lost. We propose a simple server allocation scheme that achieves the minimum average execution time of accepted jobs while ensuring that the blocking probability of jobs vanishes as the system becomes large ($n \to \infty $). This result is established for various traffic conditions as well as for heterogeneous workloads. To prove our result, we employ Stein’s method which also yields non-asymptotic bounds on the blocking probability and the mean execution time. Furthermore, our simulations show that the performance of the scheme is insensitive to the distribution of job execution times.

A large proportion of jobs submitted to modern computing clusters and data centers are parallelizable and capable of running on a flexible number of computing cores or servers. Although allocating more servers to such a job results in a higher speed-up in the job's execution, it reduces the number of servers available to other jobs, which in the worst case, can result in an incoming job not finding any available server to run immediately upon arrival. Hence, a key question to address is: how to optimally allocate servers to jobs such that (i) the average execution time across jobs is minimized and (ii) almost all jobs find at least one server immediately upon arrival. To address this question, we consider a system with n servers, where jobs are parallelizable up to d(n) servers and the speed-up function of jobs is concave and increasing. Jobs not finding any available servers upon entry are blocked and lost. We propose a simple server allocation scheme that achieves the minimum average execution time of accepted jobs while ensuring that the blocking probability of jobs vanishes as the system becomes large (n → ∞). This result is established for various traffic conditions as well as for heterogeneous workloads. To prove our result, we employ Stein's method which also yields non-asymptotic bounds on the blocking probability and the mean execution time. Furthermore, our simulations show that the performance of the scheme is insensitive to the distribution of job execution times.

We consider a system with n unit-rate servers where jobs arrive according a Poisson process with rate nλ (λ<1). In the standard Power-of-d or Pod scheme with d≥2, for each incoming job, a dispatcher samples d servers uniformly at random and sends the incoming job to the least loaded of the d sampled servers. However, in practice, load comparisons may not always be accurate. In this paper, we analyze the effects of noisy load comparisons on the performance of the Pod scheme. To test the robustness of the Pod scheme against load comparison errors, we assume an adversarial setting where, in the event of an error, the adversary assigns the incoming job to the worst possible server, i.e., the server with the maximum load among the d sampled servers. We consider two error models: load-dependent and load-independent errors. In the load-dependent error model, the adversary has limited power in that it is able to cause an error with probability ϵ∈[0,1] only when the difference in the minimum and the maximum queue lengths of the d sampled servers is bounded by a constant threshold g≥0. For this type of errors, we show that, in the large system limit, the benefits of the Pod scheme are retained even if g and ϵ are arbitrarily large as long as the system is heavily loaded, i.e., λ is close to 1. In the load-independent error model, the adversary is assumed to be more powerful in that it can cause an error with probability ϵ independent of the loads of the sampled servers. For this model, we show that the performance benefits of the Pod scheme are retained only if ϵ≤1/d; for ϵ>1/d we show that the stability region of the system reduces and the system performs poorly in comparison to the random scheme. Our mean-field analysis uses a new approach to characterise fixed points which neither have closed form solutions nor admit any recursion. Furthermore, we develop a generic approach to prove tightness and stability for any state-dependent load balancing scheme.

We consider a system with n unit-rate servers where jobs arrive according a Poisson process with rate nλ (λ < 1). In the standard Power-of-two or Po2 scheme, for each incoming job, a job dispatcher samples two servers uniformly at random and sends the incoming job to the least loaded of the two sampled servers. However, in practice, the load information may not be accurate at the job dispatcher. In this paper, we analyze the effects of erroneous load comparisons on the performance of the Po2 scheme. Specifically, we consider load-dependent and load-independent errors. In the load-dependent error model, an incoming job is sent to the server with the larger queue length among the two sampled servers with an error probability ε if the difference in the queue lengths of the two sampled servers is less than or equal to a constant g; no error is made if the queue-length difference is higher than g. For this type of errors, we show that, in the large system limit, the benefits of the Po2 scheme are retained for all values of g and ε as long as the system is heavily loaded, i.e., λ is close to 1. In the load-independent error model, the incoming job is sent to the sampled server with the maximum load with an error probability of ε independent of the loads of the sampled servers. For this model, we show that the performance benefits of the Po2 scheme are retained only if ε ≤ 1/2; for ε > 1/2 we show that the stability region of the system reduces and the system performs poorly in comparison to the random scheme. To prove our stability results, we develop a generic approach to bound the drifts of Lyapunov functions for any state-dependent load balancing scheme. Furthermore, the mean-field analysis in our paper uses a new approach to characterise fixed points which do not admit a recursion.

A fundamental problem in large-scale data centers is to reduce the average response time of jobs. The Join-the-Shortest-Queue (JSQ) load balancing scheme is known to minimise the average response time of jobs for homogeneous systems consisting of identical servers. However, heterogeneous systems consisting of servers with different speeds, JSQ performs poorly. Furthermore, JSQ suffers from high communication overhead as it requires knowledge of the queue length of all servers while assigning incoming jobs to one of the destination servers. Therefore, the Join-the-Idle-Queue (JIQ) scheme was introduced which not only reduces the communication overhead but also minimises the average response time of jobs under homogeneous systems. Despite these advantages, JIQ is still known to be inefficient in minimising the average response time of jobs under heterogeneous systems. In this paper, we consider a speed-aware version of JIQ for heterogeneous systems and show that it achieves delay optimality in the fluid limit. One of the technical challenges to establishing this optimality is to show the tightness of the sequence of steady-state distributions indexed by system size. We show this tightness result by evaluating the drift of appropriate Lyapunov functions. This approach to proving tightness is different from the usual coupling approach used for homogeneous systems. Another important challenge in proving the optimality result is to establish the fluid limit which is done using the time-scale separation technique. Finally, using the monotonicity of the fluid process we have shown that the fluid limit has a unique and globally attractive fixed point.

The Join-the-Shortest-Queue (JSQ) load-balancing scheme is known to minimise the average delay of jobs in homogeneous systems consisting of identical servers. However, it performs poorly in heterogeneous systems where servers have different processing rates. Finding a delay optimal scheme remains an open problem for heterogeneous systems. In this paper, we consider a speed-aware version of the JSQ scheme for heterogeneous systems and show that it achieves delay optimality in the fluid limit. One of the key issues in establishing this optimality result for heterogeneous systems is to show that the sequence of steady-state distributions indexed by the system size is tight in an appropriately defined space. The usual technique for showing tightness by coupling with a suitably defined dominant system does not work for heterogeneous systems. To prove tightness, we devise a new technique that uses the drift of exponential Lyapunov functions. Using the non-negativity of the drift, we show that the stationary queue length distribution has an exponentially decaying tail — a fact we use to prove tightness. Another technical difficulty arises due to the complexity of the underlying state-space and the separation of two time-scales in the fluid limit. Due to these factors, the fluid-limit turns out to be a function of the invariant distribution of a multi-dimensional Markov chain which is hard to characterise. By using some properties of this invariant distribution and using the monotonicity of the system, we show that the fluid limit is has a unique and globally attractive fixed point.

We analyse a data-processing system with n clients producing jobs which are processed in batches by m parallel servers; the system throughput critically depends on the batch size and a corresponding sub-additive speedup function. In practice, throughput optimization relies on numerical searches for the optimal batch size, a process that can take up to multiple days in existing commercial systems. In this paper, we model the system in terms of a closed queueing network; a standard Markovian analysis yields the optimal throughput in ωn4 time. Our main contribution is a mean-field model of the system for the regime where the system size is large. We show that the mean-field model has a unique, globally attractive stationary point which can be found in closed form and which characterizes the asymptotic throughput of the system as a function of the batch size. Using this expression we find the asymptotically optimal throughput in O(1) time. Numerical settings from a large commercial system reveal that this asymptotic optimum is accurate in practical finite regimes.

We consider a generic model of distributed caching systems, where the cache servers are constrained by two main resources: memory size and bandwidth. Content distribution networks (CDNs) providing video contents and peer-to-peer video-on-demand services are a few examples of such systems. The throughput of these systems crucially depends on how these resources are managed, i.e., how contents are replicated across servers and how requests of specific contents are matched to servers storing the contents. In this paper, we formulate the problem of computing the replication policy and the matching policy, which jointly maximizes the throughput of the caching system. It is shown that computing the optimal replication policy for a given finite system is an NP-hard problem. A greedy replication scheme is then proposed and is shown to achieve a constant factor approximation guarantee when combined with the optimal matching policy. We note that the optimal matching policy has the problem of interruption in service of the ongoing requests due to re-assignment or repacking of the existing requests. To avoid this problem, we propose a simple randomized online matching scheme and analyze its performance in conjunction with the proposed replication scheme. We consider a limiting regime, where the number of servers is large and the arrival rates of the contents are scaled proportionally, and show that the proposed policies achieve asymptotic optimality. Extensive simulation results are presented to evaluate the performance of different policies and study the behavior of the caching system under different service time distributions of the requests.

We consider models of content delivery networks in which the servers are constrained by two main resources: memory and bandwidth. In such systems, the throughput crucially depends on how contents are replicated across servers and how the requests of specific contents are matched to servers storing those contents. In this paper, we first formulate the problem of computing the optimal replication policy which if combined with the optimal matching policy maximizes the throughput of the caching system in the stationary regime. It is shown that computing the optimal replication policy for a given system is an NP-hard problem. A greedy replication scheme is proposed and it is shown that the scheme provides a constant factor approximation guarantee. We then propose a simple randomized matching scheme which avoids the problem of interruption in service of the ongoing requests due to re-assignment or repacking of the existing requests in the optimal matching policy. The dynamics of the caching system is analyzed under the combination of proposed replication and matching schemes. We study a limiting regime, where the number of servers and the arrival rates of the contents are scaled proportionally, and show that the proposed policies achieve asymptotic optimality. Extensive simulation results are presented to evaluate the performance of different policies and study the behavior of the caching system under different service time distributions of the requests.

In this paper, we investigate the impact of majority-rule based random interactions among agents in a large social network on the diffusion of opinions in the network. Opinion of each agent is assumed to be a binary variable taking values in the set {0, 1}. Interactions among agents are modeled using the majority rule, where each agent updates its opinion at random instants by adopting the 'majority' opinion among a group of randomly sampled agents. We investigate two scenarios that respectively incorporate `bias' of the agents towards a specific opinion and stubbornness of some of the agents in the majority rule dynamics. For the first scenario, where all the agents are assumed to be 'biased' towards one of the opinions, it is shown that the agents reach a consensus on the preferred opinion (with high probability) only if the initial fraction of agents having the preferred opinion is above a certain threshold. Furthermore, the mean time taken to reach the consensus is shown to be logarithmic in the network size. In the second scenario, where the presence of 'stubborn' agents, who never update their opinions, is assumed, we characterize the equilibrium distribution of opinions of the non-stubborn agents using mean field techniques. The mean field limit is shown to have multiple stable equilibrium points which leads to a phenomenon known as metastability.

We consider randomized job routing techniques for a system consisting of a large number of parallel processor sharing servers with heterogeneous server speeds. In particular, a scheme, that routes an incoming job request to the server providing the highest instantaneous processing rate per job among two servers, chosen uniformly at random, is proposed. We show that, unlike the homogeneous case, in the heterogeneous case, such randomized dynamic schemes need not always perform better than the optimal static scheme (in which jobs are assigned to servers with fixed probabilities independent of server states) in terms of reducing the mean response time of jobs. Specifically, we show that the stability region under the proposed scheme is a subset of that under the optimal static routing scheme. We also obtain the stationary tail distribution of server occupancies for the proposed scheme in the limit as the system size grows to infinity. This distribution has been shown to be insensitive to job length distribution and decay super-exponentially.

Multi-packet reception (MPR) promises significant throughput gains in wireless local area networks (WLANs) by allowing nodes to transmit even in the presence of ongoing transmissions in the medium. However, the medium access control (MAC) layer must now be redesigned to facilitate - rather than discourage - these overlapping transmissions. We investigate asynchronous MPR MAC protocols, which successfully accomplish this by controlling the node behavior based on the number of ongoing transmissions in the channel. The protocols use the backoff timer mechanism of the distributed coordination function, which makes them practically appealing. We first highlight a unique problem of acknowledgment delays, which arises in asynchronous MPR, and investigate a solution that modifies the medium access rules to reduce these delays and increase system throughput in the single receiver scenario. We develop a general renewal-theoretic fixed-point analysis that leads to expressions for the saturation throughput, packet dropping probability, and average head-of-line packet delay. We also model and analyze the practical scenario in which nodes may incorrectly estimate the number of ongoing transmissions.

Multi-packet reception (MPR), in which a receiver can decode multiple simultaneous transmissions, significantly improves the uplink throughput of wireless local area networks (WLANs). However, the medium access control (MAC) layer must be redesigned to encourage, and not avoid, simultaneous transmissions. Asynchronous MPR MAC protocols, in which nodes independently access the channel so long as the number of ongoing transmissions is less than a threshold, are promising solutions for enabling MPR in IEEE 802.11-based WLANs. In this paper, we highlight the problem of acknowledgment (ACK) delays that arises in asynchronous MPR when multiple nodes transmit in succession without the channel becoming idle. We propose a novel asynchronous MAC protocol that reduces the ACK delays, increases throughput, and retains the distributed nature of the 802.11 distributed coordination function (DCF). An accurate renewal theoretic fixed-point analysis that leads to general analytical expressions for the saturation throughput is also developed.

The theoretical analysis of evolutionary algorithms is believed to be very important for understanding their internal search mechanism and thus to develop more efficient algorithms. This paper presents a simple mathematical analysis of the explorative search behavior of a recently developed metaheuristic algorithm called harmony search (HS). HS is a derivative-free real parameter optimization algorithm, and it draws inspiration from the musical improvisation process of searching for a perfect state of harmony. This paper analyzes the evolution of the population-variance over successive generations in HS and thereby draws some important conclusions regarding the explorative power of HS. A simple but very useful modification to the classical HS has been proposed in light of the mathematical analysis undertaken here. A comparison with the most recently published variants of HS and four other state-of-the-art optimization algorithms over 15 unconstrained and five constrained benchmark functions reflects the efficiency of the modified HS in terms of final accuracy, convergence speed, and robustness.