On the impossibility of group membership

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the impossibility of group membership

Full text

Pdf (874 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 322 - 330

Year of Publication: 1996

ISBN:0-89791-800-2

Authors

Tushar Deepak Chandra	H2-L10, IBM T. J. Watson Research Center, 30 Saw Mill Road, Hawthorne, NY
Vassos Hadzilacos	Computer Systems Research Institute, University of Toronto, 6 King's College Road, Toronto, Ontario, Canada M5S 1A1
Sam Toueg	Department of Computer Science, Upson Hall, Cornell University, Ithaca, NY
Bernadette Charron-Bost	Laboratoire d'Informatique LIX, Ecole Polytechnique, 91128 Palaiseau Cedex, FRANCE

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 57, Citation Count: 37

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/248052.248120 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	ACBMT95	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.
	ADKM92	Yair Amir , Danny Dolev , Shlomo Kramer , Dalia Malki, Membership Algorithms for Multicast Communication Groups, Proceedings of the 6th International Workshop on Distributed Algorithms, p.292-312, November 02-04, 1992
	BDGB94	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.
	BDM95	O. Babaoglu , R. Davoli , A. Montresor, Group Membership and View Synchrony in Partitionable Asynchronous Distributed Systems: Specifications, University of Bologna, 1995
	Ben83	Michael Ben-Or, Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.27-30, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806707]
	BJ87	K. Birman , T. Joseph, Exploiting virtual synchrony in distributed systems, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.123-138, November 08-11, 1987, Austin, Texas, United States
	BS94	Özalp Babaoğlu , André Schiper, On group communication in large-scale distributed systems, Proceedings of the 6th workshop on ACM SIGOPS European workshop: Matching operating systems to application needs, September 12-14, 1994, Wadern, Germany [doi>10.1145/504390.504396]
	BT83	Gabriel Bracha , Sam Toueg, Asynchronous consensus and broadcast protocols, Journal of the ACM (JACM), v.32 n.4, p.824-840, Oct. 1985 [doi>10.1145/4221.214134]
	CD89	Benny Chor and Cynthia Dwork. Randomization in Byzantine Agreement. Advances in Computer Research (JAI Press Inc.), 4:443-497, 1989.
	Cri91	Flaviu Cristian. Reaching agreement on processor group membership in synchronous distributed systems. Distributed Computing, 4(4):175-187, April 1991.
	CT91	Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for asynchronous systems (preliminary version), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.325-340, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112627]
	DKM93	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.
	DMS94	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.
	DMS95	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.
	DMS96	Danny Dolev , Dalia Malki , Ray Strong, A framework for partitionable membership service, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.343, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248124]
	EMS95	P. D. Ezhilchelvan , R. A. Macedo , S. K. Shrivastava, Newtop: a fault-tolerant group communication protocol, Proceedings of the 15th International Conference on Distributed Computing Systems, p.296, May 30-June 02, 1995
	FLP85	Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
	HS95	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.
	JFR93	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.
	KT91	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.
	MPS91	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.
	MSMA94	L. E. Moser , P. M. Melliar-Smith , V. Agrawala, Processor Membership in Asynchronous Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.5 n.5, p.459-473, May 1994 [doi>10.1109/71.282557]
	Nei96	Gil Neiger, A new look at membership services (extended abstract), Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.331-340, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248121]
	NT90	Gil Neiger , Sam Toueg, Automatically increasing the fault-tolerance of distributed algorithms, Journal of Algorithms, v.11 n.3, p.374-419, Sep. 1990 [doi>10.1016/0196-6774(90)90019-B]
	Rab83	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.
	RB91	Aleta M. Ricciardi , Kenneth P. Birman, Using process groups to implement failure detection in asynchronous environments, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.341-353, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112628]
	RB94	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.
	Ric93	Aleta Marie Ricciardi, The group membership problem in asynchronous systems, Cornell University, Ithaca, NY, 1993
	vRBC+93	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.
	VVR92	Paulo Veríssimo , Luís Rodrigues, Group orientation: a paradigm for modern distributed systems, Proceedings of the 5th workshop on ACM SIGOPS European workshop: Models and paradigms for distributed systems structuring, September 21-23, 1992, Mont Saint-Michel, France [doi>10.1145/506378.506417]

