On the bit complexity of distributed computations in a ring with a leader

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the bit complexity of distributed computations in a ring with a leader

Full text

Pdf (532 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: 151 - 160

Year of Publication: 1986

ISBN:0-89791-198-9

Authors

Y Mansour	Department of Computer Science, Technion - Israel Institute of Technology, Haifa, Israel
S Zaks	Department of Computer Science, Technion - Israel Institute of Technology, Haifa, Israel

Sponsor

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 7, Citation Count: 3

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.10603 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.

	ASW	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]
	DKR	D. Dolev, M. Klawe and M. Rodeh, An O(n logn) unidirectional distributed algorithm for extrema finding in a circle, Journal of algorithms, 3, 1982, pp. 245- 260.
	E	Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
	F	Greg N. Frederickson, Tradeoffs for selection in distributed networks (Preliminary Version), Proceedings of the second annual ACM symposium on Principles of distributed computing, p.154-160, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806718]
	HA	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]
	HE	F. C. Hennei, One-tape, off-line Turing machine computations, Information and Control 8, 1965, pp. 553-578.
	HU	John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	IR	A. Itai and M. Rodeh, Symmetry breaking in distributed networks, Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science, 1981, pp. 150-158.
	KRS	E Korach , D Rotem , N Santoro, Distributed algorithms for finding centers and medians in networks, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.3, p.380-401, July 1984 [doi>10.1145/579.585]
	MC	Jayadev Misra , K. M. Chandy, A Distributed Graph Algorithm: Knot Detection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.678-686, Oct. 1982 [doi>10.1145/69622.357190]
	MW	Shlomo Moran , Manfred Warmuth, Gap theorems for distributed computing, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.131-150, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10602]
	P	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]
	PKR	Jan K. Pachl , E. Korach , D. Rotem, A technique for proving lower bounds for distributed maximum-finding algorithms (Preliminary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.378-382, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802213]
	T	B. A. Trachtenbrot, Turing machine computations with logarithmic delay, (in Russian) Algebra I logica 3 , 1964, pp. 33-48. English translation in TR 5, 1966, Computing Center, University of California at Berkeley, Berkeley, CA.

CITED BY 3

	Alain Mayer , Yoram Ofek , Rafail Ostrovsky , Moti Yung, Self-stabilizing symmetry breaking in constant-space (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.667-678, May 04-06, 1992, Victoria, British Columbia, 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
	Shlomo Moran , Manfred Warmuth, Gap theorems for distributed computing, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.131-150, August 11-13, 1986, Calgary, Alberta, Canada