Leader Election in Anonymous Rings: Franklin Goes Probabilistic


Bakhshi, Rena and Fokkink, Wan and Pang, Jun and Pol, Jaco van de (2008) Leader Election in Anonymous Rings: Franklin Goes Probabilistic. In: Fifth IFIP International Conference On Theoretical Computer Science, 8-10 September 2008, Milano, Italy (pp. pp. 57-72).

[img] PDF
Restricted to UT campus only
: Request a copy
Abstract: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.
Item Type:Conference or Workshop Item
Copyright:© 2008 Springer
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/62250
Official URL:http://dx.doi.org/10.1007/978-0-387-09680-3_4
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 250959