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.
IFIP
G. Ausiello
IFIP International Conference on Theoretical Computer Science
Software Analysis and Transformation

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.