Article

Free access

Recovery time of dynamic allocation processes

Author:

Artur CzumajAuthors Info & Claims

SPAA '98: Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures

Pages 202 - 211

https://doi.org/10.1145/277651.277686

Published: 01 June 1998 Publication History

PDF eReader

References

[1]

M. Adler, S. Chakrabarti, M. Mitzenmacher, and L. Rasmussen. Parallel randomized load balancing. In Proceedings of the 27th Annual A CM Symposium on Theory of Computing, pages 238-247, Las Vegas, Nevada, May 29-June 1, 1995. ACM Press, New York, NY.

Digital Library

Google Scholar

[2]

M. Ajtai, J. Aspnes, M. Naor, Y. Rabani, L. J. Schulman, and O. Waarts. Fairness in scheduling. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 477-485, San Francisco, CA, January 22-24, 1995. SIAM, Philadelphia, PA.

Digital Library

Google Scholar

[3]

D. Aldous. Random walks of finite groups and rapidly mixing Markov chains, in J. Az#ma and M. Yor, e(titors, S#rninaire de Probabilitds XVII, 1981//82, volume 986 of Lecture Notes in Mathematics, pages 243-297. Springer-Verlag, Berlin, 1983.

Google Scholar

[4]

R. Anderson, L. Lov~sz, P. Shor, J. Spencer, E. Tardos, and S. Winograd. Disks, balls, and walls: Analysis of a combinatorial game. American Mathematical Monthly, 96(6):481-493, 1989.

Digital Library

Google Scholar

[5]

Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal. Balanced allocations. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 593-602, Montreal, Quebec, Canada, May 23-25, 1994. ACM Press, New York, NY.

Digital Library

Google Scholar

[6]

P. Berenbrink, F. Meyer auf der Heide, and K. Schr5der. Allocating weighted jobs in parallel. In Proceedings of the 9th Annual A CM Symposium on Parallel Algorithms and Architectures, pages 302-310, Newport, RI, June 22-25, 1997. ACM Press, New York, NY.

Digital Library

Google Scholar

[7]

R. Bubley and M. Dyer. Path coupling: A technique for proving rapid mixing in Markov chains. In Proceedings of the 38th IEEE Symposium on Foundations of Computer Science, pages 223-231, Miami Beach, FL, October 19-22, 1997. IEEE Computer Society Press, Los Alamitos, CA.

Digital Library

Google Scholar

[8]

R. Bubley and M. Dyer. Faster random generation of linear extensions. In Proceedings of the 9th Annual A CM-SIAM Symposium on Discrete Algorithms, pages 350-354, San Francisco, CA, january 25-27, 1998. SIAM, Philadelphia, PA.

Digital Library

Google Scholar

[9]

R. Bubley, M. Dyer, and C. GreenhiI1. Beating the 2A bound for approximately counting colourings: A computer-assisted proof of rapid mixing. In Proceedings of the 9th Annual A CM-SIAM Symposium on Discrete Algorithms, pages 355-363, San Francisco, CA, January 25-27, 1998. SIAM, Philadelphia, PA.

Digital Library

Google Scholar

[10]

A. Czumaj, P. Kanarek, M. Kutytowski, and K. Loryg. Delayed path coupling and its applications to analysing distributed stochastic processes for generating random permutations. Manuscript, April 1998.

Google Scholar

[11]

A. Czumaj and V. Stemann. Randomized allocation processes. In Proceedings of the 38th IEEE Symposium on Foundations of Computer Science, pages 194-203, Miami Beach, FL, October 19-22, 1997. IEEE Computer Society Press, Los Alamitos, CA.

Digital Library

Google Scholar

[12]

P. Diaconis. Group Representations in Probability and Statistics, volume 11 of Lecture Notes - Monograph Series. Institute of Mathematical Statistics, Hayward, CA, 1988.

Google Scholar

[13]

R. Fagin and J. H. Williams. A fair carpool scheduling algorithm. IBM Journal of Research and Development, 27(2):133-139, March 1983.

