article

Group communication specifications: a comprehensive study

Authors:

Gregory V. Chockler,

Idit Keidar,

Roman VitenbergAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 33, Issue 4

Pages 427 - 469

https://doi.org/10.1145/503112.503113

Published: 01 December 2001 Publication History

Get Access

Abstract

View-oriented group communication is an important and widely used building block for many distributed applications. Much current research has been dedicated to specifying the semantics and services of view-oriented group communication systems (GCSs). However, the guarantees of different GCSs are formulated using varying terminologies and modeling techniques, and the specifications vary in their rigor. This makes it difficult to analyze and compare the different systems. This survey provides a comprehensive set of clear and rigorous specifications, which may be combined to represent the guarantees of most existing GCSs. In the light of these specifications, over 30 published GCS specifications are surveyed. Thus, the specifications serve as a unifying framework for the classification, analysis, and comparison of group communication systems. The survey also discusses over a dozen different applications of group communication systems, shedding light on the usefulness of the presented specifications. This survey is aimed at both system builders and theoretical researchers. The specification framework presented in this article will help builders of group communication systems understand and specify their service semantics; the extensive survey will allow them to compare their service to others. Application builders will find a guide here to the services provided by a large variety of GCSs, which could help them choose the GCS appropriate for their needs. The formal framework may provide a basis for interesting theoretical work, for example, analyzing relative strengths of different properties and the costs of implementing them.

References

[1]

ABDELZAHER, T., SHAIKH, A., JAHANIAN,F.,AND SHIN,K. 1996. RTCAST: Lightweight multicast for realtime process groups. In IEEE Real-Time Technology and Applications Symposium (RTAS) (June).]]

Digital Library

Google Scholar

[2]

AHUJA, M. 1993. Assertions about past and future in highways: Global flush broadcast and flush-v ector- time. Information Processing Letters 48,1 (October), 21-28.]]

Digital Library

Google Scholar

[3]

AL-SHAER, E., YOUSSEF, A., ABDEL-WAHAB, H., MALY, K., AND OVERSTREET, C. M. 1997. Reliability, scalability and robustness issues in IRI. In IEEE Sixth Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE'97) (June).]]

Digital Library

Google Scholar

[4]

AL-SHAER,E.S.,ABDEL-WAHAB, H., AND MALY,K. 1999. HiFi: A new monitoring architecture for distributed system management. In 19th International Conference on Distributed Computing Systems (ICDCS) (June), pp. 171-178.]]

Digital Library

Google Scholar

[5]

AMIR, O., AMIR,Y.,AND DOLEV, D. 1993. A highly available application in the Transis environment. In Proceedings of the Hardware and Software Architectures for Fault Tolerance Workshop, at Le Mont Saint-Michel, France (June). LNCS 774.]]

Digital Library

Google Scholar

[6]

AMIR,Y.AND STANTON, J. 1998. The spread wide area group communication system. TR CNDS-98-4, The Center for Networking and Distributed Systems, The Johns Hopkins University.]]

Google Scholar

[7]

AMIR, Y., BREITGAND, D., CHOCKLER,G.,AND DOLEV,D. 1996. Group communication as an infrastructure for distributed system management. In The Third International Workshop on Services in Distributed and Networked Environment (SDNE) (June), pp. 84-91.]]

Digital Library

Google Scholar

[8]

AMIR, Y., CHOCKLER,G.V.,DOLEV,D.,AND VITENBERG, R. 1997. Efficient state transfer in partitionable environments. In Second European Research Seminar on Advances in Distributed Systems (ERSADS'97) (March), pp. 183-192. BROADCAST (ESPRIT WG 22455): Operating Systems Laboratory, Swiss Federal Institute of Technology, Lausanne. Full version: Tech. Rep. CS98-12, Institute of Computer Science, The Hebrew University, Jerusalem, Israel.]]

Google Scholar

[9]

AMIR, Y., DOLEV, D., KRAMER,S.,AND MALKI, D. 1992a. Membership algorithms for multicast communication groups. In Six International Workshop on Distributed Algorithms (WDAG) (November), pp. 292-312. Springer Verlag.]]

Digital Library

Google Scholar

[10]

AMIR, Y., DOLEV, D., KRAMER,S.,AND MALKI, D. 1992b. Transis: A communication sub-system for high availability. In 22nd IEEE Fault-Tolerant Computing Symposium (FTCS) (July).]]

Google Scholar

[11]

AMIR, Y., DOLEV, D., MELLIAR-SMITH,P.M.,AND MOSER, L. E. 1994. Robust and efficient replication using group communication. Tech. Rep. CS94- 20, Institute of Computer Science, Hebrew University, Jerusalem, Israel.]]

Google Scholar

[12]

