An optimal synchronizer for the hypercube

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An optimal synchronizer for the hypercube

Full text

Pdf (898 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the sixth annual ACM Symposium on Principles of distributed computing table of contents

Vancouver, British Columbia, Canada

Pages: 77 - 85

Year of Publication: 1987

ISBN:0-89791-239-4

Authors

David Peleg	Department of Computer Science, Stanford University, Stanford, California
Jeffrey D. Ullman	Department of Computer Science, Stanford University, Stanford, California

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 22, Citation Count: 9

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

	A1	Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
	A2	B. Awerbuch, Reducing Complexities of the Distributed Max- Flow and Breadth-First-Search Algorithms by Means of Network Synchronization, Networks 15, (1985), pp. 425-437.
	A3	Baruch Awerbuch, Communication-time trade-offs in network synchronization, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.272-276, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323621]
	BS	B. Becker and H-U. Simon, How Robust is tile n-Cube? Proc. 27th Syrup. on Foundations of Comp. Science, 1986, pp. 283-291.
	DHSS	Danny Dolev , Joe Halpern , Barbara Simons , Ray Strong, A new look at fault tolerant network routing, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.526-535, December 1984 [doi>10.1145/800057.808723]
	GHS	R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
	H	R. Hill, A First Course i~1 Coding Theory, Oxford Applied Mathematics aad Computing Science Press, Oxford, 1986.
	P	N.C. Pease, The Indirect Bina.ry ll- Cube Microprocessor Array, IEEE Trans. Comp. 6, (1977), pp. 458- 473.
	U	Jeffrey D Ullma, Computational Aspects of VLSI, W. H. Freeman & Co., New York, NY, 1984

CITED BY 9

	David Peleg , Eli Upfal, A tradeoff between space and efficiency for routing tables, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.43-52, May 02-04, 1988, Chicago, Illinois, United States
	Samir Khuller , Balaji Raghavachari , Neal Young, Balancing minimum spanning and shortest path trees, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.243-250, January 25-27, 1993, Austin, Texas, United States
	Vojtech Bálint, The non-approximability of bicriteria network design problems, Journal of Discrete Algorithms, v.1 n.3-4, p.339-355, June 2003
	Arthur M. Farley , Andrzej Proskurowski , Daniel Zappala , Kurt Windisch, Spanners and message distribution in networks, Discrete Applied Mathematics, v.137 n.2, p.159-171, 1 March 2004
	Victor D. Chepoi , Feodor F. Dragan , Chenyu Yan, Additive sparse spanners for graphs with bounded length of largest induced cycle, Theoretical Computer Science, v.347 n.1-2, p.54-75, 30 November 2005
	Mohammad Ali Abam , Mark de Berg , Joachim Gudmundsson, A simple and efficient kinetic spanner, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Serafino Cicerone , Gabriele Di Stefano , Dagmar Handke, Self-spanner graphs, Discrete Applied Mathematics, v.150 n.1, p.99-120, 1 September 2005
	Mihai Bǎdoiu , Piotr Indyk , Anastasios Sidiropoulos, Approximation algorithms for embedding general metrics into trees, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.512-521, January 07-09, 2007, New Orleans, Louisiana
	Suleyman Uludag , King-Shan Lui , Klara Nahrstedt , Gregory Brewster, Analysis of Topology Aggregation techniques for QoS routing, ACM Computing Surveys (CSUR), v.39 n.3, p.7-es, 2007