Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10329448 | Electronic Notes in Theoretical Computer Science | 2005 | 16 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Wan Fokkink, Jun Pang,