AMIR, Y., MOSER, L. E., MELLIAR-SMITH,P.M., AGARWAL,D.A.,AND CIARFELLA, P. 1995. The Totem single-ring ordering and membership protocol. ACM Transactions on Computer Systems 13, 4 (November).]]

Digital Library

Google Scholar

[13]

ANCEAUME, E., CHARRON-BOST, B., MINET,P.,AND TOUEG, S. 1995. On the formal specification of group membership services. TR 95-1534 (August), Dept. of Computer Science, Cornell University.]]

Google Scholar

[14]

ANKER, T., CHOCKLER, G., DOLEV,D.,AND KEIDAR, I. 1998. Scalable group membership services for novel applications. In M. Mavronicolas, M. Merritt, and N. Shavit, Eds., Networks in Distributed Computing (DIMACS Workshop), vol. 45 of DIMACS, pp. 23-42. American Mathematical Society.]]

Crossref

Google Scholar

[15]

ANKER, T., CHOCKLER, G., SHNAIDERMAN, I., AND DOLEV, D. 2000. The design of Xpand: A group communication system for wide area networks. Tech. Rep. 2000-31 (July), Institute of Computer Science, Hebrew University, Jerusalem, Israel.]]

Google Scholar

[16]

ANKER, T., CHOCKLER,G.V.,DOLEV,D.,AND KEIDAR,I. 1997. The Caelum toolkit for CSCW: The sky is the limit. In The Third International Workshop on Next Generation Information Technologies and Systems (NGITS 97) (June), pp. 69-76.]]

Google Scholar

[17]

ANKER, T., DOLEV,D.,AND KEIDAR, I. 1999. Fault tolerant video-on-demand services. In 19th International Conference on Distributed Computing Systems (ICDCS) (June), pp. 244-252.]]

Digital Library

Google Scholar

[18]

BABAOGLU, O., BARTOLI, A., AND DINI, G. 1996. On programming with view synchrony. In 16th International Conference on Distributed Computing Systems (ICDCS) (May), pp. 3-10. Also Tech. Rep. UBLCS95-15, Department of Computer Science, University of Bologna, 1995.]]

Digital Library

Google Scholar

[19]

BABAOGLU, O., DAVOLI, A., MONTRESOR, A., AND SEGALA, R. 1998a. System support for partitionaware network applications. In 18th International Conference on Distributed Computing Systems (ICDCS) (May), pp. 184-191.]]

Digital Library

Google Scholar

[20]

BABAOGLU, O., DAVOLI, R., AND MONTRESOR, A. 1998b. Group communication in partitionable systems: Specification and algorithms. TR UBLCS98-1 (April), Department of Computer Science, University of Bologna. In IEEE Transactions on Software Engineering, 27, 4 (April 2001), 308- 336.]]

Digital Library

Google Scholar

[21]

BIRMAN, K. 1996. Building Secure and Reliable Network Applications. Manning.]]

Digital Library

Google Scholar

[22]

BIRMAN,K.AND JOSEPH, T. 1987. Exploiting virtual synchrony in distributed systems. In 11th ACM SIGOPS Symposium on Operating Systems Principles (SOSP) (November), pp. 123- 138. ACM.]]

Digital Library

Google Scholar

[23]

BIRMAN,K.AND VAN RENESSE, R. 1994. Reliable Distributed Computing with the Isis Toolkit. IEEE Computer Society Press.]]

Digital Library

Google Scholar

[24]

BIRMAN, K., FRIEDMAN, R., HAYDEN, M., AND RHEE,I. 1998. Middleware support for distributed multimedia and collaborative computing. In Multimedia Computing and Networking (MMCN98).]]

Google Scholar

[25]

BIRMAN, K. P. 1986. ISIS: A system for faulttolerant distributed computing. Tech. Rep. TR86-744 (April), Cornell University, Department of Computer Science.]]

Digital Library

Google Scholar

[26]

CHANDRA, T., HADZILACOS, V., TOUEG,S.,AND CHARRON-BOST, B. 1996. On the impossibility of group membership. In 15th ACM Symposium on Principles of Distributed Computing (PODC) (May), pp. 322-330.]]

Digital Library

Google Scholar

[27]

CHANDRA,T.D.AND TOUEG, S. 1996. Unreliable failure detectors for reliable distributed systems. Journal of the ACM 43, 2 (March), 225-267.]]

Digital Library

Google Scholar

[28]

CHERITON,D.AND ZWAENEPOEL, W. 1985. Distributed process groups in the V kernel. ACM Transactions on Computer Systems 3,2,77- 107.]]

Digital Library

Google Scholar

[29]

CHOCKLER, G., HULEIHEL,N.,AND DOLEV, D. 1998. An adaptive totally ordered multicast protocol that tolerates partitions. In 17th ACM Symposium on Principles of Distributed Computing (PODC) (June), pp. 237-246.]]

