Balanced allocations (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Balanced allocations (extended abstract)

Full text

Pdf (902 KB)

Source

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

Montreal, Quebec, Canada

Pages: 593 - 602

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Yossi Azar	Tel Aviv University, Israel
Andrei Z. Broder	Digital Systems Research Center, 130 Lytton Avenue, Palo Alto, CA
Anna R. Karlin	Digital Systems Research Center, 130 Lytton Avenue, Palo Alto, CA
Eli Upfal	IBM Almaden Research Center, San Jose, CA and Department of Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 89, Citation Count: 46

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/195058.195412 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	N. Alon and J. Spencer. The probabilistic method. John Wiley and Sons, 1992.
	2	James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line load balancing with applications to machine scheduling and virtual circuit routing, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.623-631, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167248]
	3	B. Awerbuch, Y. Azar and S. Plotkin. Throughput competitive online routing. In Proceedings of the 3#th IEEE Conference on Foundations of Computer Science, pp. 32-40, 1993.
	4	Baruch Awerbuch , Yossi Azar , Serge Plotkin , Orli Waarts, Competitive routing of virtual circuits with unknown duration, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.321-327, January 23-25, 1994, Arlington, Virginia, United States
	5	Y. Azar, A. Z. Broder and A .R. Karlin. Online load balancing. In Proceedzngs of the 33rd IEEE Conference on Foundatwns of Computer Science, 1992.
	6	Yossi Azar , Bala Kalyanasundaram , Serge A. Plotkin , Kirk Pruhs , Orli Waarts, Online Load Balancing of Temporary Tasks, Proceedings of the Third Workshop on Algorithms and Data Structures, p.119-130, August 11-13, 1993
	7	Yossi Azar , Joseph Naor , Raphael Rom, The competitiveness of on-line assignments, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.203-210, September 1992, Orlando, Florida, United States
	8	Andrei Z. Broder , Anna R. Karlin, Multilevel adaptive hashing, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.43-53, January 22-24, 1990, San Francisco, California, United States
	9	M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, R. Tarjan. Dynamic Perfect Hashing- Upper and Lower Bounds In Proceedings of the P9th IEEE Conference on Foundations of Computer Science, 1988.
	10	Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
	11	Gaston H. Gonnet, Expected Length of the Longest Probe Sequence in Hash Code Searching, Journal of the ACM (JACM), v.28 n.2, p.289-304, April 1981 [doi>10.1145/322248.322254]
	12	Norman L. Johnson and Samuel Kotz. Urn Models and Their Application. John Wiley & Sons, 1977.
	13	Richard M. Karp , Michael Luby , Friedhelm Meyer auf der Heide, Efficient PRAM simulation on a distributed memory machine, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.318-326, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129743]
	14	R. M. Karp , U. V. Vazirani , V. V. Vazirani, An optimal algorithm for on-line bipartite matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.352-358, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100262]
	15	Valentin F. Kolchin, Boris A. Sevastyanov, and V#ldlmir P. Chi.#tyakov. Random Allocations. John Wiley & Sons, 1978.
	16	Steven Phillips , Jeffery Westbrook, Online load balancing and network flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.402-411, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167201]
	17	Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]

