We present a probabilistic leader election algorithm for anonymous, bidirectional, asynchronous rings. It is based on an algorithm from Franklin, augmented with random identity selection, hop counters to detect identity clashes, and round numbers modulo 2. As a result, the algorithm is finite-state, so that various model checking techniques can be employed to verify its correctness, that is, eventually a unique leader is elected with probability one. We also sketch a formal correctness proof of the algorithm for rings with arbitrary size.
Additional Metadata
THEME Software (theme 1)
Publisher IFIP
Editor G. Ausiello
Conference IFIP International Conference on Theoretical Computer Science
Citation
Bakhshi, R, Fokkink, W.J, Pang, J, & van de Pol, J.C. (2008). Leader election in anonymous rings: Franklin goes probabilistic. In G Ausiello (Ed.), Proc. 5th Conference on Theoretical Computer Science (algorithms track) (pp. 57–72). IFIP.