Perfectly Fair Sharing Is Slow, Near-Fair Runs in Seconds

Imagine a few hundred cell towers, servers, or smart devices that each need to pick a channel, a time slot, or a task — and no two neighbors can pick the same one. That's called "coloring," a classic math problem. A fairer version also asks that every option gets used about equally often, so no single channel or server gets slammed while others sit idle. The new paper asks a practical question: how much do these machines need to talk to each other to pull that off?

The bad news is that perfect fairness is a group project. The authors proved that on the simplest possible network — a ring of machines strung together in a circle — dividing things exactly evenly takes roughly as many rounds of chatter as there are machines. In other words, information basically has to travel the whole network before anyone can finish. Let a little imbalance in (call it g) and the cost drops proportionally, but never disappears.

The good news is that "almost fair" is a local job. On rings, keeping the groups within a constant factor of equal takes only a handful of rounds — a number so small it barely grows even for absurdly large networks. On general networks, the authors show you can keep every group within a tiny percentage of the average in time that doesn't depend on how wide the network is at all. One version finishes in about (log n)(log log n)² rounds using just a slightly bigger menu of options.

The takeaway for anyone running infrastructure: stop demanding perfection. Insisting on exactly equal load balancing forces signals to crawl across your whole data center or cell network. Accepting a small tolerance — say, every server within a few percent of average — buys you a massive speedup and lets machines solve the problem by talking only to their immediate neighbors. That's a design rule worth remembering.