The topology of randomized symmetry-breaking distributed computing

DOI10.1007/s41468-023-00150-9MaRDI QIDQ6645915

Pierre Fraigniaud, Zvi Lotker, Ran Gelles

Publication date: 29 November 2024

Published in: Journal of Applied and Computational Topology (Search for Journal in Brave)

zbMATH Keywords

distributed computingleader electioncorrelated randomnesseventual solvabilityKolmogorov's 0--1 law

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Symmetry breaking in distributed networks
• Elections in anonymous networks
• Calling names on nameless networks
• Election in partially anonymous networks with arbitrary knowledge in message passing systems
• Anonymous networks
• Bit complexity of breaking and achieving symmetry in chains and rings
• Computing on an anonymous ring
• The Bit Complexity of Randomized Leader Election on a Ring
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Generalized FLP impossibility result for t-resilient asynchronous computations
• Wait-free k-set agreement is impossible
• The asynchronous computability theorem for t-resilient tasks
• Distributed computability in Byzantine asynchronous systems
• On the Complexity of Universal Leader Election
• The Topology of Randomized Symmetry-Breaking Distributed Computing

This page was built for publication: The topology of randomized symmetry-breaking distributed computing