Variations on Itai-Rodeh Leader Election for Anonymous Rings and their Analysis in PRISM
Jun Pang, Wan J. Fokkink · Zenodo (CERN European Organization for Nuclear Research) · 2020
Abstract: We present two probabilistic leader election algorithms for anonymous uni-directional rings with FIFO channels, based on an algorithm from Itai and Rodeh [Itai and Rodeh 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 even-tually a unique leader is elected with probability one. Furthermore, we give a manual correctness proof for each algorithm.