More Web Proxy on the site http://driver.im/

Article

Free access

Election and traversal in unidirectional networks

Authors:

Yehuda AfekAuthors Info & Claims

PODC '84: Proceedings of the third annual ACM symposium on Principles of distributed computing

Pages 190 - 198

https://doi.org/10.1145/800222.806746

Published: 02 June 2019 Publication History

Abstract

This paper presents distributed algorithms for election and traversal in strongly connected unidirectional networks. A unidirectional network consists of nodes which are processors connected by unidirectional communication links. Initially, processors differ by their identifier but are otherwise similar. The election algorithm distinguishes a single processor from all other processors. The election algorithm requires O(log n) bits of memory in each processor and has communication complexity of O(n • m+n²log n) bits. In the traversal algorithm one node initiates a token which visits all the nodes of the network and returns to the initiator. The traversal algorithm is derived from the election algorithm. It achieves the same communication complexity and uses only O(1) bits of memory in each processor.

References

[1]

J. E. Burns, "A Formal Model for Message Passing systems," 91, Indiana Univ., Bloomington (May 1980).

[2]

Danny Dolev, Maria Klawe, and Michael Rodeh, "An O(n log n) Unidirectional Algorithm for Extrema Finding in a Circle," Journal of Algorithm3, pp.245-260 (1982).

[3]

Greg N. Frederickson and Nancy A. Lynch, "The Impact of Synchronous Communication on the Problem of Electing a Leader in a Ring," (Nov. 83). Detailed Abstract.

[4]

Eli Gafni, Mike Loui, Parsoon Tawiri, Doug West, and Shmuel Zaks, "Lower Bounds on Common Knowledge in Distributed Algorithms, with Applications," Preprint, Univ. of Illinois (January 1984).

[5]

Eli Gafni and Willard Korfhage, "Election on A Unidirectional Eulerian Graph,", UCLA Computer Science Department (March 1984). Preprint.

[6]

Robert G. Gallager, "A Shortest Path Routing Algorithm with Automatic Resynch,", M.I.T. (March 1976). Unpublished note.

[7]

Robert G. Gallager, "Finding a Leader in a Network with O(N log N) Messages,", M.I.T. (1977). Unpublished Note.

[8]

Robert G. Gallager, Pierre A. Humblet, and P. M. Spira, "A Distributed Algorithm for Minimum Weight Spanning Trees," ACM Trans. Program. Lang. Syst. 5, pp.66-77 (Jan 1983).

Digital Library

[9]

Pierre A. Humblet, "A Distributed Algorithm for Minimum Weight Directed Spanning Trees," IEEE Trans. Comm.COM-31(6), pp.756-762 (June 1983).

[10]

D. Kozen, "Automata and Planar Graphs," IBM Research Report RC 7604, IBM (April 1979).

[11]

N.A. Lynch and M.J. Fischer, "On describing the behavior and implementation of distributed systems," Theoretical Computer Science13, pp.17-43 (1981).

[12]

J. Misra, "Detecting Termination of Distributed Computations Using Markers," pp. 290-295 in Proceedings Proceedings of the ACM Symp. on Principles of Distributed Computing, Montreal (August 1983). token.

Digital Library

[13]

J. Pachl, E. Korach, and D. Rotem, "A Technique for Proving Lower Bounds for Distributed Election Algorithms," pp. 372-382 in Proceedings Proc. 14th symposium on Theory of Computing (1982).

Digital Library

[14]

Gary L. Peterson, "An O(n log n) Unidirectional Algorithm for the Circular Extrema Problem," ACM Trans. Program. Lang. Syst.4(4), pp.758-762 (October 1982).

Digital Library

[15]

Adrian Segall, "Distributed Network Protocols," IEEE Transactions on Information TheoryIT-29(1) (January 1983).

Digital Library

[16]

H. S. Shank, "Graph Properties Recognition Machines," Mathematical Systems Theory5, pp.45-49 (1971).

[17]

Robert Tarjan, "Depth-First Search and Linear Graph Algorithms," SIAM J. Comput.1, pp.146-160 (1972).

Digital Library

Cited By

