article

Free access

An improved algorithm for decentralized extrema-finding in circular configurations of processes

Authors:

Ernest Chang,

Rosemary RobertsAuthors Info & Claims

Communications of the ACM, Volume 22, Issue 5

Pages 281 - 283

https://doi.org/10.1145/359104.359108

Published: 01 May 1979 Publication History

PDF eReader

Abstract

This note presents an improvement to LeLann's algorithm for finding the largest (or smallest) of a set of uniquely numbered processes arranged in a circle, in which no central controller exists and the number of processes is not known a priori. This decentralized algorithm uses a technique of selective message extinction in order to achieve an average number of message passes of order (n log n) rather than O(n²).

Reference

[1]

LeLann, G. Distributed systems-Towards a formal approach. Information Processing 77, North-Holland Pub. Co., Amsterdam, pp. 155-160.

Google Scholar

Cited By

View all

Hinrichsen JJacobs JKrebbers R(2024)Multris: Functional Verification of Multiparty Message Passing in Separation LogicProceedings of the ACM on Programming Languages10.1145/36897628:OOPSLA2(1446-1474)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689762
Frei FGelles RGhazy ANolin AKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Content-Oblivious Leader Election on RingsProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662785(549-552)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662785
Elad NPadon OShoham S(2024)An Infinite Needle in a Finite Haystack: Finding Infinite Counter-Models in Deductive VerificationProceedings of the ACM on Programming Languages10.1145/36328758:POPL(970-1000)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632875
Show More Cited By

Recommendations

On an improved algorithm for decentralized extrema finding in circular configurations of processors

This note presents a more efficient algorithm for finding the largest element in a circular list of processors when messages can be passed in either direction. It passes 2N*floor(lg N) + 3N messages in the worst case, compared to Chang and Roberts' N(N +...
Decentralized extrema-finding in circular configurations of processors

This note presents an efficient algorithm, requiring O(n log n) message passes, for finding the largest (or smallest) of a set of n uniquely numbered processors arranged in a circle, in which no central controller exists and the number of processors is ...
Synchronized Distributed Termination

An efficient decentralized algorithm for synchronized termination of a distributed computation is presented. It is assumed that distributed processes are connected via unidirectional channels into a strongly connected network, in which no central ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 22, Issue 5

May 1979

43 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359104

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1979

Published in CACM Volume 22, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

272
Total Citations
View Citations
2,753
Total Downloads

Downloads (Last 12 months)424
Downloads (Last 6 weeks)30

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hinrichsen JJacobs JKrebbers R(2024)Multris: Functional Verification of Multiparty Message Passing in Separation LogicProceedings of the ACM on Programming Languages10.1145/36897628:OOPSLA2(1446-1474)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689762
Frei FGelles RGhazy ANolin AKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Content-Oblivious Leader Election on RingsProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662785(549-552)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662785
Elad NPadon OShoham S(2024)An Infinite Needle in a Finite Haystack: Finding Infinite Counter-Models in Deductive VerificationProceedings of the ACM on Programming Languages10.1145/36328758:POPL(970-1000)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632875
Hong CLin A(2024)Regular Abstractions for Array SystemsProceedings of the ACM on Programming Languages10.1145/36328648:POPL(638-666)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632864
Alkohali EAlgabri MAbdullah M(2024)Improving the Performance of Bully Algorithm for Leader Election in Distributed Systems2024 1st International Conference on Emerging Technologies for Dependable Internet of Things (ICETI)10.1109/ICETI63946.2024.10777233(1-7)Online publication date: 25-Nov-2024
https://doi.org/10.1109/ICETI63946.2024.10777233
Doose DBrunel J(2024)Simple LTL Model Checking on Finite and Infinite Traces over Concrete DomainsFormal Methods and Software Engineering10.1007/978-981-96-0617-7_21(375-390)Online publication date: 29-Nov-2024
https://doi.org/10.1007/978-981-96-0617-7_21
Mora FDesai APolgreen ESeshia S(2023)Message Chains for Distributed System VerificationProceedings of the ACM on Programming Languages10.1145/36228767:OOPSLA2(2224-2250)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622876
Lin SManerkar YLohstroh MPolgreen EYu SJerad CLee ESeshia S(2023)Towards Building Verifiable CPS using Lingua FrancaACM Transactions on Embedded Computing Systems10.1145/360913422:5s(1-24)Online publication date: 31-Oct-2023
https://dl.acm.org/doi/10.1145/3609134
Redmond PKuper LMcDonell TVazou N(2023)An Exceptional Actor System (Functional Pearl)Proceedings of the 16th ACM SIGPLAN International Haskell Symposium10.1145/3609026.3609728(32-43)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3609026.3609728
Pick LDesai AGupta A(2023)Psym: Efficient Symbolic Exploration of Distributed SystemsProceedings of the ACM on Programming Languages10.1145/35912477:PLDI(660-685)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591247
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Abstract

Reference

Cited By

Recommendations

On an improved algorithm for decentralized extrema finding in circular configurations of processors

Decentralized extrema-finding in circular configurations of processors

Synchronized Distributed Termination

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations