article

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

Authors:

Yehuda Afek,

Eli GafniAuthors Info & Claims

SIAM Journal on Computing, Volume 20, Issue 2

Pages 376 - 394

https://doi.org/10.1137/0220023

Published: 01 March 1991 Publication History

Abstract

No abstract available.

Cited By

View all

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 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
Show More Cited By

Index Terms

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

Recommendations

Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks
MFCS '00: Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science

We consider the problem of leader election in asynchronous oriented N-node complete networks. We present a leader election algorithm with O(N) message and O(log logN) time complexity. The message complexity is optimal and the time complexity is the best ...
Globally Asynchronous, Locally Synchronous Circuits: Overview and Outlook

For more than 20 years, significant research effort was concentrated on globally asynchronous, locally synchronous (GALS) design methodologies. But despite several successful implementations, GALS has had little impact on industry products. This article ...
Synchronous vs. asynchronous unison
SSS'05: Proceedings of the 7th international conference on Self-Stabilizing Systems

This paper considers the self-stabilizing unison problem. The contribution of this paper is threefold. First, we establish that when any self-stabilizing asynchronous unison protocol runs in synchronous systems, it converges to synchronous unison if the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIAM Journal on Computing Volume 20, Issue 2

April 1990

195 pages

ISSN:0097-5397

Editor:
A. Yao

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 March 1991

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

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 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
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
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
Kutten SPandurangan GPeleg DRobinson PTrehan A(2015)On the Complexity of Universal Leader ElectionJournal of the ACM10.1145/269944062:1(1-27)Online publication date: 2-Mar-2015
https://dl.acm.org/doi/10.1145/2699440
Kutten SPandurangan GPeleg DRobinson PTrehan A(2015)Sublinear bounds for randomized leader electionTheoretical Computer Science10.1016/j.tcs.2014.02.009561:PB(134-143)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.02.009
Kutten SPandurangan GPeleg DRobinson PTrehan AFatourou PTaubenfeld G(2013)On the complexity of universal leader electionProceedings of the 2013 ACM symposium on Principles of distributed computing10.1145/2484239.2484274(100-109)Online publication date: 22-Jul-2013
https://dl.acm.org/doi/10.1145/2484239.2484274
Das SKutten SYifrach A(2006)Improved distributed exploration of anonymous networksProceedings of the 8th international conference on Distributed Computing and Networking10.1007/11947950_34(306-318)Online publication date: 27-Dec-2006
https://dl.acm.org/doi/10.1007/11947950_34
Show More Cited By

View Options

View options

Login options

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

Abstract

Cited By

Index Terms

Recommendations

Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks

Globally Asynchronous, Locally Synchronous Circuits: Overview and Outlook

Synchronous vs. asynchronous unison

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations