Symmetry breaking in distributed networks

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

Michael Rodeh, Alon Itai

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 networkselecting a leaderfinding the size of the ring

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed algorithms (68W15)

Related Items

Synthesizing optimal bias in randomized self-stabilization, Strictly in-place algorithms for permuting and inverting permutations, Model Checking Probabilistic Systems, Cost distribution of the Chang-Roberts leader election algorithm and related problems, Value iteration for simple stochastic games: stopping criterion and learning algorithm, Minimal counterexamples for linear-time probabilistic verification, Counting in one-hop beeping networks, A predicate transformer for choreographies. Computing preconditions in choreographic programming, Fast leader election in anonymous rings with bounded expected delay, Randomized function evaluation on a ring, Naming symmetric processes using shared variables, Hundreds of impossibility results for distributed computing, Message terminating algorithms for anonymous rings of unknown size, Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds, Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring, Unnamed Item, Asymptotic analysis of a leader election algorithm, On the Microscopic View of Time and Messages, Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition, Fast protocols for leader election and spanning tree construction in a distributed network, On the cost of uniform protocols whose memory consumption is adaptive to interval contention, An Inductive Technique for Parameterised Model Checking of Degenerative Distributed Randomised Protocols, CEGAR for compositional analysis of qualitative properties in Markov decision processes, The Synergy of Finite State Machines, A linear process-algebraic format with data for probabilistic automata, Analysis of fully distributed splitting and naming probabilistic procedures and applications, Analysis of Fully Distributed Splitting and Naming Probabilistic Procedures and Applications, Distributed communication complexity of spanning tree construction, Verification of multiplayer stochastic games via abstract dependency graphs

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