A group membership algorithm with a practical specification
- Creators
- Franceschetti, Martin
-
Bruck, Jehoshua
Abstract
Presents a solvable specification and gives an algorithm for the group membership problem in asynchronous systems with crash failures. Our specification requires processes to maintain a consistent history in their sequences of views. This allows processes to order failures and recoveries in time and simplifies the programming of high level applications. Previous work has proven that the group membership problem cannot be solved in asynchronous systems with crash failures. We circumvent this impossibility result building a weaker, yet nontrivial specification. We show that our solution is an improvement upon previous attempts to solve this problem using a weaker specification. We also relate our solution to other methods and give a classification of progress properties that can be achieved under different models.
Additional Information
© Copyright 2001 IEEE. Reprinted with permission. Manuscript received 19 Oct. 1999; revised 13 Nov. 2000; accepted 13 Mar. 2001. The authors would like to thank Professor A.J. Martin and his student Robert Southworth, who helped formalize the problem and gave suggestions on how to specify the code using CSP; Michael Gibson, who read a previous version of the manuscript and made useful comments to improve the presentation, and all the anonymous referees for their constructive criticism. Extra thanks are due to the anonymous referee who pointed out an error in a previous version of the paper that allowed us to simplify the algorithm, and to Matthew Cook, for reviewing the final version of the manuscript. This work was supported in part by the US National Science Foundation Young Investigator Award CCR-9457811, by the Sloan Research Fellowship, by an IBM Partnership Award by Defense Advanced Research Projects Agency through an agreement with the NASA Office of Space Access and Technology, and by the Caltech Lee Center for Advanced Networking.Files
| Name | Size | Download all |
|---|---|---|
|
md5:bbd02d6f52366cd67d3e33b0e9e1404e
|
248.0 kB | Preview Download |
Additional details
- Eprint ID
- 5410
- Resolver ID
- CaltechAUTHORS:FRAieeetpds01
- Created
-
2006-10-16Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field