Time and message bounds for election in synchronous and asynchronous complete networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Time and message bounds for election in synchronous and asynchronous complete networks

Full text

Pdf (1.04 MB)

Source

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

Minaki, Ontario, Canada

Pages: 186 - 195

Year of Publication: 1985

ISBN:0-89791-168-7

Authors

Yehuda Afek	Computer Science Department, University of California, Los Angeles, CA
Eli Gafni	Computer Science Department, University of California, Los Angeles, CA

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 23, Citation Count: 11

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

	Arj83	Eshrat Arjomandi , Michael J. Fischer , Nancy A. Lynch, Efficiency of Synchronous Versus Asynchronous Distributed Systems, Journal of the ACM (JACM), v.30 n.3, p.449-456, July 1983 [doi>10.1145/2402.322387]
	Bur80	J. E. Burns, "A Formal Model for Message Passing Systems" TR-91. indiana Univ., Bloo~nin~gton (~ay 1980).
	Fre84	Greg N. Frederickson , Nancy A. Lynch, The impact of synchronous communication on the problem of electing a leader in a ring, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.493-503, December 1984 [doi>10.1145/800057.808719]
	Gaf85	Eli Gafni, Improvements in the time complexity of two message-optimal election algorithms, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.175-185, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323612]
	Gal77	Robert G. Gallager, 'IFinding a Leader in a Network with O(E) + O(N log _N) Messages,", M'.I.T. (1977). Unpublished Note.
	Gal83	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]
	Hum84	Pierre A. Humblet, "Selectinga Leader in a Clique in O(N log N) Messages," pp. 1139-1140 in Procee&ngs of 23r4 Conference on Decision and Control, Las'Vegas, Nevada (December 84).
	Kor84	E. Korach , S. Moran , S. Zaks, Tight lower and upper bounds for some distributed algorithms for a complete network of processors, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.199-207, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806747]
	Kor85	E. Korach , S. Kutten , S. Moran, A modular technique for the design of efficient distributed leader finding algorithms, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.163-174, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323611]
	Pac82	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]
	Pet84	GarvL. Peterson "Emcient Algorithms for ~lections in ~deshes and ~omplete Networks," TR 140, Dep. of Computer Science, Univ. of Rochester, Rochester, New York (August 1984).

CITED BY 11

	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
	Eli Gafni, Improvements in the time complexity of two message-optimal election algorithms, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.175-185, August 1985, Minaki, Ontario, Canada
	B. Awerbuch, Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.230-240, January 1987, New York, New York, United States
	Gurdip Singh, Leader election in complete networks, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.179-190, August 10-12, 1992, Vancouver, British Columbia, Canada
	Shay Kutten , David Peleg, Fast distributed construction of k-dominating sets and applications, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.238-251, August 20-23, 1995, Ottowa, Ontario, 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
	E. Korach , S. Kutten , S. Moran, A modular technique for the design of efficient distributed leader finding algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.84-101, Jan. 1990
	Gurdip Singh, Leader election in the presence of link failures (abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.375, August 14-17, 1994, Los Angeles, California, United States
	Alon Itai , Shay Kutten , Yaron Wolfstahl , Shmuel Zaks, Optimal Distributed t-Resilient Election in Complete Networks, IEEE Transactions on Software Engineering, v.16 n.4, p.415-420, April 1990
	Hosame H. Abu-Amara, Fault-Tolerant Distributed Algorithm for Election in Complete Networks, IEEE Transactions on Computers, v.37 n.4, p.449-453, April 1988
	H. Abu-Amara , J. Lokre, Election in Asynchronous Complete Networks with Intermittent Link Failures, IEEE Transactions on Computers, v.43 n.7, p.778-788, July 1994