Article

Free access

On the impossibility of group membership

Authors:

Tushar Deepak Chandra,

Vassos Hadzilacos,

Sam Toueg,

Bernadette Charron-BostAuthors Info & Claims

PODC '96: Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing

Pages 322 - 330

https://doi.org/10.1145/248052.248120

Published: 01 May 1996 Publication History

PDF eReader

References

[1]

Emmanueile Anceaume, Bernadette Charron-Bost, Pascale Minet, and Sam Toueg. On the formal specification of group membership services. Technical Report 95-1534, Computer Science Department, Cornell University, Ithaca, New York 14853, August 1995.

Google Scholar

[2]

Yair Amir, Danny Dolev, Shlomo Kramer, and Dalia Malki. Membership algorithms for multicast communication groups. In Proceedings of the 6th International Workshop on Distributed Algorithms (WDAG- 6), (LCNS, 6~7), pages 292-312, November 1992.

Digital Library

Google Scholar

[3]

Ozalp Babao~,lu, Renzo Davoli, Luigi- Alberto Giachini, and Mary Gray Baker. RE~A CS: a communications infrastructure for constructing reliable applications in large-scale distributed systems. BROADCAST Project deliverable report, 1994. Department of Computing Science, University of Newcastle upon Tyne, UK.

Google Scholar

[4]

()zalp Babao~lu, Renzo Davoli, and Alberto Montresor. Failure detectots, group membership and viewsynchronous communication in partitionable asynchronous systems (preliminary version). Technical Report UBLCS-95-18, Department of Compurer Science, University of Bologna, Bologna, Italy, November 1995.

Digital Library

Google Scholar

[5]

Michael Ben-Or. Another advanrage of free choice: Completely asynchronous agreement protocols. In Proceedings of the Second A CM Symposium on Principles of Distributed Computing, pages 27-30, August 1983.

Digital Library

Google Scholar

[6]

Kenneth P. Birman and Thomas A. Joseph. Exploiting virtual synchrony in distributed systems. In Proceedings of the 11th Annual Symposium Opersting Systems Principles, pages 123- 138, Austin, TX, November 1987.

Digital Library

Google Scholar

[7]

/}zalp Babao~,lu and Andr~ Schiper. On group communication in large scale distributed systems. In Proceedings of the A CM SIGOPS European Workshop, Dagstuhl, Germany, September 1994.

Digital Library

Google Scholar

[8]

Gabriel Bracha and Sam Toueg. Resilient consensus protocols. In Proceedings of the Second A CM Symposium on Principles of Distributed Computing, pages 12-26, August 1983. An extended and revised version appeared as "Asynchronous consensus and broadcast protocols" in the Journal of the A CM, 32(4):824-840, October 1985.

Digital Library

Google Scholar

[9]

Benny Chor and Cynthia Dwork. Randomization in Byzantine Agreement. Advances in Computer Research (JAI Press Inc.), 4:443-497, 1989.

Google Scholar

[10]

Flaviu Cristian. Reaching agreement on processor group membership in synchronous distributed systems. Distributed Computing, 4(4):175-187, April 1991.

Digital Library

Google Scholar

[11]

Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for asynchronous systems. In Proceedings of the Tenth A CM Symposium on Principles of Distributed Computing, pages 325-340. ACM Press, August 1991. To appear in the Journal of the A CM. An extended and revised version is also available by anonymous ftp from ftp. ca. coraell, edu in pub/chandra/fda, ps.

Digital Library

Google Scholar

[12]

Danny Dolev, Shlomo Kramer, and Dalia Malki. Early delivery totally ordered multicast in asynchronous environment. In Proceedings of the ~3th Annual International Symposium on Fault- Tolerant Computing, pages 544- 553, Toulouse, June 1993.

Crossref

Google Scholar

[13]

Danny Dolev, Dalia Malki, and Ray Strong. An asynchronous membership protocol that tolerates partitions. Technical Report CS94-6, Institute of Computer Science, The Hebrew University of jerusalem, 1994.

Google Scholar

[14]

Danny Dolev, Dalia Malki, and Ray Strong. A framework for partitionable membership service. Technical Report CS95-4, Institute of Computer Science, The Hebrew University of Jerusalem, 1995.

Google Scholar

[15]

Danny Dolev, Dalia Malki, and Ray Strong. A framework for partitionable membership service. In Proceedings of the 15th Annual A CM Symposium on Principles of Distributed Computing, Philadephia, PA, 1996.

Digital Library

Google Scholar

[16]

