Leader Election in Anonymous Rings: Franklin Goes Probabilistic

Rena Bakhshi, Wan Fokkink, Jun Pang, Jan Cornelis van de Pol

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    10 Citations (Scopus)
    144 Downloads (Pure)

    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.
    Original languageUndefined
    Title of host publicationFifth IFIP International Conference On Theoretical Computer Science
    EditorsG. Ausiello, J. Karhumäki, G. Mauri, L. Ong
    Place of PublicationBoston
    PublisherSpringer
    Pages57-72
    Number of pages16
    ISBN (Print)978-0-387-09679-7
    DOIs
    Publication statusPublished - 22 Jul 2008

    Publication series

    NameIFIP International Federation for Information Processing
    PublisherSpringer Verlag
    Number1
    Volume273/2008
    ISSN (Print)1571-5736

    Keywords

    • EWI-12292
    • CR-C.2.4
    • METIS-250959
    • FMT-MC: MODEL CHECKING
    • IR-62250
    • CR-I.1.2

    Cite this

    Bakhshi, R., Fokkink, W., Pang, J., & van de Pol, J. C. (2008). Leader Election in Anonymous Rings: Franklin Goes Probabilistic. In G. Ausiello, J. Karhumäki, G. Mauri, & L. Ong (Eds.), Fifth IFIP International Conference On Theoretical Computer Science (pp. 57-72). [10.1007/978-0-387-09680-3_4] (IFIP International Federation for Information Processing; Vol. 273/2008, No. 1). Boston: Springer. https://doi.org/10.1007/978-0-387-09680-3_4