Symmetry breaking in distributed networks

DOI10.1016/0890-5401(90)90004-2zbMath0705.68020MaRDI QIDQ918187

Alon Itai, Michael Rodeh

Publication date: 1990

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(90)90004-2

zbMATH Keywords

distributed networks; electing a leader; finding the size of the ring

Mathematics Subject Classification ID

68M10: Network design and communication in computer systems

68W15: Distributed algorithms

Related Items

Minimal counterexamples for linear-time probabilistic verification, Message terminating algorithms for anonymous rings of unknown size, A linear process-algebraic format with data for probabilistic automata, Cost distribution of the Chang-Roberts leader election algorithm and related problems, Randomized function evaluation on a ring, Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition, On the cost of uniform protocols whose memory consumption is adaptive to interval contention, Fast leader election in anonymous rings with bounded expected delay, Asymptotic analysis of a leader election algorithm, Analysis of Fully Distributed Splitting and Naming Probabilistic Procedures and Applications

Cites Work

• Unnamed Item
• Unnamed Item
• On the existence of symmetric algorithms to find leaders in networks of communicating sequential processes
• On the bit complexity of distributed computations in a ring with a leader
• The choice coordination problem
• Decentralized extrema-finding in circular configurations of processors
• An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• An improved algorithm for decentralized extrema-finding in circular configurations of processes
• Concurrent Processes and Their Syntax
• Probabilistic automata