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...
-----