Paul D. Ezhilchelvan, Raimundo A. Mac~do, and Santosh K. Shrivastava. Newtop: a fault-tolerant group communication protocol. In Proceedings of the 15ih International Conference on Distributed Computing $ystem~, V~ncouver, BC, Canada, June 1995.

Digital Library

Google Scholar

[17]

Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the A CM, 32(2):374-382, April 1985

Digital Library

Google Scholar

[18]

Matti A. Hiltunen and Richard D. Schlichting. Properties of membership services. In Proceedings of the ~nd International Symposium on Autonomous Decentralized Systems, Phoenix, AZ, April 1995.

Google Scholar

[19]

Farnam Jahanian, Sameh Fakhouri, and Ragunathan Rajkumar. Processor group membership protocols: specification, design and implementation. In Proceeding of the l~h IEEE Symposium on Reliable Distributed Systems, pages 2-11, Princeton, October 1993.

Google Scholar

[20]

M. Frans Kaashoek and Andrew S. Tanenbaum. Group communication in the Amoeba distributed operating system. In Proceedings of the 11th International Conference on Distributed Computer Systems, pages 222-230, Arlington, TX, May 1991.

Google Scholar

[21]

Shivakant Mishra, Larry L. Peterson, and Richard D. Schlichting. A merebership protocol based on partial order. In Proceedings of the IEEE International Working Conference on Dependable Computing For Critical Applications, pages 137-145, Tucson, AZ, February 1991.

Google Scholar

[22]

P.M. Melliar-Smith, Louise Moser, and Vivek Agrawala. Processor membership in asynchronous distributed systems. IEEE Transactions on Parallel and Distributed Systems, 5(5):459- 473, May 1994.

Digital Library

Google Scholar

[23]

Gil Neiger. A new look at merebership services. In Proceedings of the 15th Annual A CM Symposium on Principles of Distributed Computing, Philadephia, PA, 1996.

Digital Library

Google Scholar

[24]

Gil Neiger and Sam Toueg. Automatically increasing the fault-tolerance of distributed algorithms. Journal of Algorithms, 11(3):374-419, September 1990.

Digital Library

Google Scholar

[25]

Michael R~bin. Randomized Byzantine Generals. In Proceedings of the Twenty-Fourth S~mposium on Foundations of Computer Science, pages 403-409. IEEE Computer Society Press, November 1983.

Google Scholar

[26]

Aleta Ricciardi and Kenneth P. Birman. Using process groups to iraplement failure detection in asynchronous environments. In Proceedings of the l Oth Annual A CM Symposium on Principles of Distributed Computing, pages 341-352, 1991. Also available as technical report 93-1328, Department of Computer Science, CorneU University.

Digital Library

Google Scholar

[27]

Aleta Ricciardi and Kenneth P. Bitman. Process membership in asynchronous environments. Available by anonymous ftp from ftp. ca. cornel1, edu in pub/alet a/AsyncHembService, ps, April 1994.

Google Scholar

[28]

Aleta Ricciardi. The group membership problem in asynchronous systerns. PhD thesis, Department of Computer Science, Cornell University, USA, January 1993.

Digital Library

Google Scholar

[29]

Robbert van Renesse, Kenneth P. Bitman, Robert Cooper, Bradford Glade, and Patrick Stephenson. The Horus system. In Kenneth P. Birman and Robbert van Renesse, editors, Reliable Distributed Computing with the Isis Toolkit, pages 133-147. IEEE Computer Society Press, Los Alamitos, CA, 1993.

Google Scholar

[30]

Paulo Verissimo, Werner Vogels, and Luis Rodrigues. Group orientation: a paradigm for modern distributed systems. in Proceedings of the A CM SIGOPS 1992 Workshop, Le Mont Saint-Michel, France, 1992.

Digital Library

Google Scholar

Cited By

View all

Silva DGraczyk RDecouchant JVolp MEsteves-Verissimo P(2021)Threat Adaptive Byzantine Fault Tolerant State-Machine Replication2021 40th International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS53918.2021.00017(78-87)Online publication date: Sep-2021
https://doi.org/10.1109/SRDS53918.2021.00017
Hood KOglio JNesterenko MSharma G(2021)Partitionable Asynchronous Cryptocurrency Blockchain2021 IEEE International Conference on Blockchain and Cryptocurrency (ICBC)10.1109/ICBC51069.2021.9461080(1-9)Online publication date: 3-May-2021
https://doi.org/10.1109/ICBC51069.2021.9461080
Sadi MAmad MBadache N(2019)HiCo-MoG: Hierarchical consensus-based group membership service in mobile Ad Hoc networksJournal of High Speed Networks10.3233/JHS-19060925:2(155-172)Online publication date: 21-Jun-2019
https://doi.org/10.3233/JHS-190609
Show More Cited By

