NDLI: Specifying and using a partitionable group communication service

Content Provider	ACM Digital Library
Author	Fekete, Alan Shvartsman, Alex Lynch, Nancy
Copyright Year	2001
Abstract	Group communication services are becoming accepted as effective building blocks for the construction of fault-tolerant distributed applications. Many specifications for group communication services have been proposed. However, there is still no agreement about what these specifications should say, especially in cases where the services are $\textit{partitionable},$ i.e., where communication failures may lead to simultaneous creation of groups with disjoint memberships, such that each group is unware of the existence of any other group. In this paper, we present a new, succinct specification for a view-oriented partitionable group communication service. The service associates each message with a particular $\textit{view}$ of the group membership. All send and receive events for a message occur within the associated view. The service provides a total order on the messages within each view, and each processor receives a prefix of this order. Our specification separates safety requirements from performance and fault-tolerance requirements. The safety requirements are expressed by an abstract, global state machine. To present the performance and fault-tolerance requirements, we include failure-status input actions in the specification; we then give properties saying that consensus on the view and timely message delivery are guaranteed in an execution provided that the execution $\textit{stabilizes}$ to a situation in which the failure-status stops changing and corresponds to consistently partioned system. Because consensus is not required in every execution, the specification is not subject to the existing impossibility results for partionable systems. Our specification has a simple implementation, based on the membership algorithm of Christian and Schmuck. We show the utility of the specification by constructing an ordered-broadcast application, using an algorithm (based on algorithms of Amir, Dolev, Keidar, and others) that reconciles information derived from different instantiations of the group. The application manages the view-change activity to build a shared sequence of messages, i.e., the per-view total orders of the group service are combined to give a universal total order. We prove the correctness and analyze the performance and fault-tolerance of the resulting application.
Starting Page	171
Ending Page	216
Page Count	46
File Format	PDF
ISSN	07342071
e-ISSN	15577333
DOI	10.1145/377769.377776
Volume Number	19
Issue Number	2
Journal	ACM Transactions on Computer Systems (TOCS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2001-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Composable building blocks Conditional performance analysis Distributed algorithms Group communication protocols Message-passing protocols Ordered broadcast Service specification Total-order broadcast
Content Type	Text
Resource Type	Article
Subject	Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Specifying and Using a Partitionable Group Communication Service (1999)

Specifying and Using a Partitionable Group Communication Service (2000)

Specifying and Using a Partitionable Group Communication Service (1998)

Specifying and Using a Partitionable Group Communication Service (1997)

Specifying and Using a Partitionable Group Communication Service (1997)

Totally ordered broadcast in the face of network partitions. Exploiting group communication for replication in partitionable networks (1999).

Total order broadcast and multicast algorithms: Taxonomy and survey

Chapter TOTALLYORDERED BROADCAST IN THE FACE OF NETWORK PARTITIONS Exploiting Group Communication for Replication in Partitionable Networks

Specifying and using a partitionable group communication service.

Specifying and using a partitionable group communication service

Similar Documents

Specifying and Using a Partitionable Group Communication Service (1999)

Specifying and Using a Partitionable Group Communication Service (2000)

Specifying and Using a Partitionable Group Communication Service (1998)

Specifying and Using a Partitionable Group Communication Service (1997)

Specifying and Using a Partitionable Group Communication Service (1997)

Totally ordered broadcast in the face of network partitions. Exploiting group communication for replication in partitionable networks (1999).

Total order broadcast and multicast algorithms: Taxonomy and survey

Chapter TOTALLYORDERED BROADCAST IN THE FACE OF NETWORK PARTITIONS Exploiting Group Communication for Replication in Partitionable Networks

Specifying and using a partitionable group communication service.

Specifying and using a partitionable group communication service