CITED BY 37

	Shlomi Dolev , Elad Schiller, Communication Adaptive Self-Stabilizing Group Membership Service, IEEE Transactions on Parallel and Distributed Systems, v.14 n.7, p.709-720, July 2003
	Vasken Bohossian , Chenggong C. Fan , Paul S. LeMahieu , Marc D. Riedel , Jehoshua Bruck , Lihao Xu, Computing in the RAIN: A Reliable Array of Independent Nodes, IEEE Transactions on Parallel and Distributed Systems, v.12 n.2, p.99-114, February 2001
	Gil Neiger, A new look at membership services (extended abstract), Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.331-340, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Danny Dolev , Dalia Malki, The Transis approach to high availability cluster communication, Communications of the ACM, v.39 n.4, p.64-70, April 1996
	Gregory V. Chockler , Idid Keidar , Roman Vitenberg, Group communication specifications: a comprehensive study, ACM Computing Surveys (CSUR), v.33 n.4, p.427-469, December 2001
	Alan Fekete , Nancy Lynch , Alex Shvartsman, Specifying and using a partitionable group communication service, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.53-62, August 21-24, 1997, Santa Barbara, California, United States
	Roberto De Prisco , Alan Fekete , Nancy Lynch , Alex Shvartsman, A dynamic view-oriented group communication service, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.227-236, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Danny Dolev , Idit Keidar , Esti Yeger Lotem, Dynamic voting for consistent primary components, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.63-71, August 21-24, 1997, Santa Barbara, California, United States
	Paulo Veríssimo , António Casimiro, The Timely Computing Base Model and Architecture, IEEE Transactions on Computers, v.51 n.8, p.916-930, August 2002
	Wei Chen , Sam Toueg , Marcos Kawazoe Aguilera, On the Quality of Service of Failure Detectors, IEEE Transactions on Computers, v.51 n.5, p.561-580, May 2002
	John Rushby, Systematic Formal Verification for Fault-Tolerant Time-Triggered Algorithms, IEEE Transactions on Software Engineering, v.25 n.5, p.651-660, September 1999
	Andre Schiper , Sam Toueg, From Set Membership to Group Membership: A Separation of Concerns, IEEE Transactions on Dependable and Secure Computing, v.3 n.1, p.2, January 2006
	Massimo Franceschetti , Jehoshua Bruck, A Group Membership Algorithm with a Practical Specification, IEEE Transactions on Parallel and Distributed Systems, v.12 n.11, p.1190-1200, November 2001
	References, Grid resource management: state of the art and future trends, Kluwer Academic Publishers, Norwell, MA, 2004
	Flaviu Cristian , Christof Fetzer, The Timed Asynchronous Distributed System Model, IEEE Transactions on Parallel and Distributed Systems, v.10 n.6, p.642-657, June 1999
	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003
	Alberto Bartoli, Implementing a replicated service with group communication, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.8, p.493-519, August 2004
	Felix C. Gärtner, Fundamentals of fault-tolerant distributed computing in asynchronous environments, ACM Computing Surveys (CSUR), v.31 n.1, p.1-26, March 1999
	Jeremy Sussman , Keith Marzullo, The Bancomat problem: an example of resource allocation in a partitionable asynchronous system, Theoretical Computer Science, v.291 n.1, p.103-131, 4 January 2003
	Qingfeng Huang , Christine Julien , Gruia-Catalin Roman, Relying on Safe Distance to Achieve Strong Partitionable Group Membership in Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.3 n.2, p.192-205, April 2004
	Roger I. Khazan, Group membership: a novel approach and the first single-round algorithm, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Özalp Babaoglu , Renzo Davoli , Alberto Montresor, Group Communication in Partitionable Systems: Specification and Algorithms, IEEE Transactions on Software Engineering, v.27 n.4, p.308-336, April 2001
	Christos T. Karamanolis , Jeffrey N. Magee, Client-Access Protocols for Replicated Services, IEEE Transactions on Software Engineering, v.25 n.1, p.3-21, January 1999
	Shivakant Mishra , Christof Fetzer , Flaviu Cristian, The Timewheel Group Communication System, IEEE Transactions on Computers, v.51 n.8, p.883-899, August 2002
	Shivakant Mishra , Lan Fei , Xiao Lin , Guming Xing, On Group Communication Support in CORBA, IEEE Transactions on Parallel and Distributed Systems, v.12 n.2, p.193-208, February 2001
	Idit Keidar , Jeremy Sussman , Keith Marzullo , Danny Dolev, Moshe: A group membership service for WANs, ACM Transactions on Computer Systems (TOCS), v.20 n.3, p.191-238, August 2002
	Raimundo J. Araújo Macêdo , Flávio M. Assis Silva, The mobile groups approach for the coordination of mobile agents, Journal of Parallel and Distributed Computing, v.65 n.3, p.275-288, March 2005
	Yair Amir , Cristina Nita-Rotaru , Jonathan Stanton , Gene Tsudik, Secure Spread: An Integrated Architecture for Secure Group Communication, IEEE Transactions on Dependable and Secure Computing, v.2 n.3, p.248-261, July 2005
	Paulo E. Veríssimo, Travelling through wormholes: a new look at distributed systems models, ACM SIGACT News, v.37 n.1, March 2006
	Wei Chen , Sam Toueg , Marcos Kawazoe Aguilera, On the Quality of Service of Failure Detectors, IEEE Transactions on Computers, v.51 n.1, p.13-32, January 2002
	Roberto Baldoni , Stefano Cimmino , Carlo Marchetti, A classification of total order specifications and its application to fixed sequencer-based implementations, Journal of Parallel and Distributed Computing, v.66 n.1, p.108-127, January 2006
	Specifying and using a partitionable group communication service, ACM Transactions on Computer Systems (TOCS), v.19 n.2, p.171-216, May 2001
	Danny Dolev, Century papers at the first quarter-century milestone, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, p.3-4, July 23-26, 2006, Denver, Colorado, USA
	E. Garcia , H. Guyennet , J.-C. Lapayre, Groups Partitioning Over CORBA for Cooperative Work, Cluster Computing, v.9 n.1, p.67-78, January 2006
	Mark W. Burns , Alan D. George , Bradley A. Wallace, Simulative performance analysis of gossip failure detection for scalable distributed systems, Cluster Computing, v.2 n.3, p.207-217, 1999
	Juan Carlos García , Stefan Beyer , Pablo Galdámez, Cross-layer cooperation between membership estimation and routing, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
	Marcos Kawazoe Aguilera , Idit Keidar , Dahlia Malkhi , Alexander Shraer, Dynamic atomic storage without consensus, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada