The power of two choices in randomized load balancing

We consider the following natural model: Customers arrive as a Poisson stream of rate gimeln, gimel < 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 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 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.