The Power of Two Choices in Randomized Load Balancing

By Michael M. Mitzenmacher. 2001

1,518 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Management Information Systems

How researchers see this paper

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

In Computer Networks and Communications

In Management Information Systems

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, methodology): “In multi-choice hashing [9, 61], the item is placed in the bucket least full among d candidate buckets.”
Clipper: A Low-Latency Online Prediction Serving System (2016, background): “e additional hardware accelerators. If a model container has more than one replica associated with it, requests are randomly load balanced across all replicas using the power of two choices algorithm [41]. Because different replicas can have different performance characteristics, particularly when s”
Interference alignment and cancellation (2009, positive): “To reduce computational overhead, it picks other clients in the group using the best of two choices, a standard approach for reducing the complexity of combinatorial problems [ 23 ].”
Horton Tables: Fast Hash Tables for In-Memory Data-Intensive Computing (2016, background): “In practice, f = 2 is used most often because it permits sufficient flexibility in where keys are mapped without suffering from having to search too many buckets [20, 54, 63].”
On the maximum queue length in the supermarket model (2006, neutral): “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”
Scalable Private Set Intersection Based on OT Extension (2018, background): “Estimating maxb has been subject to extensive research [28, 62, 48].”
Incentives and redistribution in homogeneous bike-sharing systems with stations of finite capacity (2012, result): “This result is similar to the well-known power of two choices that has been proved to be a very efficient load balancing strategy, see [19].”
Sparrow: distributed, low latency scheduling (2013, methodology): “Sparrow’s design takes inspiration from the power of two choices load balancing technique [14], which provides low expected task wait times using a stateless, randomized approach.”
Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services (2011, neutral): “The randomized load balancing algorithm, SQ(d) , has been studied theoretically in [16, 10, 3, 7, 9].”
Balanced Allocations (1999, background): “The question they analyze is, what is the expected maximum load under a random order of insertion under the greedy strategy? More recent results, based on the balanced allocation paradigm, have appeared in [23, 24, 25, 12].”
DRILL: Micro Load Balancing for Low-latency Data Center Networks (2017, methodology): “DRILL’s queueing algorithm is inspired by “power of two choices” load balancing [53].”
Efficient erasure correcting codes (2001, background): “This induced a random bipartite graph on(perhaps with multiedges) in the obvious manner with the desired degree structure.”
Rethinking virtual network embedding: substrate support for path splitting and migration (2008, background): “In fact, even having just two paths can significantly reduce the maximum load on a network, compared to solutions that limit the traffic flow to a single path [24, 19].”
Control Techniques for Complex Networks: Workload (2007, background): “Mitzenmacher, The power of two choices in randomized load balancing [373] (see also [ 374, 31].”