More Web Proxy on the site http://driver.im/

Article

Balanced allocations with heterogenous bins

Author:

Udi WiederAuthors Info & Claims

SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures

Pages 188 - 193

https://doi.org/10.1145/1248377.1248407

Published: 09 June 2007 Publication History

Abstract

Balls-into-bins processes are a useful and common abstraction for many load-balancing related problems. A well known paradigm for load balancing in distributed or parallel servers is the "multiple choice paradigm" where an item (ball) is put in the less loaded out of d uniformly chosen servers (bins). In many applications however the uniformity of the sampling probability is not guaranteed. If the system is heterogenous or dynamic it may be the case that some bins are sampled with a higher probability than others. We investigate the power of the multiple choice paradigm in the setting where bins are not sampled from the uniform distribution. Byers et al [5] showed that a logarithmic imbalance in the sampling probability could be tolerated, as long as the number of balls is linear in the number of bins. We show that if the number of balls is much larger than the number of bins, this ceases to be the case. Given a probability over bins, we prove tight upper and lower bounds for the number of choices needed in the 1-out-of-d scheme in order to maintain a balanced allocations when the number of items is arbitrarily high.

References

[1]

Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, and Lars Rasmussen. Parallel randomized load balancing. In Proc. of Symp. on Theory of Computing (STOC), pages 238--247, 1995.

Digital Library

[2]

Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. SIAM Journal Computing, 29(1):180--200, 1999.

Digital Library

[3]

Petra Berenbrink, Artur Czumaj, Angelika Steger, and Berthold Vöcking. Balanced allocations: the heavily loaded case. Siam Journal Computing, 35(6):1350--1385, 2006.

Digital Library

[4]

John Byers, Jeffrey Considine, and Michael Mitzenmacher. Simple load balancing for distributed hash tables. In Proc. of Intl. Workshop on Peer-to-Peer System (IPTPS), pages 80--87, 2003.

[5]

John W. Byers, Jeffrey Considine, and Michael Mitzenmacher. Geometric generalizations of the power of two choices. In Proc. of Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 54--63, New York, 2004.

Digital Library

[6]

David Karger, Eric Lehman, F. Thomson Leighton, Rina Panigrahy, Matthew Levine, and Daniel Lewin. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In Symp. on Theory of Computing (STOC), pages 654--663, 1997.

Digital Library

[7]

David R. Karger and Matthias Ruhl. Simple efficient load balancing algorithms for peer-to-peer systems. In Proc. of Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 36--43, 2004.

Digital Library

[8]

Richard M. Karp, Michael Luby, and Friedhelm Meyer auf der Heide. Efficient PRAM simulation on a distributed memory machine. In Proc. 24th Symp. on Theory of Computing (STOC), pages 318--326, 1992.

Digital Library

[9]

Witold Litwin. Linear hashing: A new tool for file and table addressing. In Proceedings of International Conference on Very Large Data Bases (VLDB), pages 212--223, 1980.

[10]

John MacCormick, Nick Murphy, Venugopalan Ramasubramanian, Udi Wieder, Jinfeng Yang, and Lidong Zhou. Kinesis: The power of controlled freedom in distributed storage systems. In manuscript.

[11]

Dahlia Malkhi, Moni Naor, and David Ratajczak. Viceroy: a scalable and dynamic emulation of the butterfly. In Proc. 21st ACM Symp. on Principles of Distributed Computing, (PODC), pages 183--192, 2002.

Digital Library

[12]

Gurmeet S. Manku. Balanced binary trees for id management and load balance in distributed hash tables. In Proc. 23rd Symp. on Principles of Distributed Computing, (PODC), pages 197--205, 2004.

Digital Library

[13]

Michael Mitzenmacher, Andrèa Richa, and Ramesh Sitaraman. Handbook of Randomized Computing, chapter The power of two random choices: A survey of the techniques and results. Kluwer, 2000.

[14]

Moni Naor and Udi Wieder. Novel architectures for p2p applications: the continuous-discrete approach. In Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 50--59, 2003.

Digital Library

[15]

Martin Raab and Angelika Stege. Balls into bins - a simple and tight analysis. In RANDOM, pages 159--170, 1998.

[16]

Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable Peer-To-Peer lookup service for internet applications. In Proceedings of the 2001 ACM SIGCOMM Conference, pages 149--160, 2001.

Digital Library

[17]

Kunal Talwar and Udi Wieder. Balanced allocaitons: The weighted case. In Proc. of Symp. on Thoery of Computing (STOC), 2007.

Digital Library

[18]

