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

article

Open access

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

Editor: Susan L. Graham Authors:

S. MoranAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 12, Issue 1

Pages 84 - 101

https://doi.org/10.1145/77606.77610

Published: 03 January 1990 Publication History

Abstract

A general, modular technique for designing efficient leader finding algorithms in distributed, asynchronous networks is developed. This technique reduces the problem of efficient leader finding to a simpler problem of efficient serial traversing of the corresponding network. The message complexity of the resulting leader finding algorithms is bounded by [f(n) + n)(log₂k + 1) (or (f(m) + n)(log₂k + 1)], where n is the number of nodes in the network [m is the number of edges in the network], k is the number of nodes that start the algorithm, and f (n) [f(m)] is the message complexity of traversing the nodes [edges] of the network. The time complexity of these algorithms may be as large as their message complexity. This technique does not require that the FIFO discipline is obeyed by the links. The local memory needed for each node, besides the memory needed for the traversal algorithm, is logarithmic in the maximal identity of a node in the network. This result achieves in a unified way the best known upper bounds on the message complexity of leader finding algorithms for circular, complete, and general networks. It is also shown to be applicable to other classes of networks, and in some cases the message complexity of the resulting algorithms is better by a constant factor than that of previously known algorithms.

References

[1]

AFEK, Y., AND GAFNI, A. Time and message bounds for election in synchronous and asynchronous complete networks. In Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing (Minaki, Canada, Aug. 1985), pp. 186-195.

[2]

BURNS, J.E. A formal model for message passing systems. Tech. Rep. TR-91, Indiana University, Sept. 1980.

[3]

BOUGE, L., AND FRANCEZ, N. A compositional approach to superimposition. In Proceedings of the 15th Annual ACM Symposium on the Principles of Programming Languages (San Diego, Calif., Jan. 1988), pp. 240-249.

[4]

DOLEV, D., KLAWE, M., AND RODEH, M. An O(nlogn) unidirectional distributed algorithm for extrema finding in a circle. J. Algorithms 3 (1982), 245-260.

[5]

EVEN, S. Graph Algorithms. Computer Science Press, 1979.

[6]

FREDRICKSON, C., AND LYNCH, N. The impact of synchronous communication on the problem of electing a leader in a ring. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing (Washington, D.C., 1984), pp. 493-503.

[7]

GAFNI, E., AND AFEK, Y. Election and traversal in unidirectional networks. In Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 1984), pp. 190-198.

[8]

GAFNI, E., AND AFEK, Y. Simple and efficient distributed algorithms for election in complete networks. In Proceedings of the 22nd Annual Allerton Conference on Communication, Control, and Computing (Monticello, Ill., Oct. 1984), pp. 689-698.

[9]

GAFNI, E., AND KORFHAGE, W. Distributed election in unidirectional Eulerian networks. In Proceedings of the 22nd Annual Allerton Conference on Communication, Control, and Computing (Monticello, Ill., Oct. 1984), pp. 699-700.

[10]

GALLAGER, R.G. Choosing a leader in a network. Unpublished memorandum, M.I.T., Cambridge, Mass., 1977.

[11]

GALLAGER, R.G. Finding a leader in networks with O(E) + O(NlogN) messages. Internal Memo., M.I.T., Cambridge, Mass., 1978.

[12]

GALLAGER, R. G., HUMBLET, P. M., AND SPIRA, P.M. A distributed algorithm for minimumweight spanning trees. ACM Trans. Program. Lang. Syst. 5, I (Jan. 1983), 66-77.

[13]

H{RSHBERG, D. S., AND SINCLAIR, J. $. Decentralized extrema-findingin circular configurations of processors. Commun. ACM 23, 11 (Nov. 1980), 627-628.

[14]

HUMBLET, P. Selecting a leader in a clique in O(nlogn) messages. Intern. Memo., Laboratory for Information and Decision Systems, M.I.T., Cambridge, Mass., 1984.

[15]

KORACH, E., AND MARKOVlTZ, M. Algorithm for distributed spanning tree construction in dynamic networks. Tech. Rep. 401, Dept. Computer Science, Technion, Haifa, Israel, Feb. 1986.

[16]

KORACU, E., MORAN, S., AND ZAKS, S. Tight lower and upper bounds for some distributed algorithms for a complete network of processors. In Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 1984), pp. 199-207.

[17]

KORACH, E., ROTEM, D., AND SANTORO, N. A probabilistic algorithm for decentralized extremafinding in a circular configuration of processors. Tech. Rep., University of Waterloo, Ont., Canada, 1981.

[18]

KORACH, E., ROTEM, D., AND SANTORO, N. Distributed algorithms for finding centers and medians in networks. ACM Trans. Program. Lang. Syst. 6, 3 (July 1984), 380-401.

[19]

KUTTEN, S. A unified approach to the efficient construction of distributed leader-findingalgorithms. Presented at the IEEE International Conference on Communication and Energy, Montreal, Canada, Oct. 1984.

[20]

KUTTEN, S. Traversing directed graphs--An upper and lower bound. Internal Memo., 1984.

[21]

LAVALLEE, I., AND ROUCAIROL, G. A fully distributed (minimal) spanning tree algorithm. Inf. Processing Lett. 23 (Aug. 1986), 55-62.

[22]