Maurer CMaurer C(2021)Leader Election AlgorithmsNonsequential and Distributed Programming with Go10.1007/978-3-658-29782-4_18(381-395)Online publication date: 20-Jan-2021
https://doi.org/10.1007/978-3-658-29782-4_18
Maurer CMaurer C(2019)AuswahlalgorithmenNichtsequentielle und Verteilte Programmierung mit Go10.1007/978-3-658-26290-7_18(401-416)Online publication date: 24-Oct-2019
https://doi.org/10.1007/978-3-658-26290-7_18
Maurer CMaurer C(2018)AuswahlalgorithmenNichtsequentielle und Verteilte Programmierung mit Go10.1007/978-3-658-21153-0_18(389-404)Online publication date: 29-May-2018
https://doi.org/10.1007/978-3-658-21153-0_18
Show More Cited By

Index Terms

Election and traversal in unidirectional networks

Recommendations

Distributed algorithms for election in unidirectional and complete networks (traversal, synchronous, leader, asynchronous, complexity)
Distributed Algorithms for Unidirectional Networks

This paper addresses the question of distributively computing over a strongly connected unidirectional data communication network. In unidirectional networks the existence of a communication link from one node to another does not imply the existence of ...
Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks
PODC '17: Proceedings of the ACM Symposium on Principles of Distributed Computing

We study two fundamental communication primitives: broadcasting and leader election in the classical model of multi-hop radio networks with unknown topology and without collision detection mechanisms. It has been known for almost 20 years that in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '84: Proceedings of the third annual ACM symposium on Principles of distributed computing

August 1984

301 pages

ISBN:0897911431

DOI:10.1145/800222

Copyright © 1984 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
479
Total Downloads

Downloads (Last 12 months)39
Downloads (Last 6 weeks)8

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Maurer CMaurer C(2021)Leader Election AlgorithmsNonsequential and Distributed Programming with Go10.1007/978-3-658-29782-4_18(381-395)Online publication date: 20-Jan-2021
https://doi.org/10.1007/978-3-658-29782-4_18
Maurer CMaurer C(2019)AuswahlalgorithmenNichtsequentielle und Verteilte Programmierung mit Go10.1007/978-3-658-26290-7_18(401-416)Online publication date: 24-Oct-2019
https://doi.org/10.1007/978-3-658-26290-7_18
Maurer CMaurer C(2018)AuswahlalgorithmenNichtsequentielle und Verteilte Programmierung mit Go10.1007/978-3-658-21153-0_18(389-404)Online publication date: 29-May-2018
https://doi.org/10.1007/978-3-658-21153-0_18
EffatParvar MEffatparvar MBemana ADehghan M(2007)Determining a Central Controlling Processor with Fault Tolerant Method in Distributed SystemProceedings of the International Conference on Information Technology10.1109/ITNG.2007.75(658-663)Online publication date: 2-Apr-2007
https://dl.acm.org/doi/10.1109/ITNG.2007.75
Moran S(2006)Message complexity versus space complexity in fault tolerant broadcast protocolsNetworks10.1002/net.323019050319:5(505-519)Online publication date: 11-Oct-2006
https://doi.org/10.1002/net.3230190503
Mattern F(2005)Experience with a new distributed termination detection algorithmDistributed Algorithms10.1007/BFb0019800(127-143)Online publication date: 16-Jun-2005
https://doi.org/10.1007/BFb0019800
Tel G(2005)Directed network protocolsDistributed Algorithms10.1007/BFb0019791(13-29)Online publication date: 16-Jun-2005
https://doi.org/10.1007/BFb0019791
Tel G(2005)Total algorithmsCONCURRENCY 8810.1007/3-540-50403-6_45(277-291)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-50403-6_45
Qi Wu Jing Huang Jingping Bi (2003)Arbitrator-based algorithm for measurement collaboration problem2003 International Conference on Computer Networks and Mobile Computing, 2003. ICCNMC 2003.10.1109/ICCNMC.2003.1243042(166-173)Online publication date: 2003
https://doi.org/10.1109/ICCNMC.2003.1243042
Afek YBremler ASaks M(1997)Self-stabilizing unidirectional network algorithms by power-supplyProceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms10.5555/314161.314193(111-120)Online publication date: 5-Jan-1997
https://dl.acm.org/doi/10.5555/314161.314193
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents