power-of-two-choices · research · also Two-choice load balancing, P2C

Power of two choices

Power of two choices routes a job to the less-loaded of two randomly sampled eligible servers, using a specified load signal and tie rule.

Related Observatory article: Read on hesela.com

In the supermarket model, arrivals are Poisson with total rate lambda times n, each server has independent exponential service of mean one, queues are FIFO, and lambda is below one. Candidates are sampled uniformly with replacement and their current queue lengths are compared. At the limiting equilibrium as n tends to infinity, the fraction of queues containing at least i jobs is lambda^(2^i - 1); random one-choice routing gives lambda^i. This is a queue-occupancy tail, not the probability that a storage request misses a time deadline. [1]

Stale feedback changes the model. Mitzenmacher's periodic-update study finds regimes in which two choices outperform global shortest-queue selection, but sufficiently old information can make random assignment better. Its simulations and limiting models are not a measured storage fleet or a universal ranking of policies. [2]

Hesela's separate finite example assigns four jobs to three empty servers with no departures. All 6561 ordered two-choice sequences are counted. Updating counts after each assignment gives probability 49/729 that a server ends with at least three jobs. Freezing all reported counts at zero gives 1/3, exactly the one-choice distribution, when ties use the first sampled candidate. Choosing the lowest ID instead biases selection. This is an exact synthetic example, not a replication of either paper. [3]

Relations

related
Adaptive replica selection, Tail latency

Limitations

  • Replica eligibility and read consistency must be established before load-based routing; this policy does not certify freshness or durability. [3]
  • The finite example has no service times, departures or network delays and cannot estimate latency percentiles. [3]

Citations

  1. Mitzenmacher. The Power of Two Choices in Randomized Load Balancing. IEEE TPDS 12(10), 2001, pp. 1094-1104; sections 1 and 2.2-2.4. (accessed 2026-11-20)
  2. Mitzenmacher. How Useful Is Old Information? IEEE TPDS 11(1), 2000, pp. 6-20; sections 2 and 3.1-3.4. (accessed 2026-11-20)
  3. Hesela. Exact finite two-choice allocation: current counts, frozen feedback and tie-breaking control. (accessed 2026-11-20)
Sources & caveats
  • Primary-source synthesis separates a limiting queueing result from a finite synthetic allocation example.
  • The exact example includes independent path enumeration and a multinomial check; no hardware experiment, original theorem or field-speedup claim.

JSON: /data/terms/power-of-two-choices.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Power of two choices. Hesela. 2026-11-20. https://hesela.dev/terms/power-of-two-choices/