Symmetry breaking in distributed networks

Summary

Probabilistic algorithms are proposed to overcome the difficulty of designing a ring of n processors such that they will be able to choose a leader by sending messages along the ring, if the processors are indistinguishable.

Keywords

Correctness, Computer science, Ring (chemistry), Probabilistic logic, State (computer science)

References

Two lower bounds in asynchronous distributed computationPavol Ďuriš, Zvi Galil — 1987
An O(n log n) Unidirectional Distributed Algorithm for Extrema Finding in a CircleDanny Dolev, Maria Klawe, Michael Rodeh — 1982
Concurrent Processes and Their SyntaxGeorge Milne, Robin Milner — 1979
On the bit complexity of distributed computations in a ring with a leaderYishay Mansour, Shmuel Zaks — 1986
An improved algorithm for decentralized extrema-finding in circular configurations of processesErnest Chang, Rosemary Roberts — 1979
An O(nlog n) Unidirectional Algorithm for the Circular Extrema ProblemGary L. Peterson — 1982
On an improved algorithm for decentralized extrema finding in circular configurations of processorsRandolph Franklin — 1982
A Lower Bound for Probabilistic Distributed AlgorithmsJan Pachl — 1987
Probabilistic solitude verification on a ringKarl Abrahamson, Andréw Adler, Lisa Highám — 1986
A compositional approach to superimpositionLuc Bougé, Nissim Francez — 1988
Decentralized Extrema- Finding in Circular Configurations of ProcessorsR. Stockton Gaines — 1980
A New Approach to Detection of Locally Indicative StabilityN. Shavit, N. Francez — 1986
FairnessL. Priese — 1988

Cited by

SMT-based Counterexample Generation for Markov ChainsBettina Braitling, Ralf Wimmer, Bernd Becker — 2011
Faults and fault-tolerance in distributed computing systems: the election problemByungho Yi — 1994
A comparison of toolsH. A. Oldenkamp — 2007
Bisimulation minimisation and probabilistic model checkingTim Kemna — 2006
Probabilistic model checking : a comparison of toolsH. A. Oldenkamp — 2007
Distributed AlgorithmsWan Fokkink — 2013
Design and analysis of distributed algorithmsNicola Santoro — 2006
CEGAR for compositional analysis of qualitative properties in Markov decision processesKrishnendu Chatterjee, Martin Chmelík, Przemysław Daca — 2015
Exact Quantum Algorithms for the Leader Election ProblemSeiichiro Tani, Hirotada Kobayashi, Keiji Matsumoto — 2005
Simplifying Itai-Rodeh Leader Election for Anonymous RingsWan Fokkink, Jun Pang — 2005
Principles of model checkingChristel Baier, Joost-Pieter Katoen — 2008
Computing on Anonymous Quantum NetworkHirotada Kobayashi, Keiji Matsumoto, Seiichiro Tani — 2010
Variations on Itai-Rodeh Leader Election for Anonymous Rings and their Analysis in PRISMJun Pang, Wan Fokkink — 2006
Model checking nondeterministic and randomly timed systemsMartin R. Neuhäußer — 2010
Diagnosis, Synthesis and Analysis of Probabilistic ModelsTingting Han — 2009
The computational power of the W And GHZ StatesEllie D’Hondt, Prakash Panangaden — 2004
Randomized fault-detecting leader election in a bi-directional ringN.R. Wagner — 1990
Asynchronous Bounded Expected Delay NetworksRena Bakhshi, Jörg Endrullis, Wan Fokkink — 2010
Model checking Markov chains : techniques and toolsIvan S. Zapreev — 2008
Counterexamples in probabilistic verificationNils Jansen, Erika Ábrahám, Bernd Becker — 2015

Related papers

Program Repair by Stepwise Correctness EnhancementNafi Diallo, Wided Ghardallou, Ali Mili — 2016
A Fault-Localization Approach Based on the Coincidental Correctness ProbabilityXiaoli Zhou, Hanfei Wang, Jianhua Zhao — 2015
“So my program doesn’t run!” Definition, origins, and practical expressions of students’ (mis)conceptions of correctnessYifat Ben‐David Kolikant, M. Mussai — 2008
On the correctness of problem solving in ancient mathematical procedure textsMário Bacelar Valente — 2021
An Innovative Framework for Coincidental Correctness Impacting on Fault LocalizationHeling Cao, Lei Li, Yigui Sun — 2022
Correctness at Evaluation of the Output and Methods for it ImprovementParaskeva Dimitrova — 1998