B. Vècking. How asymmetry helps load balancing. In Proc. of Symp. on Foundations of Computer Science (FOCS), pages 131--141, 1999.

Digital Library

Cited By

Los DSauerwald T(2023)Balanced Allocations with the Choice of NoiseJournal of the ACM10.1145/362538670:6(1-84)Online publication date: 27-Sep-2023
https://dl.acm.org/doi/10.1145/3625386
Bhadauria RHazay CVenkitasubramaniam MWu WZhang Y(2023)Private Polynomial Commitments and Applications to MPCPublic-Key Cryptography – PKC 202310.1007/978-3-031-31371-4_5(127-158)Online publication date: 2-May-2023
https://doi.org/10.1007/978-3-031-31371-4_5
Los DSauerwald TMilani AWoelfel P(2022)Balanced Allocations with the Choice of NoiseProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538428(164-175)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538428
Show More Cited By

Index Terms

Balanced allocations with heterogenous bins
1. Mathematics of computing
  1. Probability and statistics
    1. Stochastic processes

Recommendations

Balanced Allocations with the Choice of Noise
We consider the allocation of m balls (jobs) into n bins (servers). In the standard Two-Choice process, at each step t=1,2,... ,m we first sample two randomly chosen bins, compare their two loads and then place a ball in the least loaded bin. It is well-...
Balanced allocations: the weighted case
STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

We investigate balls-and-bins processes where m weighted balls areplaced into n bins using the "power of two choices" paradigm,whereby a ball is inserted into the less loaded of two randomly chosen bins. The case where each of the m balls has unit ...
Parallel Balanced Allocations: The Heavily Loaded Case
SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures

We study parallel algorithms for the classical balls-into-bins problem, in which m balls acting in parallel as separate agents are placed into n bins. Algorithms operate in synchronous rounds, in each of which balls and bins exchange messages once. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures

June 2007

376 pages

ISBN:9781595936677

DOI:10.1145/1248377

General Chair:
Phillip B. Gibbons
Intel Research, USA
,
Program Chair:
Christian Scheideler
Technische Universität München, Germany

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SPAA07

Sponsor:

SPAA07: 19th ACM Symposium on Parallelism in Algorithms and Architectures

June 9 - 11, 2007

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
384
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)2

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Los DSauerwald T(2023)Balanced Allocations with the Choice of NoiseJournal of the ACM10.1145/362538670:6(1-84)Online publication date: 27-Sep-2023
https://dl.acm.org/doi/10.1145/3625386
Bhadauria RHazay CVenkitasubramaniam MWu WZhang Y(2023)Private Polynomial Commitments and Applications to MPCPublic-Key Cryptography – PKC 202310.1007/978-3-031-31371-4_5(127-158)Online publication date: 2-May-2023
https://doi.org/10.1007/978-3-031-31371-4_5
Los DSauerwald TMilani AWoelfel P(2022)Balanced Allocations with the Choice of NoiseProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538428(164-175)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538428
Los DSauerwald TAgrawal KLee I(2022)Balanced Allocations in BatchesProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538593(389-399)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538593
Clementi ANatale EZiccardi I(2021)Parallel Load Balancing on constrained client-server topologiesTheoretical Computer Science10.1016/j.tcs.2021.09.026895:C(16-33)Online publication date: 4-Dec-2021
https://dl.acm.org/doi/10.1016/j.tcs.2021.09.026
Clementi ANatale EZiccardi IScheideler CSpear M(2020)Parallel Load Balancing on Constrained Client-Server TopologiesProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400232(163-173)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400232
Xu KLv LLi TShen MWang HYang K(2020)Minimizing Tardiness for Data-Intensive Applications in Heterogeneous Systems: A Matching Theory PerspectiveIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.293099231:1(144-158)Online publication date: 1-Jan-2020
https://doi.org/10.1109/TPDS.2019.2930992
Mirrokni VThorup MZadimoghaddam MCzumaj A(2018)Consistent hashing with bounded loadsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175309(587-604)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175309
Zhang XChen HHu F(2017)Back Propagation Grouping: Load Balancing at Global Scale When Sources Are Skewed2017 IEEE International Conference on Services Computing (SCC)10.1109/SCC.2017.61(426-433)Online publication date: Jun-2017
https://doi.org/10.1109/SCC.2017.61
Hazay CVenkitasubramaniam M(2017)Scalable Multi-party Private Set-IntersectionPublic-Key Cryptography – PKC 201710.1007/978-3-662-54365-8_8(175-203)Online publication date: 26-Feb-2017
https://doi.org/10.1007/978-3-662-54365-8_8
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents