Least-loaded routing

Why does routing to the least-loaded server oscillate, and how do two random choices fix it?

This is the purest example of gain with delay. A client that routes each request to the currently least-loaded server acts on a load number that is stale by the propagation delay d. All N clients read the same stale number in the same window, make the same decision, and herd onto the one empty server. It overloads before the number updates. Then they all move together to the next server. The oscillation period is about 2d, and total capacity use is poor, even though every single routing decision was optimal given its information.

Power of two choices

Power of two choices solves it: pick two servers at random and send the request to the less loaded of the two. The load imbalance improves from O(log N / log log N) to O(log log N): an exponential improvement. (These are growth rates: for 1,000,000 servers, log N / log log N is about 5 to 6, while log log N is about 3. The gap widens as N grows.) There is no global decision point and, importantly, no synchronization, because each client's random sample is independent.

This is the principle that randomization can replace coordination, and it is the clearest case yet. The randomness is not there to improve the estimate. It is there to destroy the correlation between clients. The cost: you never reach true least-loaded placement, which you could not have had anyway with stale data.

import random
def pick_server(servers, load):
    a, b = random.sample(servers, 2)
    return a if load[a] <= load[b] else b