Leader Election in Anonymous Rings: Franklin Goes Probabilistic


Share/Save/Bookmark

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
645kB
[img]
Preview
PDF
416kB
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
Faculty:
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
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 250959