Improvements in the time complexity of two message-optimal election algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improvements in the time complexity of two message-optimal election algorithms

Full text

Pdf (1.01 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: 175 - 185

Year of Publication: 1985

ISBN:0-89791-168-7

Author

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): 18, Citation Count: 17

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

	Afe	Yehuda Afek , Eli Gafni, Time and message bounds for election in synchronous and asynchronous complete networks, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.186-195, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323613]
	Als76	Peter A. Alsberg , John D. Day, A principle for resilient sharing of distributed resources, Proceedings of the 2nd international conference on Software engineering, p.562-570, October 13-15, 1976, San Francisco, California, United States
	Bur80	J. E. Burns, "A Formal Model for Message Passing systems," TR-91, Indiana Univ., Bloomington (May 1980).
	Cha79a	Ernest Chang , Rosemary Roberts, An improved algorithm for decentralized extrema-finding in circular configurations of processes, Communications of the ACM, v.22 n.5, p.281-283, May 1979 [doi>10.1145/359104.359108]
	Cha79b	Ernest Jen-Hao Chang, "Decentralized Algorithms in Distributed Systems," CSRG-103, University of Toronto, Toronto, Canada (October 1979). Ph.D. Thesis.
	Dol82	Danny Dolev, Maria Klawe, and Michael Rodeh, "An O(n log n) Unidirectional Algorithm for Extrema Finding in a Circle," Journal of Algorithm 3, pp.245-260 (1982).
	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]
	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]
	Ger80	M. Gerla and L. Kleinrock, "Flow Control: A Comparative Study," IEEE Trans. Commu. COM-28, pp.553-574 (Apr. 1980).
	Hir80	D. S. Hirschberg , J. B. Sinclair, Decentralized extrema-finding in circular configurations of processors, Communications of the ACM, v.23 n.11, p.627-628, Nov. 1980 [doi>10.1145/359024.359029]
	Ita81	A. itai and M. Rodeh, "The lord of the ring or probabilistic methods for breaking symmetry in distributed networks," RJ-3110, IBM (April 1981).
	Men78	Daniel A. Menasce , Gerald J. Popek , Richard R. Muntz, A locking protocol for resource coordination in distributed databases, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509256]
	Pet82	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]
	Pri57	R.C. Prim, "Shortest Connection Networks and Some Generalizations," Bell System Technical Journal 30, pp.1389- 1401 (1957).
	Seg83	Adrian Segall, "Distributed Network Protocols," IEEE Transactions on Information Theory iT-29(1) (January 10ss).
	Vit84	Paul M.B. Vitányi, Distributed elections in an archimedean ring of processors, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.542-547, December 1984 [doi>10.1145/800057.808725]

CITED BY 17

	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
	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
	Michalis Faloutsos , Mart Molle, Optimal distributed algorithm for minimum spanning trees revisited, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.231-237, August 20-23, 1995, Ottowa, Ontario, Canada
	Yehuda Afek , Eli Gafni, Time and message bounds for election in synchronous and asynchronous complete networks, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.186-195, August 1985, Minaki, Ontario, Canada
	C. Cheng , I. Cimet , S. Kumar, A protocol to maintain a minimum spanning tree in a dynamic topology, ACM SIGCOMM Computer Communication Review, v.18 n.4, p.330-337, August 1988
	Prasoon Tiwari, Lower bounds on communication complexity in distributed computer networks, Journal of the ACM (JACM), v.34 n.4, p.921-938, Oct. 1987
	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
	Michael Elkin, A faster distributed protocol for constructing a minimum spanning tree, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Jennifer L. Welch , Leslie Lamport , Nancy Lynch, A lattice-structured proof of a minimum spanning, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.28-43, August 15-17, 1988, Toronto, Ontario, Canada
	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
	Michalis Faloutsos , Mart Molle, A linear-time optimal-message distributed algorithm for minimum spanning trees, Distributed Computing, v.17 n.2, p.151-170, August 2004
	Michael Elkin, Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Gurdip Singh , Arthur J. Bernstein, A highly asynchronous minimum spanning tree protocol, Distributed Computing, v.8 n.3, p.151-161, March 1995
	Hasan M. Sayeed , Marwan Abu-Amara , Hosame Abu-Amara, Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links, Distributed Computing, v.9 n.3, p.147-156, December 1995
	M. S. Kordafshari , M. Gholipour , M. Jahanshahi , A. T. Haghighat, Two novel algorithms for electing coordinator in distributed systems basedon bully algorithm, Proceedings of the 4th WSEAS International Conference on Software Engineering, Parallel & Distributed Systems, p.1-6, February 13-15, 2005, Salzburg, Austria
	Michael Elkin, A faster distributed protocol for constructing a minimum spanning tree, Journal of Computer and System Sciences, v.72 n.8, p.1282-1308, December, 2006
	Pierre Fraigniaud , Amos Korman , Emmanuelle Lebhar, Local MST computation with short advice, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA