SRI Logo
About Us|R and D Divisions|Careers|Newsroom|Contact Us|SRI Home
     
  SRI Logo

Low-Overhead Time-Triggered Group Membership
 by Dr. Patrick Lincoln, Dr. John Rushby & Shmuel Katz.

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.


Abstract
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.
BibTEX Entry
@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}
}
Files
 













 

About Us  |  R&D Divisions  |  Careers  |  Newsroom  |  Contact Us
© 2017 SRI International 333 Ravenswood Avenue, Menlo Park, CA 94025-3493
SRI International is an independent, nonprofit corporation. Privacy policy