Digital Library

Google Scholar

[14]

M. Jerrum and A. Sinclair. Tile Markov chain Monte Carlo method: An approach to approximate counting and integration. In D. S. Hochbaum, editor, Approximation Algorithms for AfTa-Hard Problems, chapter 12, pages 482-520. PWS Publishing Company, Boston, MA, 1996.

Digital Library

Google Scholar

[15]

N. L. Johnson and S. Kotz. Urn Models and Their Application: An Approach to Modern Discrete Probability Theory. Wiley series in probability and mathematical statistics: Applied probability and statistics. John Wiley & Soils, New York, NY, 1977.

Google Scholar

[16]

V. F. Kolchin, B. A. Sevast'yanov, and V. P. Chistyakov. Random Allocations. V. H. Winston & Sons, Washington, D.C., 1978.

Google Scholar

[17]

T. Lindvall. Lectures on the Coupling Method. Wiley series in Probability and Mathematical Statistics. John Wiley & Sons, New York, NY, 1992.

Google Scholar

[18]

M. Mitzenmacher. Load balancing and density dependent jump Markov processes. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, pages 213-222, Burlington, Vermont, October 14-16, 1996. IEEE Computer Society Press, Los Alamitos, CA.

Digital Library

Google Scholar

[19]

M. Mitzenmacher. How useful is old information. In Proceedings of the 16th A CM Symposium on Principles of Distributed Computing, pages 83-91, Santa Barbara, August 21-24, 1997. ACM Press, New York, NY.

Digital Library

Google Scholar

[20]

M. Mitzenmacher. On the analysis of randomized load balancing schemes. In Proceedings of the 9th Annual A CM Symposium on Parallel Algorithms and Architectures, pages 292-301, Newport, RI, June 22-25, 1997. ACM Press, New York, NY.

Digital Library

Google Scholar

[21]

M. Mitzenmacher. Studying balanced allocations with differential equations. Technical Report SRC Technical Note 1997-024, System Research Center of Digital Equipment Corporation, Palo Alto, CA, October 1997.

Google Scholar

[22]

M. D. Mitzenmacher. The Power of Two Choices in Randomized Load Balancing. PhD thesis, Computer Science Department, University of California at Berkeley, September 1996.

Digital Library

Google Scholar

[23]

A. Sinclair. Algorithms for Random Generation and Counting: A Markov Chain Approach. Progress in Theoretical Computer Science. Birkh~user, Boston, MA, 1993.

Digital Library

Google Scholar

[24]

V. Stemann. Parallel balanced allocations. In Proceedings of the 8th Annual A CM Symposium on Parallel Algorithms and Architectures, pages 261-269, Padua, Italy, June 24-26, 1996. ACM Press, New York, NY.

Digital Library

Google Scholar

Cited By

View all

Becchetti LClementi ANatale EPasquale FPosta G(2019)Self-stabilizing repeated balls-into-binsDistributed Computing10.1007/s00446-017-0320-432:1(59-68)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00446-017-0320-4
Berenbrink PFriedetzky TKling PMallmann-Trenn FNagel LWastell C(2018)Self-Stabilizing Balls and Bins in BatchesAlgorithmica10.5555/3288645.328867880:12(3673-3703)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.5555/3288645.3288678
Berenbrink PFriedetzky TKling PMallmann-Trenn FNagel LWastell C(2018)Self-Stabilizing Balls and Bins in BatchesAlgorithmica10.1007/s00453-018-0411-z80:12(3673-3703)Online publication date: 15-Feb-2018
https://doi.org/10.1007/s00453-018-0411-z
Show More Cited By

Index Terms

Recovery time of dynamic allocation processes
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages
        Distributed programming languages
        Parallel programming languages
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management

Recommendations

Allocation of processes and files for load balancing in distributed systems
Resource allocation in dynamic real-time systems
Randomized Allocation Processes
FOCS '97: Proceedings of the 38th Annual Symposium on Foundations of Computer Science

We investigate various randomized processes allocating balls into bins that arise in applications in dynamic resource allocation and on-line load balancing. We consider the scenario when m balls arriving sequentially are to be allocated into n bins on-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '98: Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures

June 1998

312 pages

ISBN:0897919890

DOI:10.1145/277651

Chairmen:
Gary Miller
Carnegie Mellon Univ., Pittsburgh, PA
,
Phillip B. Gibbons
Bell Labs

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SPAA/PODC98

Sponsor:

SPAA/PODC98: 10th Annual ACM Symposium on Parallel Algorithms and Architectures/Symposium on Principles of Distributed Computing

June 28 - July 2, 1998

Puerto Vallarta, Mexico

Acceptance Rates

SPAA '98 Paper Acceptance Rate 30 of 84 submissions, 36%;

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

Upcoming Conference

SPAA '25

Sponsor:
sigact
sigact

37th ACM Symposium on Parallelism in Algorithms and Architectures

July 28 - August 1, 2025

Portland , OR , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
299
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)6

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Becchetti LClementi ANatale EPasquale FPosta G(2019)Self-stabilizing repeated balls-into-binsDistributed Computing10.1007/s00446-017-0320-432:1(59-68)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00446-017-0320-4
Berenbrink PFriedetzky TKling PMallmann-Trenn FNagel LWastell C(2018)Self-Stabilizing Balls and Bins in BatchesAlgorithmica10.5555/3288645.328867880:12(3673-3703)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.5555/3288645.3288678
Berenbrink PFriedetzky TKling PMallmann-Trenn FNagel LWastell C(2018)Self-Stabilizing Balls and Bins in BatchesAlgorithmica10.1007/s00453-018-0411-z80:12(3673-3703)Online publication date: 15-Feb-2018
https://doi.org/10.1007/s00453-018-0411-z
Berenbrink PKling PLiaw CMehrabian A(2017)Tight Load Balancing Via Randomized Local Search2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2017.52(192-201)Online publication date: May-2017
https://doi.org/10.1109/IPDPS.2017.52
Berenbrink PFriedetzky TKling PMallmann-Trenn FNagel LWastell CGiakkoupis G(2016)Self-stabilizing Balls & Bins in BatchesProceedings of the 2016 ACM Symposium on Principles of Distributed Computing10.1145/2933057.2933092(83-92)Online publication date: 25-Jul-2016
https://dl.acm.org/doi/10.1145/2933057.2933092
Berenbrink PFriedetzky TGoldberg LGoldberg PHu ZMartin R(2006)Distributed selfish load balancingProceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm10.5555/1109557.1109597(354-363)Online publication date: 22-Jan-2006
https://dl.acm.org/doi/10.5555/1109557.1109597
Luczak MMcDiarmid C(2005)On the power of two choices: Balls and bins in continuous timeThe Annals of Applied Probability10.1214/10505160500000020515:3Online publication date: 1-Aug-2005
https://doi.org/10.1214/105051605000000205
Czumaj AKanarek PLoryś KKutylowski M(2001)Switching Networks for Generating Random PermutationsSwitching Networks: Recent Advances10.1007/978-1-4613-0281-0_2(25-61)Online publication date: 2001
https://doi.org/10.1007/978-1-4613-0281-0_2
Berenbrink PCzumaj AFriedetzky TVvedenskaya NMiller GTeng S(2000)Infinite parallel job allocation (extended abstract)Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures10.1145/341800.341813(99-108)Online publication date: 9-Jul-2000
https://dl.acm.org/doi/10.1145/341800.341813
Berenbrink PFriedetzky TSteger AMiller GRamachandran V(1999)Randomized and adversarial load balancingProceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures10.1145/305619.305638(175-184)Online publication date: 1-Jun-1999
https://dl.acm.org/doi/10.1145/305619.305638
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Allocation of processes and files for load balancing in distributed systems

Resource allocation in dynamic real-time systems

Randomized Allocation Processes