Parallel balanced allocations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Parallel balanced allocations

Full text

Pdf (940 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures table of contents

Padua, Italy

Pages: 261 - 269

Year of Publication: 1996

ISBN:0-89791-809-6

Author

Volker Stemann

International Computer Science Institute, 1947 Center St. Berkeley, CA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 15, Citation Count: 10

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/237502.237565 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.

	ABK95	Micah Adler , John W. Byers , Richard M. Karp, Parallel sorting with limited bandwidth, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.129-136, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215431]
	ABKU94	Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced allocations (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.593-602, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195412]
	ACMR95	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 [doi>10.1145/225058.225131]
	CMS95	A. Czumaj , F. Meyer auf der Heide, Improved Optimal Shared Memory Simulations, and the Power of Reconfiguration, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.11, January 04-06, 1995
	DDLM95	T. Decker , R. Diekmann , R. Luling , B. Monien, Towards developing universal dynamic mapping algorithms, Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing, p.456, October 25-28, 1995
	DM93	Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, Simple, efficient shared memory simulations, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.110-119, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165246]
	GMR94	Leslie Ann Goldberg , Yossi Matias , Satish Rao, An optical simulation of shared memory, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.257-267, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181406]
	KLM92	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]
	KLM93	R.M. Karp, M. Luby, and F. Meyer auf der Heide. Efficient PRAM simulation on a distributed memory machine. Technical report, University of Paderborn, September 1993. To appear in Algomthmica. A preliminary version is {KLM92}.
	KSC78	V.F. Kolchin, B.A. Sevsatyanov, and V.P. Chistyakov. Random Allocation. V.H. Winston and Sons, 1978.
	LAB93	Pangfeng Liu , William Aiello , Sandeep Bhatt, An atomic model for message-passing, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.154-163, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165251]
	McD89	C. McDiarmid. On the method of bounded differences. In J. Siemons, editor, Surveys #n Combmatorics, London Mathematical Society Lecture Note Series 141, pages 148-188. Cambridge University Press, 1989.
	MNV94	Yishay Mansour , Noam Nisan , Uzi Vishkin, Trade-offs between communication throughput and parallel time, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.372-381, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195199]
	MPR94	P. D. MacKenzie , C. G. Plaxton , R. Rajaraman, On contention resolution protocols and associated probabilistic phenomena, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.153-162, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195122]
	MSS95	F. Meyer auf der Heide, C. Scheideler, and V. Stemann. Exploiting storage redundancy to speed up randomized shared memory simulations. In Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, pages 267-278, 1995.
	UW87	Eli Upfal , Avi Wigderson, How to share memory in a distributed system, Journal of the ACM (JACM), v.34 n.1, p.116-127, Jan. 1987 [doi>10.1145/7531.7926]

CITED BY 10

	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 , 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
	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
	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
	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
	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, 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
	Berthold Vöcking, How asymmetry helps load balancing, Journal of the ACM (JACM), v.50 n.4, p.568-589, July 2003
	Michael Mitzenmacher, Studying Balanced Allocations with Differential Equations, Combinatorics, Probability and Computing, v.8 n.5, p.473-482, September 1999
	Srinivas Kashyap , Supratim Deb , K. V. M. Naidu , Rajeev Rastogi , Anand Srinivasan, Efficient gossip-based aggregate computation, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA