Look at two queues, not one

A thousand jobs arrive at a thousand servers: checkouts, call handlers, computers. Send each job to a server at random and some servers get swamped while others sit idle. Let each job look at just two servers and take the quieter one, and the worst pile collapses.

The rules, all of them. Jobs arrive one at a time. Each looks at a set number of servers chosen at random and joins the one with the fewest jobs so far. With one choice it does not look at all. Jobs never leave or move. We look at the piles at the end.

With one random choice and as many jobs as servers, 37% of servers get nothing and the tallest pile grows with the size of the system. With two choices the share of servers holding three jobs or more falls from 8% to under 1%, and the tallest pile barely grows at all: with a million servers it is 4, against 8 or 9. A third or fourth choice adds almost nothing more. The shares are checked against exact results: Poisson counts for one choice and Michael Mitzenmacher's equations for two and three. This is how real computer systems share work: looking at every server would be best but slow, and looking at two gets nearly all of the gain. What it leaves out: jobs finishing, and jobs of different sizes.