text: In large storage systems, files are often coded across several servers to improve reliability and retrieval speed. We consider a system of @math servers storing files using a Maximum Distance Separable code (cf. li2016mean ). Specifically, each file is stored in equally sized pieces across @math servers such that any @math pieces can reconstruct the original file. File requests are routed using the Batch Sampling routing scheme. I.e. when a request for a file is received, a centralized dispatcher routes the job into the @math -shortest queues among the @math for which the corresponding server contains a piece of the file being requested. We study the long time behavior of this class of load balancing mechanisms. In particular, it is shown that the ODE system that describes the mean field limit of the occupancy measure process has a unique fixed point which is stable. This fixed point corresponds to a distribution on @math of queue lengths with tails that decay super-exponentially. Upper and lower bounds on the decay rate are provided. Finally, we show that the unique invariant measure of the Markov occupancy measure process converges to the Dirac measure concentrated at the unique fixed point of the ODE system, establishing the interchangeability of the @math and @math limits.
  @cite_4: We consider a system of @math servers inter-connected by some underlying graph topology @math . Tasks arrive at the various servers as independent Poisson processes of rate @math . Each incoming task is irrevocably assigned to whichever server has the smallest number of tasks among the one where it appears and its neighbors in @math . Tasks have unit-mean exponential service times and leave the system upon service completion. The above model has been extensively investigated in the case @math is a clique. Since the servers are exchangeable in that case, the queue length process is quite tractable, and it has been proved that for any @math , the fraction of servers with two or more tasks vanishes in the limit as @math . For an arbitrary graph @math , the lack of exchangeability severely complicates the analysis, and the queue length process tends to be worse than for a clique. Accordingly, a graph @math is said to be @math -optimal or @math -optimal when the occupancy process on @math is equivalent to that on a clique on an @math -scale or @math -scale, respectively. We prove that if @math is an Erd o s-R 'enyi random graph with average degree @math , then it is with high probability @math -optimal and @math -optimal if @math and @math as @math , respectively. This demonstrates that optimality can be maintained at @math -scale and @math -scale while reducing the number of connections by nearly a factor @math and @math compared to a clique, provided the topology is suitably random. It is further shown that if @math contains @math bounded-degree nodes, then it cannot be @math -optimal. In addition, we establish that an arbitrary graph @math is @math -optimal when its minimum degree is @math , and may not be @math -optimal even when its minimum degree is @math for any @math .
  @cite_7: The model is motivated by the problem of load distribution in large-scale cloud-based data processing systems. We consider a heterogeneous service system, consisting of multiple large server pools. The pools are different in that their servers may have different processing speeds and or different buffer sizes (which may be finite or infinite). We study an asymptotic regime in which the customer arrival rate and pool sizes scale to infinity simultaneously, in proportion to some scaling parameter n. Arriving customers are assigned to the servers by a "router," according to a pull-based algorithm, called PULL. Under the algorithm, each server sends a "pull-message" to the router, when it becomes idle; the router assigns an arriving customer to a server according to a randomly chosen available pull-message, if there are any, or to a random server, otherwise. Assuming subcritical system load, we prove asymptotic optimality of PULL. Namely, as system scale @math n??, the steady-state probability of an arriving customer experiencing blocking or waiting, vanishes. We also describe some generalizations of the model and PULL algorithm, for which the asymptotic optimality still holds.
  @cite_8: We consider the following natural model: customers arrive as a Poisson stream of rate spl lambda n, spl lambda <1, at a collection of n servers. Each customer chooses some constant d servers independently and uniformly at random from the n servers and waits for service at the one with the fewest customers. Customers are served according to the first-in first-out (FIFO) protocol and the service time for a customer is exponentially distributed with mean 1. We call this problem the supermarket model. We wish to know how the system behaves and in particular we are interested in the effect that the parameter d has on the expected time a customer spends in the system in equilibrium. Our approach uses a limiting, deterministic model representing the behavior as n spl rarr spl infin to approximate the behavior of finite systems. The analysis of the deterministic model is interesting in its own right. Along with a theoretical justification of this approach, we provide simulations that demonstrate that the method accurately predicts system behavior, even for relatively small systems. Our analysis provides surprising implications. Having d=2 choices leads to exponential improvements in the expected time a customer spends in the system over d=1, whereas having d=3 choices is only a constant factor better than d=2. We discuss the possible implications for system design.
  @cite_10: We consider a system of @math identical server pools and a single dispatcher where tasks arrive as a Poisson process of rate @math . Arriving tasks cannot be queued, and must immediately be assigned to one of the server pools to start execution, or discarded. The execution times are assumed to be exponentially distributed with unit mean, and do not depend on the number of other tasks receiving service. However, the experienced performance (e.g. in terms of received throughput) does degrade with an increasing number of concurrent tasks at the same server pool. The dispatcher therefore aims to evenly distribute the tasks across the various server pools. Specifically, when a task arrives, the dispatcher assigns it to the server pool with the minimum number of tasks among @math randomly selected server pools. This assignment strategy is called the JSQ @math scheme, as it resembles the power-of- @math version of the Join-the-Shortest-Queue (JSQ) policy, and will also be referred to as such in the special case @math . We construct a stochastic coupling to bound the difference in the system occupancy processes between the JSQ policy and a scheme with an arbitrary value of @math . We use the coupling to derive the fluid limit in case @math and @math as @math , along with the associated fixed point. The fluid limit turns out to be insensitive to the exact growth rate of @math , and coincides with that for the JSQ policy. We further leverage the coupling to establish that the diffusion limit corresponds to that for the JSQ policy as well, as long as @math , and characterize the common limiting diffusion process. These results indicate that the JSQ optimality can be preserved at the fluid-level and diffusion-level while reducing the overhead by nearly a factor O( @math ) and O( @math ), respectively.
  @cite_9: 
  @cite_6: 
  @cite_3: 
  @cite_2: 
  @cite_5: 
  @cite_13: Randomized load balancing greatly improves the sharing of resources while being simple to implement. In one such model, jobs arrive according to a rate-?N Poisson process, with ?<1, in a system of N rate-1 exponential server queues. In (Probl. Inf. Transm. 32:15---29, 1996), it was shown that when each arriving job is assigned to the shortest of D, D?2, randomly chosen queues, the equilibrium queue sizes decay doubly exponentially in the limit as N??. This is a substantial improvement over the case D=1, where queue sizes decay exponentially. The reasoning in (Probl. Inf. Transm. 32:15---29, 1996) does not easily generalize to jobs with nonexponential service time distributions. A modularized program for treating randomized load balancing problems with general service time distributions was introduced in (Proc. ACM SIGMETRICS, pp. 275---286, 2010). The program relies on an ansatz that asserts that, for a randomized load balancing scheme in equilibrium, any fixed number of queues become independent of one another as N??. This allows computation of queue size distributions and other performance measures of interest. In this article, we demonstrate the ansatz in several settings. We consider the least loaded balancing problem, where an arriving job is assigned to the queue with the smallest workload. We also consider the more difficult problem, where an arriving job is assigned to the queue with the fewest jobs, and demonstrate the ansatz when the service discipline is FIFO and the service time distribution has a decreasing hazard rate. Last, we show the ansatz always holds for a sufficiently small arrival rate, as long as the service distribution has 2 moments.
  @cite_12: 
summary: Load balancing mechanisms similar to the type considered here have been studied in many works. Specifically, the Join-the-Shortest-Queue (JSQ), Join-the-Idle-Queue (JIQ), and Power-of- @math (also known as the supermarket model) routing schemes have garnered quite a bit of attention (see @cite_6 @cite_5 @cite_4 @cite_8 @cite_13 @cite_7 @cite_12 @cite_10 @cite_9 and references therein). The papers @cite_6 @cite_2 were the first to study the tail behavior of the fixed point of the ODE system associated with the Power-of- @math routing scheme, showing that in steady-state the fraction of queues with lengths exceeding @math decay super-exponentially in @math , a large improvement over the exponential rate for the setting where jobs are routed to servers uniformly at random. Later works on a similar theme include @cite_4 @cite_3 @cite_9 . In all these works, the authors study fluid and diffusion approximations for various types of load balancing mechanisms. In each case, stable fixed points are identified for the LLN limit and the interchangeability of limit property is established.