A modular technique for the design of efficient distributed leader finding algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A modular technique for the design of efficient distributed leader finding algorithms

Full text

Pdf (828 KB)

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: 163 - 174

Year of Publication: 1985

ISBN:0-89791-168-7

Authors

E. Korach	Computer Science Department, Technion, Israel Institute of Technology, Haifa, Israel
S. Kutten	Computer Science Department, Technion, Israel Institute of Technology, Haifa, Israel
S. Moran	Computer Science Department, Technion, Israel Institute of Technology, Haifa, Israel

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): 2, Downloads (12 Months): 16, 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/323596.323611 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.

	B80	Burns, J. E., "A Formal Model fo Message Passing Systems", TR-91, Indiana University, September 1980.
	DKR82	Dolev, D., Klawe, M., and Rodeh, M., "An O(n log n) Unidirectional Distributed Algorithm for Extrema Finding in a Circle", J of Algorithms,
	EJ73	Edmonds, j. and Johnson E. L., "Matching, Euler Tour and the Chinese Postman", Math. Prograrr~ming 5 (1973), 8B-124.
	FL84	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]
	G77	Gallager, R. G., "Choosing a Leader in a Network", unpublished memorandum, M.I.T.
	GA84a	Eli Gafni , Yehuda Afek, Election and traversal in unidirectional networks, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.190-198, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806746]
	GA84b	Gafni, E., and Afek, Y., "A simple and Efficient Distributed Algorithm for Election in Complete Networks", (a summary) 19B4.
	GHS83	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]
	GK84	Gafni, E., and Korfhage, W., "Distributed Election in Unidirectional Eulerian Networks", Proceedings Twenty-Second Annual Allerton Conference on Communica- ~on, Control, and Computing*', AUerton, IL, October 3-5, 1984.
	H84	Humbler, P., "Selecting a Leader in a Clique in O(r~ log n) Messages", internal memorandum, Laboratory for Information and Decision Systems, M.I.T., February, 1984.
	HS80	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]
	K84a	Kutten, S. "A Unified Approach to the h-T{ieient Construction of Distributed Leader-Finding-Algorithms", iEEE International Conference on Uammunic=tian and Energy, Montreal, Canada October 1984.
	K84b	Kutten, S. "Traversing Directed Graphs- an Upper and Lower Bound", an intermediary report to the I).Sc advisor.
	KMZ83	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]
	KRS81	Korach, E., Rotem, D., and Santoro, N., "A Probabilistic Algorithm for Decentralized Extrema- Finding in a Circular Configuration of Processors", Technical Report, University of Waterloo, Ontario, Canada, 1981.
	KRS84	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]
	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]
	PKR82	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]
	S81	Segal, A., "Distributed Network Protocols", EE P~bl, 414, Department of Electrical Engeneering, Technion, Haifa, Israel, July 1981.
	T81	A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988

CITED BY 3

	L. Bougé , N. Francez, A compositional approach to superimposition, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.240-249, January 10-13, 1988, San Diego, California, United States
	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
	Baruch Awerbuch , Shay Kutten , David Peleg, Efficient deadlock-free routing, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.177-188, August 19-21, 1991, Montreal, Quebec, Canada