The power of two choices in randomized load balancing

We consider the following natural model: Customers arrive as a Poisson stre am of rate gimeln, gimel < 1, at a collection of n servers. Each customer c hooses some constant d servers independently and uniformly at random from t he n servers and waits for service at the one with the fewest customers. Cu stomers are served according to the first-in first-out (FIFO) protocol and the service time for a customer is exponentially distributed with mean 1. W e call this problem the supermarket model. We wish to know how the system b ehaves and in particular we are interested in the effect that the parameter d has on expected time a customer spends in the system in equilibrium. Our approach uses a limiting, deterministic model representing the behavior as n --> infinity to approximate the behavior of finite systems. The analysis of the deterministic model is interesting in its own right. Along with a t heoretical justification of this approach, we provide simulations that demo nstrate that the method accurately predicts system behavior, even for relat ively small systems. Our analysis provides surprising implications: Having d = 2 choices leads to exponential improvements in the expected time a cust omer 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 f or system design.