TITLE: TIL Today: The Power of Limiting Random Choices AUTHOR: Eugene Wallingford DATE: November 03, 2016 3:53 PM DESC: ----- BODY: This morning I read this blog post by Dan Luu on the use of randomized algorithms in cache eviction. He mentions a paper by Mitzenmacher, Richa, and Sitaraman called The Power of Two Random Choices that explains a cool effect we see when we limit our options when choosing among multiple options. Luu summarizes the result:

The mathematical intuition is that if we (randomly) throw n balls into n bins, the maximum number of balls in any bin is O(log n / log log n) with high probability, which is pretty much just O(log n). But if (instead of choosing randomly) we choose the least loaded of k random bins, the maximum is O(log log n / log k) with high probability, i.e., even with two random choices, it's basically O(log log n) and each additional choice only reduces the load by a constant factor.

Luu used this result to create a cache eviction policy that outperforms random eviction across the board and competes closely with the traditional LRU policy. It chooses two pages at random and evicts the least-recently used of the two. This so-called 2-random algorithm slightly outperforms LRU in larger caches and slightly underperforms LRU in smaller caches. This trade-off may be worth making because, unlike LRU, random eviction policies degrade gracefully as loops get large. The power of two random choices has potential application in any context that fits the balls-and-bins model, including load balancing. Luu mentions less obvious application areas, too, such as circuit routing. Very cool indeed. I'll have to look at Mitzenmacher et al. to see how the math works, but first I may try the idea out in some programs. For me, the programming is even more fun... -----