Simplifying Itai-Rodeh Leader Election for Anonymous Rings

W.J. Fokkink; J. Pang

doi:10.1016/j.entcs.2005.04.004

Simplifying Itai-Rodeh Leader Election for Anonymous Rings

Research output: Contribution to Journal › Article › Academic › peer-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 language	English
Pages (from-to)	53-68
Journal	Electronic Notes in Theoretical Computer Science
Volume	128
DOIs	https://doi.org/10.1016/j.entcs.2005.04.004
Publication status	Published - 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

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1016/j.entcs.2005.04.004

Persistent URL (handle)

Persistent link

Cite this

@article{e3041d400b94434da3afffa5dab0a295,

title = "Simplifying Itai-Rodeh Leader Election for Anonymous Rings",

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. {\textcopyright} 2005 Elsevier B.V. All rights reserved.",

author = "W.J. Fokkink and J. Pang",

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

year = "2005",

doi = "10.1016/j.entcs.2005.04.004",

language = "English",

volume = "128",

pages = "53--68",

journal = "Electronic Notes in Theoretical Computer Science",

issn = "1571-0661",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Simplifying Itai-Rodeh Leader Election for Anonymous Rings

AU - Fokkink, W.J.

AU - Pang, J.

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

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

U2 - 10.1016/j.entcs.2005.04.004

DO - 10.1016/j.entcs.2005.04.004

M3 - Article

SN - 1571-0661

VL - 128

SP - 53

EP - 68

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

ER -

Simplifying Itai-Rodeh Leader Election for Anonymous Rings

Abstract

Bibliographical note

UN SDGs

Access to Document

Persistent URL (handle)

Fingerprint

Cite this