Group Communication Specifications: A Comprehensive StudyGREGORY V. CHOCKLERThe Hebrew University of Jerusalem Computer Science InstituteIDIT KEIDARMIT Laboratory for Computer ScienceANDROMAN VITENBERGThe Technion Department of Computer ScienceView-oriented group communication is an important and widely used building block formany distributed applications. Much current research has been dedicated to specifyingthe semantics and services of view-oriented group communication systems (GCSs).However, the guarantees of different GCSs are formulated using varying terminologiesand modeling techniques, and the specifications vary in their rigor. This makes itdifficult to analyze and compare the different systems. This survey provides acomprehensive set of clear and rigorous specifications, which may be combined torepresent the guarantees of most existing GCSs. In the light of these specifications, over30 published GCS specifications are surveyed. Thus, the specifications serve as aunifying framework for the classification, analysis, and comparison of groupcommunication systems. The survey also discusses over a dozen different applicationsof group communication systems, shedding light on the usefulness of the presentedspecifications. This survey is aimed at both system builders and theoretical researchers.The specification framework presented in this article will help builders of groupcommunication systems understand and specify their service semantics; the extensiveCategories and Subject Descriptors: C.2.4 [Computer-Communication Networks]:Distributed Systems; D.4.7 [Operating Systems]: Organization and Design—distributed systems; F.3.1 [Logics and Meanings of Programs]: Specifying andVerifying and Reasoning about Programs—specification techniques; C.2.1[Computer-Communication Networks]: Network Architecture and Design—network communicationsGeneral Terms: Algorithms, Reliability, StandardizationAdditional Key Words and Phrases: Group communication systems, partitionable groupmembership, process group membership, specifications of group communicationsystems, view synchrony, virtual synchronyThis work is supported by Air Force Aerospace Research (OSR) grant F49620-00-1-0097, Nippon Telegraphand Telephone (NTT) grant MIT9904-12, and by NSF grants ACI-9876931, CCR-9909114, and EIA-9901592.Authors’ addresses: G. V. Chockler, Givat Ram, Jerusalem, 91904 Israel; email: [email protected];I. Keidar, 545 Technology Square, Cambridge, MA, 02139; email: [email protected]; R. Vitenberg,Technion City, Haifa 32000, Israel; email: [email protected] to make digital/hard copy of part or all of this work for personal or classroom use is grantedwithout fee provided that the copies are not made or distributed for profit or commercial advantage, thecopyright notice, the title of the publication, and its date appear, and notice is given that copying is bypermission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists,requires prior specific permission and/or a fee.c°2001 ACM 0360-0300/01/1200–0427 $5.00ACM Computing Surveys, Vol. 33, No. 4, December 2001, pp. 427–469.428 G.V. Chockler et al.survey will allow them to compare their service to others. Application builders will finda guide here to the services provided by a large variety of GCSs, which could help themchoose the GCS appropriate for their needs. The formal framework may provide a basisfor interesting theoretical work, for example, analyzing relative strengths of differentproperties and the costs of implementing them.CONTENTS1. INTRODUCTION1.1 Unifying the GCS Properties1.2 The Specification Style1.3 The Difficulties of FormallySpecifying GCSs1.4 Roadmap to this SurveySAFETY PROPERTIES OF GROUPCOMMUNICATION SERVICES2. THE MODEL AND PRESENTATIONFORMALISM2.1 The Specification Framework2.2 The External Signature of the GCSService2.3 The Mathematical Model2.4 Notation2.5 Assumptions About the Environment3. SAFETY PROPERTIES OFTHE MEMBERSHIP SERVICE3.1 Basic Properties3.2 Partitionable Versus PrimaryComponent Membership Services4. SAFETY PROPERTIES OF THEMULTICAST SERVICE4.1 Basic Properties4.2 Sending View Delivery and WeakerAlternatives4.3 The Virtual Synchrony Property5. SAFE MESSAGES6. ORDERING AND RELIABILITYPROPERTIES6.1FIFO Multicast6.2 Casual Multicast6.3 Totally Ordered Multicast6.4 Order Constraints for Messages ofDifferent Types6.5 Order Constraints for MultipleGroupsLIVENESS PROPERTIES OF GROUPCOMMUNICATION SERVICES7. INTRODUCTION8. REFINING THE MODEL TO REASONABOUT LIVENESS8.1 Extending the GCS ExternalSignature8.2 Assumption: Live Network8.3 Stable Components8.4 Eventually Perfect Failure Detectors9. PRECISE MEMBERSHIP IS AS STRONGAS ¦P10. LIVENESS PROPERTIES10.1 Liveness Properties for Stable Runs10.2 Additional Liveness Properties10.3 Related WorkCONCLUSIONS11. SUMMARYAPPENDIX A: PROVING A RELATIONSHIPBETWEEN DIFFERENT PROPERTIESREFERENCES1. INTRODUCTIONGroup communication is a means for pro-viding multipoint to multipoint communi-cation, by organizing processes in groups.A group is a set of processes that are mem-bers of the group. For example, a group canconsist of users playing an online gamewith each other. Another group can con-sist of participants in a multimedia con-ference. Each group is associated with alogical name. Processes communicate withgroup members by sending a message tothe group name; the group communicationservice delivers the message to the groupmembers.In this survey, we focus on view-orientedgroup communication systems (GCSs).Such systems provide membership andreliable multicast services. The task ofa membership service is to maintain alist of the currently active and connectedprocesses in a group. The output of themembership service is called a view. Thereliable multicast services deliver mes-sages to the current view members. Thefirst and best known GCS was devel-oped as part of the Isis toolkit [Birman1986]; it was followed by over a dozenothers.ACM Computing Surveys, Vol. 33, No. 4, December 2001.Group Communication Specifications 429GCSs are powerful building blocksthat facilitate the development offault-tolerant distributed systems. Clas-sical GCS applications include replicationusing a variant of the state machine/activereplication approach [Lamport 1978;Schneider 1990] (e.g., Keidar and Dolev[1996], Amir et al. [1994] Fekete et al.[1997], Friedman and Vaysburg [1997],and Montresor et al. [2000]); primary-backup
View Full Document
Unlocking...