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 (29)

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

This page was built for publication: Symmetry breaking in distributed networks