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

    9 Citations (Scopus)
    45 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
    Bakhshi, Rena ; Fokkink, Wan ; Pang, Jun ; van de Pol, Jan Cornelis. / Leader Election in Anonymous Rings: Franklin Goes Probabilistic. Fifth IFIP International Conference On Theoretical Computer Science. editor / G. Ausiello ; J. Karhumäki ; G. Mauri ; L. Ong. Boston : Springer, 2008. pp. 57-72 (IFIP International Federation for Information Processing; 1).
    @inproceedings{91e228f1d72f40aa908631c9029f2ac2,
    title = "Leader Election in Anonymous Rings: Franklin Goes Probabilistic",
    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.",
    keywords = "EWI-12292, CR-C.2.4, METIS-250959, FMT-MC: MODEL CHECKING, IR-62250, CR-I.1.2",
    author = "Rena Bakhshi and Wan Fokkink and Jun Pang and {van de Pol}, {Jan Cornelis}",
    note = "10.1007/978-0-387-09680-3_4",
    year = "2008",
    month = "7",
    day = "22",
    doi = "10.1007/978-0-387-09680-3_4",
    language = "Undefined",
    isbn = "978-0-387-09679-7",
    series = "IFIP International Federation for Information Processing",
    publisher = "Springer",
    number = "1",
    pages = "57--72",
    editor = "G. Ausiello and J. Karhum{\"a}ki and G. Mauri and L. Ong",
    booktitle = "Fifth IFIP International Conference On Theoretical Computer Science",

    }

    Bakhshi, R, Fokkink, W, Pang, J & van de Pol, JC 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., 10.1007/978-0-387-09680-3_4, IFIP International Federation for Information Processing, no. 1, vol. 273/2008, Springer, Boston, pp. 57-72. https://doi.org/10.1007/978-0-387-09680-3_4

    Leader Election in Anonymous Rings: Franklin Goes Probabilistic. / Bakhshi, Rena; Fokkink, Wan; Pang, Jun; van de Pol, Jan Cornelis.

    Fifth IFIP International Conference On Theoretical Computer Science. ed. / G. Ausiello; J. Karhumäki; G. Mauri; L. Ong. Boston : Springer, 2008. p. 57-72 10.1007/978-0-387-09680-3_4 (IFIP International Federation for Information Processing; Vol. 273/2008, No. 1).

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

    TY - GEN

    T1 - Leader Election in Anonymous Rings: Franklin Goes Probabilistic

    AU - Bakhshi, Rena

    AU - Fokkink, Wan

    AU - Pang, Jun

    AU - van de Pol, Jan Cornelis

    N1 - 10.1007/978-0-387-09680-3_4

    PY - 2008/7/22

    Y1 - 2008/7/22

    N2 - 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.

    AB - 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.

    KW - EWI-12292

    KW - CR-C.2.4

    KW - METIS-250959

    KW - FMT-MC: MODEL CHECKING

    KW - IR-62250

    KW - CR-I.1.2

    U2 - 10.1007/978-0-387-09680-3_4

    DO - 10.1007/978-0-387-09680-3_4

    M3 - Conference contribution

    SN - 978-0-387-09679-7

    T3 - IFIP International Federation for Information Processing

    SP - 57

    EP - 72

    BT - Fifth IFIP International Conference On Theoretical Computer Science

    A2 - Ausiello, G.

    A2 - Karhumäki, J.

    A2 - Mauri, G.

    A2 - Ong, L.

    PB - Springer

    CY - Boston

    ER -

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