Book contents
- Frontmatter
- Contents
- Preface
- 1 Events and Probability
- 2 Discrete Random Variables and Expectation
- 3 Moments and Deviations
- 4 Chernoff Bounds
- 5 Balls, Bins, and Random Graphs
- 6 The Probabilistic Method
- 7 Markov Chains and Random Walks
- 8 Continuous Distributions and the Poisson Process
- 9 Entropy, Randomness, and Information
- 10 The Monte Carlo Method
- 11 Coupling of Markov Chains
- 12 Martingales
- 13 Pairwise Independence and Universal Hash Functions
- 14 Balanced Allocations
- Further Reading
- Index
14 - Balanced Allocations
- Frontmatter
- Contents
- Preface
- 1 Events and Probability
- 2 Discrete Random Variables and Expectation
- 3 Moments and Deviations
- 4 Chernoff Bounds
- 5 Balls, Bins, and Random Graphs
- 6 The Probabilistic Method
- 7 Markov Chains and Random Walks
- 8 Continuous Distributions and the Poisson Process
- 9 Entropy, Randomness, and Information
- 10 The Monte Carlo Method
- 11 Coupling of Markov Chains
- 12 Martingales
- 13 Pairwise Independence and Universal Hash Functions
- 14 Balanced Allocations
- Further Reading
- Index
Summary
In this chapter we examine a simple yet powerful variant of the classic balls-and-bins paradigm, with applications to hashing and dynamic resource allocation.
The Power of Two Choices
Suppose that we sequentially place n balls into n bins by putting each ball into a bin chosen independently and uniformly at random. We studied this classic balls-and-bins problem in Chapter 5. There we showed that, at the end of the process, the most balls in any bin – the maximum load – is Θ(ln n/ln ln n) with high probability.
In a variant of the process, each ball comes with d possible destination bins, each chosen independently and uniformly at random, and is placed in the least full bin among the d possible locations at the time of the placement. The original balls-and-bins process corresponds to the case where d = 1. Surprisingly, even when d = 2, the behavior is completely different: when the process terminates, the maximum load is ln ln n/ln 2 + O(1) with high probability. Thus, an apparently minor change in the random allocation process results in an exponential decrease in the maximum load. We may then ask what happens if each ball has three choices; perhaps the resulting load is then O(ln ln ln n). We shall consider the general case of d choices per ball and show that, when d ≥ 2, with high probability the maximum load is ln ln n/ln d + Θ(1).
- Type
- Chapter
- Information
- Probability and ComputingRandomized Algorithms and Probabilistic Analysis, pp. 336 - 348Publisher: Cambridge University PressPrint publication year: 2005