3 ms·
The method is called "Power of Two Random Choices" (http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf http://www.eecs.harvard.edu/~michaelm/pos
by alxv 9y ago
The method is called "Power of Two Random Choices" (http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20...). And the two-choices paradigm is widely applicable beyond load balancing. In particular, it applies to hash table design (e.g. cuckoo hashing) and cache eviction schemes (https://danluu.com/2choices-eviction/ https://danluu.com/2choices-eviction/).
- mrkurt 9y agoYou're right, I updated the title. Got a little too clever with the whole "power" thing.
- adrianN 9y agoIt also works for solving SAT. Try two literals and recurse on the one that can be made to satisfy more clauses.
- naiveattack 9y ago"while each additional choice beyond two decreases the maximum load by only a constant factor" Mathemagical!