Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content
Law

The power of two choices

A single random assignment concentrates badly; the minimum over two random assignments concentrates tightly.

Bins
servers, or bins, receiving n items

Recurring principle: Randomization replaces coordination

How it behaves

One input on the horizontal axis, the others held fixed.

one random choicebest of two
Data table
Fullest bin above the mean (leading terms), by servers
Servers nseriesExcess load (leading term)
10one random choice2.76
12.6one random choice2.73
15.8one random choice2.72
20one random choice2.73
25.1one random choice2.75
31.6one random choice2.79
39.8one random choice2.83
50.1one random choice2.87
63.1one random choice2.92
79.4one random choice2.96
100one random choice3.02
126one random choice3.07
158one random choice3.12
200one random choice3.18
251one random choice3.23
316one random choice3.29
398one random choice3.35
501one random choice3.4
631one random choice3.46
794one random choice3.52
1Kone random choice3.57
1.26Kone random choice3.63
1.58Kone random choice3.69
2Kone random choice3.75
2.51Kone random choice3.8
3.16Kone random choice3.86
3.98Kone random choice3.92
5.01Kone random choice3.98
6.31Kone random choice4.03
7.94Kone random choice4.09
10Kone random choice4.15
12.6Kone random choice4.21
15.8Kone random choice4.26
20Kone random choice4.32
25.1Kone random choice4.38
31.6Kone random choice4.43
39.8Kone random choice4.49
50.1Kone random choice4.54
63.1Kone random choice4.6
79.4Kone random choice4.66
100Kone random choice4.71
126Kone random choice4.77
158Kone random choice4.82
200Kone random choice4.88
251Kone random choice4.93
316Kone random choice4.99
398Kone random choice5.04
501Kone random choice5.1
631Kone random choice5.15
794Kone random choice5.21
1Mone random choice5.26
1.26Mone random choice5.32
1.58Mone random choice5.37
2Mone random choice5.42
2.51Mone random choice5.48
3.16Mone random choice5.53
3.98Mone random choice5.58
5.01Mone random choice5.64
6.31Mone random choice5.69
7.94Mone random choice5.74
10Mone random choice5.8
12.6Mone random choice5.85
15.8Mone random choice5.9
20Mone random choice5.96
25.1Mone random choice6.01
31.6Mone random choice6.06
39.8Mone random choice6.11
50.1Mone random choice6.17
63.1Mone random choice6.22
79.4Mone random choice6.27
100Mone random choice6.32
126Mone random choice6.37
158Mone random choice6.43
200Mone random choice6.48
251Mone random choice6.53
316Mone random choice6.58
398Mone random choice6.63
501Mone random choice6.68
631Mone random choice6.73
794Mone random choice6.79
1Bone random choice6.84
10best of two1.2
12.6best of two1.34
15.8best of two1.47
20best of two1.58
25.1best of two1.69
31.6best of two1.79
39.8best of two1.88
50.1best of two1.97
63.1best of two2.05
79.4best of two2.13
100best of two2.2
126best of two2.27
158best of two2.34
200best of two2.4
251best of two2.47
316best of two2.53
398best of two2.58
501best of two2.64
631best of two2.69
794best of two2.74
1Kbest of two2.79
1.26Kbest of two2.84
1.58Kbest of two2.88
2Kbest of two2.93
2.51Kbest of two2.97
3.16Kbest of two3.01
3.98Kbest of two3.05
5.01Kbest of two3.09
6.31Kbest of two3.13
7.94Kbest of two3.17
10Kbest of two3.2
12.6Kbest of two3.24
15.8Kbest of two3.27
20Kbest of two3.31
25.1Kbest of two3.34
31.6Kbest of two3.37
39.8Kbest of two3.4
50.1Kbest of two3.44
63.1Kbest of two3.47
79.4Kbest of two3.5
100Kbest of two3.53
126Kbest of two3.55
158Kbest of two3.58
200Kbest of two3.61
251Kbest of two3.64
316Kbest of two3.66
398Kbest of two3.69
501Kbest of two3.71
631Kbest of two3.74
794Kbest of two3.76
1Mbest of two3.79
1.26Mbest of two3.81
1.58Mbest of two3.84
2Mbest of two3.86
2.51Mbest of two3.88
3.16Mbest of two3.9
3.98Mbest of two3.93
5.01Mbest of two3.95
6.31Mbest of two3.97
7.94Mbest of two3.99
10Mbest of two4.01
12.6Mbest of two4.03
15.8Mbest of two4.05
20Mbest of two4.07
25.1Mbest of two4.09
31.6Mbest of two4.11
39.8Mbest of two4.13
50.1Mbest of two4.15
63.1Mbest of two4.17
79.4Mbest of two4.19
100Mbest of two4.2
126Mbest of two4.22
158Mbest of two4.24
200Mbest of two4.26
251Mbest of two4.27
316Mbest of two4.29
398Mbest of two4.31
501Mbest of two4.32
631Mbest of two4.34
794Mbest of two4.36
1Bbest of two4.37

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

The latency floor of consistency

Previous Page

What a fault costs

Next Page