Balanced allocations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Balanced allocations: the heavily loaded case

Full text

Pdf (1.05 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 745 - 754

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Petra Berenbrink	Department of Mathematics and Computer Science, University of Paderborn, Germany
Artur Czumaj	Department of Computer and Information Science, New Jersey, Institute of Technology
Angelika Steger	Department of Computer Science, Technische Universität, München, Germany
Berthold Vöcking	University of Massachusetts, Amherst

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 24, Citation Count: 19

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/335305.335411 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Yossi Azar , Andrei Z. Broder , Anna R. Karlin, On-line load balancing, Theoretical Computer Science, v.130 n.1, p.73-84, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90153-8]
	2	Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced Allocations, SIAM Journal on Computing, v.29 n.1, p.180-200, Feb. 2000 [doi>10.1137/S0097539795288490]
	3	D. Aldous. Random walks of finite groups and rapidly mixing Markov chains. In J. Az6ma and M. Yor, editors, Sdminaire de Probabilitds XVII, 1981/82, volume 986 of Lecture Notes in Mathematics, pages 243-297. Springer- Vefiag, Berlin, 1983.
	4	R. Bubley , M. Dyer, Path coupling: A technique for proving rapid mixing in Markov chains, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.223, October 19-22, 1997
	5	A. Czumaj. Non-Markovian couplings and generating permutations via random transpositions. Manuscript, February 2000.
	6	Devdatt Dubhashi , Desh Ranjan, Balls and bins: a study in negative dependence, Random Structures & Algorithms, v.13 n.2, p.99-124, Sept. 1998 [doi>10.1002/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M]
	7	M. Mitzenmacher, Load balancing and density dependent jump Markov processes, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.213, October 14-16, 1996
	8	Michael David Mitzenmacher , Alistair Sinclair, The power of two choices in randomized load balancing, 1996
	9	Martin Raab , Angelika Steger, "Balls into Bins" - A Simple and Tight Analysis, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.159-170, October 08-10, 1998
	10	N. D. Vvedenskaya, R. L. Dobrushin, and F. I. Karpelevich. Queueing system with selection of the shortest of two queues: An assymptotic approach. Problems oflnformation Transmission, 32(1): 15-27, january-March 1996.
	11	Berthold Vöcking, How Asymmetry Helps Load Balancing, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.131, October 17-18, 1999
	12	N. D. Vvedenskaya and Y. M. Suhov. Dobrushin's meanfield approximation for queue with dynamicTechnical Report N~ 3328, INRIA, France, December 1997.

CITED BY 19

	Peter Sanders, Asynchronous scheduling of redundant disk arrays, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.89-98, July 09-13, 2000, Bar Harbor, Maine, United States
	Petra Berenbrink , Artur Czumaj , Tom Friedetzky , Nikita D. Vvedenskaya, Infinite parallel job allocation (extended abstract), Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.99-108, July 09-13, 2000, Bar Harbor, Maine, United States
	Peter Sanders, Presenting data from experiments in algorithmics, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
	Jeremy Kepner, A multi-threaded fast convolver for dynamically parallel image filtering, Journal of Parallel and Distributed Computing, v.63 n.3, p.360-372, March 2003
	Berthold Vöcking, How asymmetry helps load balancing, Journal of the ACM (JACM), v.50 n.4, p.568-589, July 2003
	Anna Ostlin , Rasmus Pagh, Uniform hashing in constant time and linear space, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Catherine McGeoch , Peter Sanders , Rudolf Fleischer , Paul R. Cohen , Doina Precup, Using finite experiments to study asymptotic performance, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
	Peter Sanders, Asynchronous Scheduling of Redundant Disk Arrays, IEEE Transactions on Computers, v.52 n.9, p.1170-1184, September 2003
	Bogdan S. Chlebus , Dariusz R. Kowalski, Randomization helps to perform independent tasks reliably, Random Structures & Algorithms, v.24 n.1, p.11-41, January 2004
	John W. Byers , Jeffrey Considine , Michael Mitzenmacher, Geometric generalizations of the power of two choices, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Rasmus Pagh , Flemming Friche Rodler, Cuckoo hashing, Journal of Algorithms, v.51 n.2, p.122-144, May 2004
	Chung-Min Chen , Christine T. Cheng, Replication and retrieval strategies of multidimensional data on parallel disks, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
	Joep Aerts , Jan Korst , Frits Spieksma , Wim Verhaegh , Gerhard Woeginger, Random Redundant Storage in Disk Arrays: Complexity of Retrieval Problems, IEEE Transactions on Computers, v.52 n.9, p.1210-1214, September 2003
	Krishnaram Kenthapadi , Rina Panigrahy, Balanced allocation on graphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.434-443, January 22-26, 2006, Miami, Florida
	Spyros Kontogiannis, Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Mette Berger , Esben Rune Hansen , Rasmus Pagh , Mihai Pǎtraşcu , Milan Ružić , Peter Tiedemann, Deterministic load balancing and dictionaries in the parallel disk model, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Martin Dietzfelbinger , Christoph Weidling, Balanced allocation and dictionaries with tightly packed constant size bins, Theoretical Computer Science, v.380 n.1-2, p.47-68, June, 2007
	Julie Anne Cain , Peter Sanders , Nick Wormald, The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.469-476, January 07-09, 2007, New Orleans, Louisiana
	John MacCormick , Nicholas Murphy , Venugopalan Ramasubramanian , Udi Wieder , Junfeng Yang , Lidong Zhou, Kinesis: A new approach to replica placement in distributed storage systems, ACM Transactions on Storage (TOS), v.4 n.4, p.1-28, January 2009