CITED BY 46

	Michael Mitzenmacher, Analyses of load stealing models based on differential equations, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.212-221, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Petra Berenbrink , Tom Friedetzky , Ernst W. Mayr, Parallel continuous randomized load balancing (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.192-201, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Petra Berenbrink , Friedhelm Meyer auf der Heide , Klaus Schröder, Allocating weighted jobs in parallel, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.302-310, June 23-25, 1997, Newport, Rhode Island, United States
	Susanne Albers , Michael Mitzenmacher, Average-case analyses of first fit and random fit bin packing, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.290-299, January 25-27, 1998, San Francisco, California, United States
	Michael Mitzenmacher, How useful is old information (extended abstract)?, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.83-91, August 21-24, 1997, Santa Barbara, California, United States
	Micah Adler , Soumen Chakrabarti , Michael Mitzenmacher , Lars Rasmussen, Parallel randomized load balancing, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.238-247, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Marios Mavronicolas , Paul Spirakis, The price of selfish routing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.510-519, July 2001, Hersonissos, Greece
	Jan Korst, Random duplicated assignment: an alternative to striping in video servers, Proceedings of the fifth ACM international conference on Multimedia, p.219-226, November 09-13, 1997, Seattle, Washington, United States
	Keqin Li, Deterministic and randomized algorithms for distributed on-line task assignment and load balancing without load status information, Proceedings of the 1998 ACM symposium on Applied Computing, p.613-622, February 27-March 01, 1998, Atlanta, Georgia, United States
	Miklos Ajtai , James Aspnes , Moni Naor , Yuval Rabani , Leonard J. Schulman , Orli Waarts, Fairness in scheduling, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.477-485, January 22-24, 1995, San Francisco, California, United States
	Petra Berenbrink , Tom Friedetzky , Angelika Steger, Randomized and adversarial load balancing, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.175-184, June 27-30, 1999, Saint Malo, France
	Michael Mitzenmacher, On the analysis of randomized load balancing schemes, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.292-301, June 23-25, 1997, Newport, Rhode Island, United States
	Petra Berenbrink , Marco Riedel , Christian Scheideler, Simple competitive request scheduling strategies, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.33-42, June 27-30, 1999, Saint Malo, France
	Artur Czumaj, Recovery time of dynamic allocation processes, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.202-211, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Jose Renato Santos , Richard R. Muntz , Berthier Ribeiro-Neto, Comparing random data allocation and data striping in multimedia servers, ACM SIGMETRICS Performance Evaluation Review, v.28 n.1, p.44-55, June 2000
	Peter Sanders , Sebastian Egner , Jan Korst, Fast concurrent access to parallel disks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.849-858, January 09-11, 2000, San Francisco, California, United States
	Michael Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, IEEE Transactions on Parallel and Distributed Systems, v.12 n.10, p.1094-1104, October 2001
	Richard Cole , Bruce M. Maggs , Friedhelm Meyer auf der Heide , Michael Mitzenmacher , Andréa W. Richa , Klaus Schröder , Ramesh K. Sitaraman , Berthold Vöcking, Randomized protocols for low-congestion circuit routing in multistage interconnection networks, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.378-388, May 24-26, 1998, Dallas, Texas, United States
	Volker Stemann, Parallel balanced allocations, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.261-269, June 24-26, 1996, Padua, Italy
	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
	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
	Berthold Vöcking, How asymmetry helps load balancing, Journal of the ACM (JACM), v.50 n.4, p.568-589, July 2003
	Lixin Gao , Arnold L. Rosenberg , Ramesh K. Sitaraman, On trading task reallocation for thread management in partitionable multiprocessors, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.309-317, June 24-26, 1996, Padua, Italy
	Haoyu Song , Sarang Dharmapurikar , Jonathan Turner , John Lockwood, Fast hash table lookup using extended bloom filter: an aid to network processing, ACM SIGCOMM Computer Communication Review, v.35 n.4, October 2005
	Paul W. Goldberg, Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Michael Mitzenmacher, How Useful Is Old Information?, IEEE Transactions on Parallel and Distributed Systems, v.11 n.1, p.6-20, January 2000
	Michael Dahlin, Interpreting Stale Load Information, IEEE Transactions on Parallel and Distributed Systems, v.11 n.10, p.1033-1047, October 2000
	Edward Chang , Chen Li , Hector Garcia-Molina, Managing parallel disks for continuous media data, Information organization and databases: foundations of data organization, Kluwer Academic Publishers, Norwell, MA, 2000
	Luc Devroye , Pat Morin, Cuckoo hashing: further analysis, Information Processing Letters, v.86 n.4, p.215-219, 31 May 2003
	Peter Sanders, Asynchronous Scheduling of Redundant Disk Arrays, IEEE Transactions on Computers, v.52 n.9, p.1170-1184, September 2003
	Rina Panigrahy, Efficient hashing with lookups in two memory accesses, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Sailesh Kumar , Patrick Crowley, Segmented hash: an efficient hash table implementation for high performance networking subsystems, Proceedings of the 2005 symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA
	Sailesh Kumar , Patrick Crowley, Segmented hash: an efficient hash table implementation for high performance networking subsystems, Proceedings of the 2005 symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA
	Aris Anagnostopoulos , Ioannis Kontoyiannis , Eli Upfal, Steady state analysis of balanced-allocation routing, Random Structures & Algorithms, v.26 n.4, p.446-467, July 2005
	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
	Michael Mitzenmacher, Studying Balanced Allocations with Differential Equations, Combinatorics, Probability and Computing, v.8 n.5, p.473-482, September 1999
	Chen Avin , Bhaskar Krishnamachari, The power of choice in random walks: an empirical study, Proceedings of the 9th ACM international symposium on Modeling analysis and simulation of wireless and mobile systems, October 02-06, 2006, Terromolinos, Spain
	Rodney B. Wallace , Ward Whitt, A Staffing Algorithm for Call Centers with Skill-Based Routing, Manufacturing & Service Operations Management, v.7 n.4, p.276-294, Fall 2005
	Jahangir Hasan , Srihari Cadambi , Venkatta Jakkula , Srimat Chakradhar, Chisel: A Storage-efficient, Collision-free Hash-based Network Processing Architecture, ACM SIGARCH Computer Architecture News, v.34 n.2, p.203-215, May 2006
	Luc Devroye , Gabor Lugosi , Gahyun Park , Wojciech Szpankowski, Multiple choice tries and distributed hash tables, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.891-899, January 07-09, 2007, New Orleans, Louisiana
	Haiying Shen , Cheng-Zhong Xu, Hash-based proximity clustering for efficient load balancing in heterogeneous DHT networks, Journal of Parallel and Distributed Computing, v.68 n.5, p.686-702, May, 2008
	Chen Avin , Bhaskar Krishnamachari, The power of choice in random walks: An empirical study, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.1, p.44-60, January, 2008
	P. Brighten Godfrey, Balls and bins with structure: balanced allocations on hypergraphs, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.511-517, January 20-22, 2008, San Francisco, California
	Henry Lin , Christos Amanatidis , Martha Sideri , Richard M. Karp , Christos H. Papadimitriou, Linked decompositions of networks and the power of choice in Polya urns, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.993-1002, January 20-22, 2008, San Francisco, California
	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
	Haiying Shen , Cheng-Zhong Xu, Locality-Aware and Churn-Resilient Load-Balancing Algorithms in Structured Peer-to-Peer Networks, IEEE Transactions on Parallel and Distributed Systems, v.18 n.6, p.849-862, June 2007