Leader election in anonymous rings: Franklin goes probabilistic
Presented at the IFIP International Conference on Theoretical Computer Science
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 International Conference on Theoretical Computer Science|
|Organisation||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.