The power of two choices in randomized load balancing
Top Cited Papers
- 1 October 2001
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 12 (10), 1094-1104
- https://doi.org/10.1109/71.963420
Abstract
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.Keywords
This publication has 29 references indexed in Scilit:
- Asymptotic analysis of an assignment problem arising in a distributed communications protocolPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Differential Equations for Random Processes and Random GraphsThe Annals of Applied Probability, 1995
- Parallel randomized load balancingPublished by Association for Computing Machinery (ACM) ,1995
- Efficient PRAM simulation on a distributed memory machinePublished by Association for Computing Machinery (ACM) ,1992
- A trace-driven simulation study of dynamic load balancingIEEE Transactions on Software Engineering, 1988
- Maximum matching in sparse random graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- On the optimal assignment of customers to parallel serversJournal of Applied Probability, 1978
- Optimality of the shortest line disciplineJournal of Applied Probability, 1977
- Limit theorems for sequences of jump Markov processes approximating ordinary differential processesJournal of Applied Probability, 1971
- Solutions of ordinary differential equations as limits of pure jump markov processesJournal of Applied Probability, 1970