Statements (30)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
gptkb:algorithm
|
| gptkbp:appliesTo |
distributed systems
caching parallel computing task scheduling hash tables server selection |
| gptkbp:citation |
Michael Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, IEEE Transactions on Parallel and Distributed Systems, 2001
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal, Balanced Allocations, SIAM Journal on Computing, 1999 |
| gptkbp:describes |
balls-into-bins process
|
| gptkbp:field |
computer science
load balancing |
| https://www.w3.org/2000/01/rdf-schema#label |
Power of Two Choices
|
| gptkbp:improves_over |
random allocation
|
| gptkbp:introduced |
gptkb:Michael_Mitzenmacher
1996 Bruce M. Maggs Ramesh K. Sitaraman William F. Sudderth |
| gptkbp:main_idea |
assign each ball to the less loaded of two randomly chosen bins
|
| gptkbp:publishedIn |
Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS 1996)
|
| gptkbp:reduces |
maximum load
|
| gptkbp:relatedConcept |
randomized algorithm
hashing load balancing algorithm maximum load |
| gptkbp:typical_result |
maximum load is log log n / log d for d choices
maximum load is log log n for two choices |
| gptkbp:bfsParent |
gptkb:Online_Load_Balancing
|
| gptkbp:bfsLayer |
7
|