Lecture Notes in Computer Science, Volume 1320.
From 11th International Workshop on Distributed Algorithms (WDAG '97).
Edited by Marios Mavronicolas and Philippas Tsigas.
Springer-Verlag, SaarbrŸcken Germany.
sep }, 1997.
Pages 155–169.

Note: The paper has been updated to correct a bug discovered by N. Shankar on 31 January 1998. The bug was independently discovered by Sadie Creese and Bill Roscoe of Oxford University using the FDR model checker.

A group membership protocol is presented and proven correct for a synchronous time-triggered model of computation with processors in a ring that broadcast in turn. The protocol, derived from one used for critical control functions in automobiles, accepts a very restrictive fault model to achieve low overhead and requires only one bit of membership information piggybacked on regular broadcasts. Given its strong fault model, the protocol guarantees that a faulty processor will be promptly diagnosed and removed from the agreed group of processors, and will also diagnose itself as faulty. The protocol is correct under a fault-arrival assumption that new faults arrive at least n+1 time units apart, when there are n processors. Exploiting this assumption leads to unusual real-time reasoning in the correctness proof.

@INPROCEEDINGS{Katz-etal97,
    AUTHOR = {Shmuel Katz and Pat Lincoln and John Rushby},
    TITLE = {Low-Overhead Time-Triggered Group Membership},
    VOLUME = {1320},
    YEAR = {1997},
    PAGES = {155--169},
    MONTH = {sep \}},
    ADDRESS = {Saarbr\"{u}cken Germany},
    URL = {http://www.csl.sri.com/papers/wdag97/},
    SERIES = {Lecture Notes in Computer Science},
    BOOKTITLE = {11th International Workshop on Distributed Algorithms (WDAG '97)},
    PUBLISHER = {Springer-Verlag},
    EDITOR = {Marios Mavronicolas and Philippas Tsigas}
}

• wdag97.dvi
• wdag97.pdf
• wdag97.ps