Abstract
We present two probabilistic leader election algorithms for anonymous unidirectional rings with FIFO channels, based on an algorithm from Itai and Rodeh [A. Itai and M. Rodeh. Symmetry breaking in distributive networks. In Proc. FOCS'81, pp. 150-158. IEEE Computer Society, 1981]. In contrast to the Itai-Rodeh algorithm, our algorithms are finite-state. So they can be analyzed using explicit state space exploration; we used the probabilistic model checker PRISM to verify, for rings up to size four, that eventually a unique leader is elected with probability one. © 2005 Elsevier B.V. All rights reserved.
Original language | English |
---|---|
Pages (from-to) | 53-68 |
Journal | Electronic Notes in Theoretical Computer Science |
Volume | 128 |
DOIs | |
Publication status | Published - 2005 |
Bibliographical note
DBLP:journals/entcs/FokkinkP05Proceedings title: Proceedings of the Fouth International Workshop on Automated Verification of Critical Systems (AVoCS 2004)
Publisher: Elsevier