PACHL, J., KORACH, r., AND ROTEM, D. Lower bounds for distributed maximum-finding algorithms. J. ACM 31, 4 (Oct. 1984), 905-918.

[23]

PETERSON, G.L. An O(nlogn) unidirectional algorithm for the circular extrema problem. ACM{ Trans. Program. Lang. Syst. 4, 4 (Oct. 1982), 758-762.

[24]

SEGALL, A. Distributed network protocols. IEEE Trans. Inf. Theory IT-29, I (Jan. 1983), 23-35.

[25]

TANENBAUM, A.S. Computer Networks. Prentice-Hall, Englewood Cliffs, N.J., 1981.

[26]

TIWARI, P., AND LOUI, M. C. Simulation of chaotic algorithms by token algorithms. In Distributed Algorithms on Graphs, E. Gafni and N. Santoro, Eds. Carleton University Press, Northfield, Minn., 1986, pp. 145-152.

[27]

VITANYI, P. M.B. Distributed election in an Archimedean ring of processors. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing (Washington, D.C., 1984), pp. 542-547.

Cited By

Kutten SRobinson PTan MZhu XOshman RNolin AHalldorsson MBalliu A(2023)Improved Tradeoffs for Leader ElectionProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594576(355-365)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594576
Kumar MMolla A(2023)On the Message Complexity of Fault-Tolerant Computation: Leader Election and AgreementIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.3239993(1-12)Online publication date: 2023
https://doi.org/10.1109/TPDS.2023.3239993
Kumar MMolla ASivasubramaniam S(2023)Improved Deterministic Leader Election in Diameter-Two NetworksAlgorithms and Complexity10.1007/978-3-031-30448-4_23(323-335)Online publication date: 13-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-30448-4_23
Show More Cited By

Index Terms

Recommendations

Yet Another Modular Technique for Efficient Leader Election
SOFSEM '98: Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics: Theory and Practice of Informatics

In this paper we present a general and still flexible modular technique for the design of efficient leader election algorithms in N-node networks. Our approach can be viewed as a generalization of the previous method introduced by Korach, Kutten and ...
Designing efficient algorithms for distributed systems
Energy-Efficient Distributed Algorithms for Synchronous Networks
Structural Information and Communication Complexity
Abstract
We study the design of energy-efficient algorithms for the LOCAL and CONGEST models. Specifically, as a measure of complexity, we consider the maximum, taken over all the edges, or over all the nodes, of the number of rounds at which an edge, or a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 12, Issue 1

Jan. 1990

141 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/77606

Editor:
Susan L. Graham

Issue’s Table of Contents

Copyright © 1990 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 January 1990

Published in TOPLAS Volume 12, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

64
Total Citations
View Citations
1,216
Total Downloads

Downloads (Last 12 months)102
Downloads (Last 6 weeks)14

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kutten SRobinson PTan MZhu XOshman RNolin AHalldorsson MBalliu A(2023)Improved Tradeoffs for Leader ElectionProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594576(355-365)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594576
Kumar MMolla A(2023)On the Message Complexity of Fault-Tolerant Computation: Leader Election and AgreementIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.3239993(1-12)Online publication date: 2023
https://doi.org/10.1109/TPDS.2023.3239993
Kumar MMolla ASivasubramaniam S(2023)Improved Deterministic Leader Election in Diameter-Two NetworksAlgorithms and Complexity10.1007/978-3-031-30448-4_23(323-335)Online publication date: 13-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-30448-4_23
Kumar MMolla AMiller ACensor-Hillel K(2021)Brief AnnouncementProceedings of the 2021 ACM Symposium on Principles of Distributed Computing10.1145/3465084.3467949(259-262)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3465084.3467949
Srinivasan Skandukoori R(2021)A synod based deterministic and indulgent leader election protocol for asynchronous large groupsInternational Journal of Parallel, Emergent and Distributed Systems10.1080/17445760.2021.187906737:2(220-247)Online publication date: 1-Feb-2021
https://doi.org/10.1080/17445760.2021.1879067
Molla AShur D(2020)Smoothed Analysis of Leader Election in Distributed NetworksStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-64348-5_14(183-198)Online publication date: 18-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64348-5_14
Casteigts AMétivier YRobson JZemmari A(2019)Deterministic Leader Election Takes $$\Theta (D + \log n)$$?(D+logn) Bit RoundsAlgorithmica10.1007/s00453-018-0517-381:5(1901-1920)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s00453-018-0517-3
Chatterjee SPandurangan GRobinson P(2019)The complexity of leader election in diameter-two networksDistributed Computing10.1007/s00446-019-00354-2Online publication date: 21-May-2019
https://doi.org/10.1007/s00446-019-00354-2
Augustine JMolla APandurangan GNewport CKeidar I(2018)Sublinear Message Bounds for Randomized AgreementProceedings of the 2018 ACM Symposium on Principles of Distributed Computing10.1145/3212734.3212751(315-324)Online publication date: 23-Jul-2018
https://dl.acm.org/doi/10.1145/3212734.3212751
Chatterjee SPandurangan GRobinson P(2018)The Complexity of Leader ElectionProceedings of the 19th International Conference on Distributed Computing and Networking10.1145/3154273.3154308(1-10)Online publication date: 4-Jan-2018
https://dl.acm.org/doi/10.1145/3154273.3154308
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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents