Electing a leader in a synchronous ring

DOI10.1145/7531.7919zbMath0631.68024OpenAlexW2093606353MaRDI QIDQ3768383

Greg N. Frederickson, Nancy A. Lynch

Publication date: 1987

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://docs.lib.purdue.edu/cstech/434

zbMATH Keywords

lower boundsring networksdistributed algorithmsRamsey's theoremleader electionsynchronous computationcomparison algorithms

Mathematics Subject Classification ID

Theory of operating systems (68N25)

Related Items (40)

The bit complexity of the predecessor problem ⋮ Improved bounds for electing a leader in a synchronous ring ⋮ Some lower bound results for decentralized extrema-finding in rings of processors ⋮ An improved election algorithm in chordal ring networks ⋮ A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors ⋮ Distributed tree comparison with nodes of limited memory ⋮ Computing with infinitely many processes ⋮ Four shades of deterministic leader election in anonymous networks ⋮ Fast leader election in anonymous rings with bounded expected delay ⋮ Improved Tradeoffs for Leader Election ⋮ Leader election in well-connected graphs ⋮ Randomized leader election ⋮ Renaming in synchronous message passing systems with Byzantine failures ⋮ Bit-optimal election in synchronous rings ⋮ On the complexity of global computation in the presence of link failures: the general case ⋮ Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links ⋮ Hundreds of impossibility results for distributed computing ⋮ A simple characterization of asynchronous computations ⋮ How much memory is needed for leader election ⋮ Knowledge, level of symmetry, and time of leader election ⋮ Anonymous wireless rings ⋮ Leader election for anonymous asynchronous agents in arbitrary networks ⋮ Impact of knowledge on election time in anonymous networks ⋮ Move-optimal gossiping among mobile agents ⋮ Strong order-preserving renaming in the synchronous message passing model ⋮ Unnamed Item ⋮ On the Microscopic View of Time and Messages ⋮ Topology recognition and leader election in colored networks ⋮ Message lower bounds via efficient network synchronization ⋮ Efficient elections in chordal ring networks ⋮ Trading Bit, Message, and Time Complexity of Distributed Algorithms ⋮ Optimal lower bounds for some distributed algorithms for a complete network of processors ⋮ Distance-Preserving Subgraphs of Interval Graphs ⋮ Wait-free implementations in message-passing systems ⋮ Rapid convergence of a local load balancing algorithm for asynchronous rings ⋮ On the Complexity of Universal Leader Election ⋮ New lower bound techniques for distributed leader finding and other problems on rings of processors ⋮ Distributed communication complexity of spanning tree construction ⋮ Electing a leader in a ring with link failures ⋮ Anonymous meeting in networks

This page was built for publication: Electing a leader in a synchronous ring