Simplifying Itai-Rodeh Leader Election for Anonymous Rings

W.J. Fokkink, J. Pang

Research output: Contribution to JournalArticleAcademicpeer-review

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 languageEnglish
Pages (from-to)53-68
JournalElectronic Notes in Theoretical Computer Science
Volume128
DOIs
Publication statusPublished - 2005

Bibliographical note

DBLP:journals/entcs/FokkinkP05
Proceedings title: Proceedings of the Fouth International Workshop on Automated Verification of Critical Systems (AVoCS 2004)
Publisher: Elsevier

Fingerprint

Dive into the research topics of 'Simplifying Itai-Rodeh Leader Election for Anonymous Rings'. Together they form a unique fingerprint.

Cite this