Digital Library

Google Scholar

[30]

CHOCKLER, G., HULEIHEL, N., KEIDAR, I., AND DOLEV,D. 1996. Multimedia multicast transport service for groupware. In TINA Conference on the Convergence of Telecommunications and Distributed Computing Technologies (September).]]

Google Scholar

[31]

CHODROW, S., HIRCSH, M., RHEE, I., AND CHEUNG,S.Y. 1997. Design and implementation of a multicast audio conferencing tool for a collaborative computing framework. In JCIS (March).]]

Google Scholar

[32]

CRISTIAN, F. 1991. Reaching agreement on processor group membership in synchronous distributedsystems. Distributed Computing 4,4 (April), 175-187.]]

Digital Library

Google Scholar

[33]

CRISTIAN,F.AND FETZER, C. 1999. The timed asynchronous distributed system model. IEEE Transactions on Parallel and Distributed Systems, 642-657.]]

Digital Library

Google Scholar

[34]

CRISTIAN,F.AND SCHMUCK, F. 1995. Agreeing on process group membership in asynchronous distributed systems. Tech. Rep. CSE95-428, Department of Computer Science and Engineering, University of California, San Diego.]]

Google Scholar

[35]

DE PRISCO, R., FEKETE, A., LYNCH,N.,AND SHVARTSMAN, A. 1998. A dynamic view-oriented group communication service. In 17th ACM Symposium on Principles of Distributed Computing (PODC) (June), pp. 227-236.]]

Digital Library

Google Scholar

[36]

DEFAGO, X., SCHIPER, A., AND URBAN, P. 2000. Totally ordered broadcast and multicast algorithms: A comprehensive survey. Tech. Rep. DSC/2000/036 (September), Swiss Federal Institute of Technology, Lausanne, Switzerland.]]

Google Scholar

[37]

DOLEV,D.AND MALKHI, D. 1996. The Transis approach to high availability cluster communication. Communications of the ACM 39, 4 (April), 64-70.]]

Digital Library

Google Scholar

[38]

DOLEV, D., FRIEDMAN, R., KEIDAR, I., AND MALKI,D. 1997. Failure detectors in omission failure environments. In 16th ACMSymposium on Principles of Distributed Computing (PODC) (August), pp. 286. Brief announcement. Full version: Tech. Rep. 96-1608, Department of Computer Science, Cornell University.]]

Digital Library

Google Scholar

[39]

DOLEV, D., MALKI,D.,AND STRONG, H. R. 1995. A framework for partitionable membership service. TR 95-4 (March), Institute of Computer Science, Hebrew University.]]

Google Scholar

[40]

DOLEV, S., SEGALA, R., AND SHVARTSMAN, A. 1999. Dynamic load balancing with group communication. In Six International Colloquium on Structural Information and Communication Complexity (SIROCCO'99), pp. 111-125.]]

Google Scholar

[41]

DWORK, C., LYNCH,N.,AND STOCKMEYER, L. 1988. Consensus in the presence of partial synchrony. Journal of the ACM 35, 2 (April), 288-323.]]

Digital Library

Google Scholar

[42]

EZHILCHELVAN,P.D.,MACEDO, A., AND SHRIVASTAVA,S.K. 1995. Newtop: A fault tolerant group communication protocol. In 15th International Conference on Distributed Computing Systems (ICDCS) (June).]]

Digital Library

Google Scholar

[43]

FEKETE,A.AND KEIDAR, I. 2001. A framework for highly available services based on group communication. In IEEE 21st International Conference on Distributed Computing Systems Workshops (ICDCS-21W 2001); the International Workshop on Applied Reliable Group Communication (WARGC) (April), 57-62.]]

Digital Library

Google Scholar

[44]

FEKETE, A., LYNCH,N.,AND SHVARTSMAN, A. 1997. Specifying and using a partitionable group communication service. In 16th ACM Symposium on Principles of Distributed Computing (PODC) (August), pp. 53-62. Full version to appear in ACM Transactions on Computer Systems 19, 2 (May 2001), 171-216.]]

Digital Library

Google Scholar

[45]

FELBER, P., GUERRAOUI, R., AND SCHIPER, A. 1998. The implementation of a CORBA object group service. Theory and Practice of Object Systems 4, 2, 93-105.]]

Digital Library

Google Scholar

[46]

FRIEDMAN,R.AND VAN RENESSE, R. 1995. Strong and weak virtual synchrony in Horus. TR 95-1537 (August), Dept. of Computer Science, Cornell University.]]

Google Scholar

[47]

FRIEDMAN,R.AND VAYSBURG, A. 1997. Fast replicated state machines over partitionable networks. In 16th IEEE International Symposium on Reliable Distributed Systems (SRDS) (October).]]

Digital Library

Google Scholar

[48]

FRITZKE,U.J.,INGELS, P., MOSTEFAOUI, A., AND RAYNAL, M. 1998. Fault-tolerant total order multicast to asynchronous groups. In 17th IEEE International Symposium on Reliable Distributed Systems (SRDS) (October), pp. 228-234.]]

Digital Library

Google Scholar

[49]

GALLENI,A.AND POWELL, D. 1996. Consensus and membership in synchronous and asynchronous distributed systems. Tech. Rep. 96104 (April), LAAS-CNRS. Revised January 1997.]]

Digital Library

Google Scholar

[50]

GANG, D., CHOCKLER, G., ANKER, T., KREMER, A., AND WINKLER, T. 1997. Conducting Midi sessions over the network using the Transis group communication system. In International Computer Music Conference (ICMC 97) (September).]]

Google Scholar

[51]

GOFT,G.AND YEGER LOTEM, E. 1999. The AS/400 cluster engine: A case study. In IGCC 1999, in conjunction with ICPP 1999.]]

Digital Library

Google Scholar

[52]

GUERRAOUI,R.AND SCHIPER, A. 1995. Transaction model vs. virtual synchrony model: Bridging the gap. In Theory and Practice in Distributed Systems, LNCS 938 (September), pp. 121-132. Springer-Verlag.]]

Digital Library

Google Scholar

[53]

GUERRAOUI,R.AND SCHIPER, A. 1997a. Consensus: The big misunderstanding. In Proceedings of the Six IEEE Computer Society Workshop on Future Trends in Distributed Computing Systems (FTDCS-6) (Tunis, Tunisia, October), pp. 183-188. IEEE Computer Society Press.]]

Digital Library

Google Scholar

[54]

GUERRAOUI,R.AND SCHIPER, A. 1997b. Softwarebased replication for fault tolerance. IEEE Computer 30, 4 (April), 68-74.]]

Digital Library

Google Scholar

[55]

GUERRAOUI,R.AND SCHIPER, A. 2000. Genuine atomic multicast in asynchronous distributed systems. Theoretical Computer Science 254, 1-2 (March 2001), 297-316. Also Tech. Rep. 98/273, Swiss Federal Institute of Technology.]]

Digital Library

Google Scholar

[56]

GUTTAG,J.V.,HORNING,J.J.,GARLAND,S.J.,JONES, K. D., MODET, A., AND WING, J. M. 1993. Larch: Languages and Tools for Formal Specification. Texts and Monographs in Computer Science. Springer-Verlag.]]

Digital Library

Google Scholar

[57]

HAYDEN,M.AND VAN RENESSE, R. 1996. optimizing layered communication protocols. Tech. Rep. TR96-1613 (November), Dept. of Computer Science, Cornell University, Ithaca, NY.]]

Digital Library

Google Scholar

[58]

HICKEY, J., LYNCH,N.,AND VAN RENESSE, R. 1999. Specifications and proofs for ensemble layers. In Fifth International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), LNCS (March). Springer- Verlag.]]

Digital Library

Google Scholar

[59]

HILTUNEN,M.AND SCHLICHTING, R. 1995. Properties of membership services. In Second International Symposium on Autonomous Decentralized Systems, pp. 200-207.]]

Crossref

Google Scholar

[60]

HILTUNEN,M.A.AND SCHLICHTING, R. D. 1998. A configurable membership service. IEEE Transactions on Computers 47, 5 (May), 573- 586.]]

Digital Library

Google Scholar

[61]

IBM 1996. RS/6000 SP High Availability Infrastructure. IBM. SG24-4838, available online at: http://www.redbooks.ibm.com/abstracts/sg2448- 38.html.]]

Google Scholar

[62]

IONA 1994. IONA and Isis. An Introduction to Orbix+ISIS. IONA Technologies and Isis Distributed Systems.]]

Google Scholar

[63]

JAHANIAN, F., FAKHOURI,S.,AND RAJKUMAR, R. 1993. Processor group membership protocols: Specification, design and implementation. In 12th IEEE International Symposium on Reliable Distributed Systems (SRDS) (October), pp. 2-11. IEEE.]]

Crossref

Google Scholar

[64]

JOHNSON, S., JAHANIAN, F., GHOSH, S., VANVOORST, B., AND WEININGER, N. 2000. Experiences with group communication middleware. In The International Conference on Dependable Systems and Networks (DSN). Practical Experience Report.]]

Digital Library

Google Scholar

[65]

JOHNSON, S., JAHANIAN,F.,AND SHAH, J. 1999. The inter-group router approach to scalable group composition. In 19th International Conference on Distributed Computing Systems (ICDCS) (June), pp. 4-14.]]

Digital Library

Google Scholar

[66]

KAASHOEK,M.F.AND TANENBAUM, A. S. 1996. An evaluation of the Amoeba group communication system. In 16th International Conference on Distributed Computing Systems (ICDCS) (May), pp. 436-447.]]

Digital Library

Google Scholar

[67]

KALANTAR,M.AND BIRMAN, K. 1999. Causally ordered multicast: The conservative approach. In 19th International Conference on Distributed Computing Systems (ICDCS) (June), pp. 36-44.]]

Digital Library

Google Scholar

[68]

KEIDAR, I. 1994. A highly available paradigm for consistent object replication. Master's thesis, Institute of Computer Science, Hebrew University, Jerusalem, Israel. Also Institute of Computer Science, Hebrew University Tech. Rep. CS95-5, and available from: http://www.cs.huji.ac.il/ >> transis/publications. html.]]

Google Scholar

[69]

KEIDAR,I.AND DOLEV, D. 1996. Efficient message ordering in dynamic networks. In 15th ACM Symposium on Principles of Distributed Computing (PODC) (May), pp. 68-76.]]

Digital Library

Google Scholar

[70]

KEIDAR,I.AND DOLEV, D. 2000. Totally ordered broadcast in the face of network partitions. Exploiting group communication for replication in partitionable networks. In D. Avresky, Ed., Chapter 3 of Dependable Network Computing, pp. 51-75. Kluwer Academic.]]

Crossref

Google Scholar

[71]

KEIDAR,I.AND KHAZAN, R. 2000. A client-server approach to virtually synchronous group multicast: Specifications and algorithms. In 20th International Conference on Distributed Computing Systems (ICDCS) (April), pp. 344-355. Full version: MIT Tech. Rep. MIT-LCS-TR-794.]]

Digital Library

Google Scholar

[72]

KEIDAR, I., SUSSMAN, J., MARZULLO, K., AND DOLEV, D. 2000. A client-server oriented algorithm for virtually synchronous group membership in WANs. In 20th International Conference on Distributed Computing Systems (ICDCS) (April), pp. 356-365. Full version: MIT Technical Memorandum MIT-LCS-TM-593a, June 1999, revised September 2000.]]

Digital Library

Google Scholar

[73]

KEMME,B.AND ALONSO, G. 1998. A suite of database replication protocols based on group communication primitives. In 18th International Conference on Distributed Computing Systems (ICDCS) (May).]]

Digital Library

Google Scholar

[74]

KHAZAN, R., FEKETE, A., AND LYNCH, N. 1998. Multicast group communication as a base for a load-balancing replicated data service. In 12th International Symposium on DIStributed Computing (DISC) (Andros, Greece, September), pp. 258- 272.]]

Digital Library

Google Scholar

[75]

KRANTZ, A., CHODROW,S.,AND HIRCSH, M. 1998. Design and implementation of a distributed x multiplexor. In 18th International Conference on Distributed Computing Systems (ICDCS) (May).]]

Digital Library

Google Scholar

[76]

KRANTZ, A., RHEE, I., BREUKER, C., CHODROW,S.,AND SUNDERAM, V. 1997. Supporting input multiplexing in a heterogenous environment. In JCIS (March).]]

Google Scholar

[77]

KSHEMKALYANI,A.D.AND SINGHAL, M. 1998. Necessary and sufficient conditions on information for causal message ordering and their optimal implementation. Distributed Computing 11,2 (April), 91-111.]]

Digital Library

Google Scholar

[78]

LAMPORT, L. 1978. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM 21, 7 (July), 558-565.]]

Digital Library

Google Scholar

[79]

LANDIS,S.AND MAFFEIS, S. 1997. Building reliable distributed systems with CORBA. Theory and Practice of Object Systems 3,1.]]

Crossref

Google Scholar

[80]

LIN,K.AND HADZILACOS, V. 1999. Asynchronous group membership with oracles. In 13th International Symposium on DIStributed Computing (DISC) (Bratislava, Slovak Republic), pp. 79-93.]]

Digital Library

Google Scholar

[81]

LYNCH, N. 1996. Distributed Algorithms. Morgan Kaufmann.]]

Digital Library

Google Scholar

[82]

LYNCH,N.AND TUTTLE, M. 1989. An introduction to input/output automata. CWIQuarterly 2, 3, 219- 246.]]

Google Scholar

[83]

MALKHI,D.AND REITER, M. 1997. A highthroughput secure reliable multicast protocol. Journal of Computer Security 5, 113-127.]]

Digital Library

Google Scholar

[84]

MALKHI, D., MERRITT, M., AND RODEH, O. 1997. Secure multicast in a WAN. In 17th International Conference on Distributed Computing Systems (ICDCS) (May), pp. 87--94.]]

Digital Library

Google Scholar

[85]

MALLOTH,C.AND SCHIPER, A. 1995. View synchronous communication in large scale networks. In Second Open Workshop of the ES- PRIT project BROADCAST (Number 6360) (July).]]

Google Scholar

[86]

MALLOTH,C.P.,FELBER, P., SCHIPER, A., AND WILHELM, U. 1995. Phoenix: A toolkit for building faulttolerant, distributed applications in large scale. In Worksho on Parallel and Distributed Platforms in Industrial Products (October).]]

Google Scholar

[87]

MISHRA,S.AND PANG, G. 1999. Design and implementation of an availability management service. In 19th International Conference on Distributed Computing Systems (ICDCS) Workshop on Middleware (June), pp. 128-133.]]

Crossref

Google Scholar

[88]

MISHRA, S., FETZER,C.,AND CRISTIAN, F. 1998. The Timewheel group membership protocol. In Third IEEE Workshop on Fault-tolerant Parallel and Distributed Systems (FTPDS) (April).]]

Crossref

Google Scholar

[89]

MISHRA, S., PETERSON,L.L.,AND SCHLICHTING,R.D. 1991. A membership protocol based on partial order. In International Working Conference on Dependable Computing for Critical Applications (February).]]

Google Scholar

[90]

MISHRA, S., PETERSON,L.L.,AND SCHLICHTING,R.L. 1993. Consul: A communication substrate for fault-tolerant distributed programs. Distributed Systems Engineering Journal 1, 2 (Dec.), 87-103.]]

Crossref

Google Scholar

[91]

MONTRESOR, A., DAVOLI, R., AND BABAOGLU, O. 2000. Middleware for dependable network services in partitionable distributed systems. In PODC Middleware Symposium (July). Also Tech. Rep. UBLCS 99-19, October 1999 (Revised April 2000).]]

Digital Library

Google Scholar

[92]

MOSER, L. E., AMIR, Y., MELLIAR-SMITH, P. M., AND AGARWAL, D. A. 1994. Extended virtual synchrony. In 14th International Conference on Distributed Computing Systems (ICDCS) (June), pp. 56-65.]]

Crossref

Google Scholar

[93]

MOSER, L. E., MELLIAR-SMITH,P.M.,AND NARASIMHAN, P. 1998. Consistent object replication in the Eternal system. Theory and Practice of Object Systems 4, 2, 81-92.]]

Digital Library

Google Scholar

[94]

NEIGER, G. 1996. A new look at membership services. In 15th ACM Symposium on Principles of Distributed Computing (PODC), pp. 331-340. ACM.]]

Digital Library

Google Scholar

[95]

OMG. 2000. Fault Tolerant CORBA Specification. OMG (Object Management Group) Document ptc/2000-04-04.]]

Google Scholar

[96]

REITER, M. K. 1996. A secure group membership protocol. IEEE Transactions on Software Engineering 22, 1 (January), 31-42.]]

Digital Library

Google Scholar

[97]

RHEE, I., CHEUNG, S., HUTTO,P.,AND SUNDERAM,V. 1997. Group communication support for dis-tributed multimedia and CSCWsystems. In 17th International Conference on Distributed Computing Systems (ICDCS).]]

Digital Library

Google Scholar

[98]

RICCIARDI,A.M.AND BIRMAN, K. P. 1991. Using process groups to implement failure detection in asynchronous environments. In ACM Symposium on Principles of Distributed Computing (PODC) (August), pp. 341-352.]]

Digital Library

Google Scholar

[99]

RODRIGUES,L.AND VERISSIMO, P. 1992. xAMp, a protocol suite for group communication. RT /43-92 (January), INESC.]]

Google Scholar

[100]

SCHIPER,A.AND RAYNAL, M. 1996. From group communication to transactions in distributed systems. Communications of the ACM 39, 4 (April), 84-87.]]

Digital Library

Google Scholar

[101]

SCHIPER,A.AND RICCIARDI, A. 1993. Virtually synchronous communication based on a weak failure suspector. In 23rd IEEE Fault-Tolerant Computing Symposium (FTCS) (June), pp. 534- 543.]]

Crossref

Google Scholar

[102]

SCHIPER,A.AND SANDOZ, A. 1993. Uniform reliable multicast in a virtually synchronous environment. In 13th International Conference on Distributed Computing Systems (ICDCS) (May), pp. 561-568.]]

Crossref

Google Scholar

[103]

SCHNEIDER, F. B. 1990. Implementing fault tolerant services using the state machine approach: A tutorial. ACMComputing Surveys 22, 4 (Dec.), 299-319.]]

Digital Library

Google Scholar

[104]

SHAMIR, G. 1996. Shared whiteboard: A Java application in the Transis environment. Lab project, High Availability lab, The Hebrew University of Jerusalem, Jerusalem, Israel. Available from: http://www.cs.huji.ac.il/ >> transis/ publications.html.]]

Google Scholar

[105]

SUSSMAN,J.AND MARZULLO, K. 1998. The Bancomat problem: An example of resource allocation in a partitionable asynchronous system. In 12th International Symposium on DIStributed Computing (DISC) (September). Full version: Tech. Rep. 98-570 University of California, San Diego Department of Computer Science and Engineering.]]

Digital Library

Google Scholar

[106]

SUSSMAN, J., KEIDAR, I., AND MARZULLO, K. 2000. Optimistic virtual synchrony. In 19th IEEE International Symposium on Reliable Distributed Systems (SRDS) (October), pp. 42-51.]]

Digital Library

Google Scholar

[107]

VALENCI, M. 1998. Audio conferencing using Transis. Lab project, High Availability lab, The Hebrew University of Jerusalem, Jerusalem, Israel. Available from: http://www.cs.huji.ac.il/ >> transis/publications. html.]]

Google Scholar

[108]

VAN RENESSE, R., BIRMAN,K.P.,AND MAFFEIS, S. 1996. Horus: A flexible group communication system. Communications of the ACM39, 4 (April), 76-83.]]

Digital Library

Google Scholar

[109]

VITENBERG, R. 1998. Properties of distributed group communication and their utilization. Master's thesis, Institute of Computer Science, Hebrew University, Jerusalem, Israel.]]

Google Scholar

[110]

VOGELS, W. 1996. World wide failures. In ACM SIGOPS 1996 European Workshop (September).]]

Digital Library

Google Scholar

[111]

VOGELS,W.AND VAN RENESSE, R. 1994. Support for complex multi-media applications using the Horus system. Ithaca, NY, Dept. of Computer Science, Cornell University. Online html document: http://www.cs.cornell.edu/Info/ People/rvr/papers/rt/novsdav.html.]]

Google Scholar

[112]

WHETTEN, B., MONTGOMERY,T.,AND KAPLAN, S. 1995. A high performance totally ordered multicast protocol. In K. P. Birman, F. Mattern, and A. Schiper, Eds., Theory and Practice in Distributed Systems: International Workshop, pp. 33-57. Springer Verlag. LNCS 938.]]

Digital Library

Google Scholar

[113]

WILHELM,U.G.AND SCHIPER, A. 1995. A hierarchy of totally ordered multicasts. In 14th IEEE International Symposium on Reliable Distributed Systems (SRDS) (September).]]

Digital Library

Google Scholar

[114]

YEGER LOTEM, E., KEIDAR, I., AND DOLEV, D. 1997. Dynamic voting for consistent primary components. In 16th ACM Symposium on Principles of Distributed Computing (PODC) (August), pp. 63-71.]]

Digital Library

Google Scholar

Cited By

View all

Iyer RKalbarczyk ZNakka N(2024)Reliable Networked and Distributed SystemsDependable Computing10.1002/9781119743453.ch8(337-411)Online publication date: 26-Apr-2024
https://doi.org/10.1002/9781119743453.ch8
Zhang MMa THua JLiu ZChen KDing NDu FJiang JMa TWu YDruschel PKaufmann AMace JFlinn JSeltzer M(2023)Partial Failure Resilient Memory Management System for (CXL-based) Distributed Shared MemoryProceedings of the 29th Symposium on Operating Systems Principles10.1145/3600006.3613135(658-674)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3600006.3613135
Izraelevitz JWang GHanscom RSilvers KLehman TChockler GGotsman A(2022)Acuerdo: Fast Atomic Broadcast over RDMAProceedings of the 51st International Conference on Parallel Processing10.1145/3545008.3545041(1-11)Online publication date: 29-Aug-2022
https://dl.acm.org/doi/10.1145/3545008.3545041
Show More Cited By

Index Terms

Group communication specifications: a comprehensive study

Recommendations

Moshe: A group membership service for WANs

We present Moshe, a novel scalable group membership algorithm built specifically for use in wide area networks (WANs), which can suffer partitions. Moshe is designed with three new significant features that are important in this setting: it avoids ...
Group Communication in Partitionable Systems: Specification and Algorithms

We give a formal specification and an implementation for a partitionable group communication service in asynchronous distributed systems. Our specification is motivated by the requirements for building partition-aware applications that can continue ...
Formalized structured analysis specifications

Reviews

Reviewer: Ashoke Deb