Index Terms

On the impossibility of group membership

Recommendations

Semi-elliptic membership function

A potentially important, yet under-stated membership function (MF) shape viz. semi-elliptic membership function (SEMF) has been elaborated in this paper so that researchers are able to see its true potential for realistic modelling of the decision ...
A Secure Group Membership Protocol
SP '94: Proceedings of the 1994 IEEE Symposium on Security and Privacy

A group membership protocol enables processes in a distributed system to agree on a group of processes that are currently operational. Membership protocols are a core component of many distributed systems and have proved to be fundamental for ...
A Secure Group Membership Protocol

A group membership protocol enables processes in a distributed system to agree on a group of processes that are currently operational. Membership protocols are a core component of many distributed systems and have proved to be fundamental for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '96: Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing

May 1996

344 pages

ISBN:0897918002

DOI:10.1145/248052

Chairmen:
James E. Burns
Bellcore
,
Yoram Moses
Weizmann Institute of Science

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODC96

Sponsor:

PODC96: 15th Annual ACM Symposium on Principles of Distributed Computing

May 23 - 26, 1996

Pennsylvania, Philadelphia, USA

Acceptance Rates

PODC '96 Paper Acceptance Rate 69 of 117 submissions, 59%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

125
Total Citations
View Citations
1,041
Total Downloads

Downloads (Last 12 months)108
Downloads (Last 6 weeks)12

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Silva DGraczyk RDecouchant JVolp MEsteves-Verissimo P(2021)Threat Adaptive Byzantine Fault Tolerant State-Machine Replication2021 40th International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS53918.2021.00017(78-87)Online publication date: Sep-2021
https://doi.org/10.1109/SRDS53918.2021.00017
Hood KOglio JNesterenko MSharma G(2021)Partitionable Asynchronous Cryptocurrency Blockchain2021 IEEE International Conference on Blockchain and Cryptocurrency (ICBC)10.1109/ICBC51069.2021.9461080(1-9)Online publication date: 3-May-2021
https://doi.org/10.1109/ICBC51069.2021.9461080
Sadi MAmad MBadache N(2019)HiCo-MoG: Hierarchical consensus-based group membership service in mobile Ad Hoc networksJournal of High Speed Networks10.3233/JHS-19060925:2(155-172)Online publication date: 21-Jun-2019
https://doi.org/10.3233/JHS-190609
Poke MGlass C(2019)A Dual Digraph Approach for Leaderless Atomic Broadcast2019 38th Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS47363.2019.00031(203-20317)Online publication date: Oct-2019
https://doi.org/10.1109/SRDS47363.2019.00031
Foreback DNesterenko MTixeuil S(2019)Churn Possibilities and ImpossibilitiesNetworked Systems10.1007/978-3-030-05529-5_20(303-317)Online publication date: 5-Jan-2019
https://doi.org/10.1007/978-3-030-05529-5_20
Katti ADi Fatta GNaughton TEngelmann C(2018)Epidemic failure detection and consensus for extreme parallelismInternational Journal of High Performance Computing Applications10.1177/109434201769091032:5(729-743)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1177/1094342017690910
Viering MChen TEugster PHu RZiarek L(2018)A Typing Discipline for Statically Verified Crash Failure Handling in Distributed SystemsProgramming Languages and Systems10.1007/978-3-319-89884-1_28(799-826)Online publication date: 14-Apr-2018
https://doi.org/10.1007/978-3-319-89884-1_28
Chuang YMelliar-Smith PMoser LLombera I(2016)Statistical Estimation and Dynamic Adaptation Algorithms for the iTrust Publication, Search and Retrieval SystemThe Computer Journal10.1093/comjnl/bxw03859:10(1492-1510)Online publication date: 15-Jul-2016
https://doi.org/10.1093/comjnl/bxw038
Hobbs C(2015)Replication and DiversificationEmbedded Software Development for Safety-Critical Systems10.1201/b18965-14(131-151)Online publication date: 3-Sep-2015
https://doi.org/10.1201/b18965-14
Katti ADi Fatta GNaughton TEngelmann CDongarra JDenis AGoglin BJeannot EMercier G(2015)Scalable and Fault Tolerant Failure Detection and ConsensusProceedings of the 22nd European MPI Users' Group Meeting10.1145/2802658.2802660(1-9)Online publication date: 21-Sep-2015
https://dl.acm.org/doi/10.1145/2802658.2802660
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Semi-elliptic membership function

A Secure Group Membership Protocol

A Secure Group Membership Protocol