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)
    154 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
    EventFifth IFIP International Conference On Theoretical Computer Science - Milano, Italy
    Duration: 8 Sep 200810 Sep 2008

    Publication series

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

    Conference

    ConferenceFifth IFIP International Conference On Theoretical Computer Science
    Period8/09/0810/09/08
    Other8-10 September 2008

    Keywords

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

    Cite this