The Power of Two Random Choices (Mitzenmacher, 2001)

[benclmnt]

SaveTwitter.Net_1754911236704370688.720p.mp4

On the left, nodes are chosen and used at random. On the right, 2 nodes are chosen at random, but only the minimum is used. Source

For any $d >= 2$, choosing $d$ nodes chosen at random + choosing the node with the lesser workload, the longest workload bound is $\Theta(\log\log N / \log d) + \Theta(1)$ with high probability. This is an improvement in upper bound from only choosing a node at random, which has an upper bound of $\Theta(\log N/ \log \log N)$ .

• To give an example with concrete numbers, if $N = 2^{16}$ then $\Theta(\log N/ \log \log N)$ is $2^{14}$ while $\Theta(\log \log N)$ is 4 (an order of magnitude smaller)
• Why 2 is enough? Any $d > 2$ only yields constant improvement

Another application of this technique is in hashmap implementation and task scheduling.

Reference:

• https://www.eecs.harvard.edu/%7Emichaelm/postscripts/handbook2001.pdf
• https://twitter.github.io/finagle/guide/Clients.html#power-of-two-choices-p2c-least-loaded