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.
|Name||IFIP International Federation for Information Processing|
|Conference||Fifth IFIP International Conference On Theoretical Computer Science|
|Period||8/09/08 → 10/09/08|
|Other||8-10 September 2008|
- FMT-MC: MODEL CHECKING