The power of two random choices: a survey of tech-niques and results

By Michael M. Mitzenmacher, A. Richa, Ramesh K. Sitaraman. 2001

481 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/359766cb47572028eb70c797115e987ff203e83f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Industrial and Manufacturing Engineering

Citations in the corpus

The (1 + β)-choice process and weighted balls-into-bins (2010, background): “There are many variants and applications of this result, see for instance the survey [5] and the references therein.”
The Power of Two Choices in Randomized Load Balancing (2001, result): “As a starting point, we suggest the recent survey [ 28 ].”
Virtual Network Embedding with Coordinated Node and Link Mapping (2009, background): “In addition to that, for networks with large numbers of nodes randomization has been shown to be effective for load balancing [20].”
Sparrow: distributed, low latency scheduling (2013, methodology): “In the theory literature, a substantial body of work analyzes the performance of the power of two choices load balancing technique, as summarized by Mitzenmacher [15].”
Hopper: Decentralized Speculation-aware Cluster Scheduling at Scale (2015, methodology): “While the power-of-two choices [38] and Sparrow [36] recommend a probe ratio of 2, we adopt a probe ratio of 4 based on our analysis in §5.”
Balls into Bins Made Faster (2013, background): “More results and techniques in multiple-choice allocation schemes can be found in [12].”
Path Selection and Multipath Congestion Control (2007, methodology): “In words, the worst case allocation in this scenario decreases like log(log(N ))/ log(N ). This is to be compared with the worst case allocation that one gets if b =1 , that is if a single path is used: from classical balls and bins models [ 15 ], this also decreases in log(log(N ))/ log(N ) as N in”
ViNEYard: Virtual Network Embedding Algorithms With Coordinated Node and Link Mapping (2012, background): “Additionally, for networks with large numbers of nodes, randomization has been shown to be effective for load balancing [22].”
Caching performance of content centric networks under multi-path routing (and more) (2011, methodology): “This policy leverages on the “power of two” principle [35], which was already used in the context of Web caching [19].”
Design and Implementation of a Consolidated Middlebox Architecture (2012, background): “We conjecture that this is akin to the “power of two random choices” observation [29] and plan to explore this in future work.”
The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation (2007, methodology): “Refer to [ 16 ] for a survey of further results on multiple choice allocation.”
Cuckoo Filter: Practically Better Than Bloom (2014, background): “Unfortunately, such an imbalanced assignment happens across blocks even when strong hash functions are used [18], which increases the overall false positive rate.”
On the maximum queue length in the supermarket model (2006, unknown): “ar X iv :m at h/ 06 05 63 9v 1 [ m at h. PR ] 2 4 M ay 2 00 6 The Annals of Probability 2006, Vol. 34, No. 2, 493–527 DOI: 10.1214/00911790500000710 c© Institute of Mathematical Statistics, 2006”