CaltechAUTHORS
  A Caltech Library Service

A group membership algorithm with a practical specification

Franceschetti, Martin and Bruck, Jehoshua (2001) A group membership algorithm with a practical specification. IEEE Transactions on Parallel and Distributed Systems, 12 (11). pp. 1190-1200. ISSN 1045-9219. https://resolver.caltech.edu/CaltechAUTHORS:FRAieeetpds01

[img]
Preview
PDF
See Usage Policy.

242Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:FRAieeetpds01

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.


Item Type:Article
ORCID:
AuthorORCID
Bruck, Jehoshua0000-0001-8474-0812
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.
Subject Keywords:Distributed agreement algorithms, group membership, asynchronous systems
Issue or Number:11
Record Number:CaltechAUTHORS:FRAieeetpds01
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:FRAieeetpds01
Alternative URL:http://dx.doi.org/10.1109/71.969128
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5410
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:16 Oct 2006
Last Modified:22 Nov 2019 09:58

Repository Staff Only: item control page