Load Balancing and Density Dependent Jump Markov Processes (Extended Abstract)

Michael Mitzenmacher Department of Computer Science U.C. Berkeley Berkeley, CA 94720 mitzen@cs.berkeley.edu Abstract We provide a new approach for analyzing both static and dynamic randomized load balancing strategies. We demonstrate the approach by providing the first analysis of the following model: customers arrive as a Poisson stream of rate n, ! 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 the expected time a customer spends in the system in equilibrium. The model provides a good abstraction of a simple, efficient load balancing scheme in the setting where jobs..