Distributed systems involving communication among groups of non-adversarial processes have recently received much interest. Two of the most important aspects of such a system are group membership services (because the membership is dynamic) and multicast services (because consistency, reliability, fault tolerance, and similar features are of concern). Group communication specifications (GCSs) provide building blocks for the construction of reliable and versatile distributed group communication systems. Currently, there are several such GCS systems proposed and implemented, namely Isis, Horus, Ensemble, Relacs, and so on. In the absence of a unified, rigorous, and systematic approach to specifying these various GCSs, it is difficult to compare, contrast, analyze, or validate their respective claims and properties. To research this paper, Chockler, Keider, and Vitenberg surveyed roughly 30 recent papers on the topic of GCS. They present a “comprehensive set of rigorously defined properties of GCSs that reflect the usefulness and nontriviality of the existing GCSs.” The authors’ specification is modular in nature, meaning that the specification of parts can be combined together to give the specification of the whole, thus contributing to the (relative) simplicity and ease of validation of the specifications themselves. The authors model each component of the system as an untimed I/O automata whose input and output actions describe its external signature. A sequence of these actions (fair trace) describes the component’s behavior. A service specification is modeled as a set of acceptable fair traces, presented as an axiom. Based on this model, the authors present the safety properties of the membership service (which includes some basic properties, such as self inclusion, local monotonicity, and primary component membership), and the safety properties of the multicast service (including basic properties such as delivery integrity, no duplication, sending view delivery, and virtual synchrony). In dealing with liveness properties, the authors extend the external signature model by augmenting the original definition with actions that model change in the connection pattern. Liveness properties are given for partitionable GCSs. Two types of liveness properties are dealt with: properties that are conditional upon the existence of stable components, and properties where there is no stable component. In general, the paper is well written, with good references to recent literature. An uninitiated reader may notice the lack of a strong motivation, and of some definitions. Overall, I recommend the paper. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM Computing Surveys Volume 33, Issue 4

December 2001

132 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/503112

Issue’s Table of Contents

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 December 2001

Published in CSUR Volume 33, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

451
Total Citations
View Citations
7,604
Total Downloads

Downloads (Last 12 months)285
Downloads (Last 6 weeks)37

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Iyer RKalbarczyk ZNakka N(2024)Reliable Networked and Distributed SystemsDependable Computing10.1002/9781119743453.ch8(337-411)Online publication date: 26-Apr-2024
https://doi.org/10.1002/9781119743453.ch8
Zhang MMa THua JLiu ZChen KDing NDu FJiang JMa TWu YDruschel PKaufmann AMace JFlinn JSeltzer M(2023)Partial Failure Resilient Memory Management System for (CXL-based) Distributed Shared MemoryProceedings of the 29th Symposium on Operating Systems Principles10.1145/3600006.3613135(658-674)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3600006.3613135
Izraelevitz JWang GHanscom RSilvers KLehman TChockler GGotsman A(2022)Acuerdo: Fast Atomic Broadcast over RDMAProceedings of the 51st International Conference on Parallel Processing10.1145/3545008.3545041(1-11)Online publication date: 29-Aug-2022
https://dl.acm.org/doi/10.1145/3545008.3545041
Barcelona-Pons DSutra PSánchez-Artigas MParís GGarcía-López P(2022)Stateful Serverless Computing with CrucialACM Transactions on Software Engineering and Methodology10.1145/349038631:3(1-38)Online publication date: 7-Mar-2022
https://dl.acm.org/doi/10.1145/3490386
Abusalah BSchatzlein DStephen JArdekani MEugster P(2022)Multi-Framework Reliability ApproachIEEE Transactions on Cloud Computing10.1109/TCC.2021.306590610:4(2750-2768)Online publication date: 1-Oct-2022
https://doi.org/10.1109/TCC.2021.3065906
Duan SZhang H(2022)Foundations of Dynamic BFT2022 IEEE Symposium on Security and Privacy (SP)10.1109/SP46214.2022.9833787(1317-1334)Online publication date: May-2022
https://doi.org/10.1109/SP46214.2022.9833787
Li JYu TWang YWattenhofer R(2022)Dynamic Byzantine Broadcast in Asynchronous Message-Passing SystemsIEEE Access10.1109/ACCESS.2022.320262710(91372-91384)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3202627
Spanakis ESfakianakis SBonomi SCiccotelli CMagalini SSakkalis V(2021)Emerging and Established Trends to Support Secure Health Information ExchangeFrontiers in Digital Health10.3389/fdgth.2021.6360823Online publication date: 9-Apr-2021
https://doi.org/10.3389/fdgth.2021.636082
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
Kolesnikov V(2021)The Design of Customizable Distributed Algorithms for InDiGO FrameworkIntelligent Computing10.1007/978-3-030-80119-9_17(311-325)Online publication date: 13-Jul-2021
https://doi.org/10.1007/978-3-030-80119-9_17
Show More Cited By

View Options

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

Moshe: A group membership service for WANs

Group Communication in Partitionable Systems: Specification and Algorithms

Formalized structured analysis specifications

Reviews

Access critical reviews of Computing literature here