Leader Election in Anonymous Rings: Franklin Goes Probabilistic

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

PDF
Restricted to UT campus only: Request a copy
630Kb

Preview

PDF
406Kb

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:	Formal Methods and Tools (FMT)
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

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 250959