Gap theorems for distributed computing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Gap theorems for distributed computing

Full text

Pdf (712 KB)

Source

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

Calgary, Alberta, Canada

Pages: 131 - 150

Year of Publication: 1986

ISBN:0-89791-198-9

Authors

Shlomo Moran	Department of Computer Science, the Technion, Haifa 32000, Israel and IBM Thomas J. Watson Research Center, Yorktown Heights, NY
Manfred Warmuth	Department of Computer and Information Sciences, University of California, Santa Cruz, CA

Sponsor

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 12, Citation Count: 5

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

	AHU83	Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
	ASW85	Chagit Attiya , Marc Snir , Manfred Warmuth, Computing on an anonymous ring, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.196-203, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323614]
	B46	N. G. de Bruijn, "A Combinatorial Problem," Koninklijke Nederlands Akademie van Wetenschappen, Proceedings, Vol. 49 (Part 2), 1946, pp. 758-764.
	B80	J.E. Burns, "A Formal Model for Message Passing Systems," Technical Report No. 91, Computer Science Department, Indiana University, Bloomington, In. 1980.
	DKR82	D. Dolev, M. Klawe and M. Rodeh. "An 0 (nlogn ) Unidirectional Algorithm for Extrema Finding in a Circle," J. of Algorithms, Vol. 3, No. 3,1982, pp. 245-260.
	E79	Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
	FLM85	Michael J. Fischer , Nancy A. Lynch , Michael Merritt, Easy impossibility proofs for distributed consensus problems, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.59-70, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323602]
	H68	J. Hartmanis, Computational Complexity of One-Tape Turing Machine Computations, Journal of the ACM (JACM), v.15 n.2, p.325-339, April 1968 [doi>10.1145/321450.321464]
	MZ85	Y Mansour , S Zaks, On the bit complexity of distributed computations in a ring with a leader, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.151-160, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10603]
	P82	Gary L. Peterson, An O(nlog n) Unidirectional Algorithm for the Circular Extrema Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.758-762, Oct. 1982 [doi>10.1145/69622.357194]
	PKR84	Jan K. Pachl , E. Korach , D. Rotem, Lower Bounds for Distributed Maximum-Finding Algorithms, Journal of the ACM (JACM), v.31 n.4, p.905-918, Oct. 1984 [doi>10.1145/1634.1889]
	T64	B. A. Trachtenbrot, "Turing computations with logarithmic delay" (In Russian), Algebra i Logica, Vol. 3, 1964, pp. 33-48, English Translation in University of California Computing Center, Technical Report, No. 5, Berkeley, California, 1966.

CITED BY 5

	Masafumi Yamashita , Tiko Kameda, Computing on an anonymous network, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.117-130, August 15-17, 1988, Toronto, Ontario, Canada
	Baruch Awerbuch , Rafail Ostrovsky, Memory-efficient and self-stabilizing network RESET (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.254-263, August 14-17, 1994, Los Angeles, California, United States
	N. Lynch, A hundred impossibility proofs for distributed computing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.1-28, June 1989, Edmonton, Alberta, Canada
	Y Mansour , S Zaks, On the bit complexity of distributed computations in a ring with a leader, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.151-160, August 11-13, 1986, Calgary, Alberta, Canada
	Baruch Awerbuch , Oded Goldreich , Ronen Vainish , David Peleg, A trade-off between information and communication in broadcast protocols, Journal of the ACM (JACM), v.37 n.2, p.238-256, April 1990