Specifying and using a partitionable group communication service

Group communication services are becoming accepted as effective building bl ocks 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, e specially in cases where the services are partitionable, i.e., where commun ication failures may lead to simultaneous creation of groups with disjoint memberships, such that each group is unaware of the existence of any other group. In this paper, we present a new, succinct specification for a view-o riented partitionable group communication service. The service associates e ach message with a particular view of the group membership. All send and re ceive events for a message occur within the associated view. The service pr ovides a total order on the messages within each view, and each processor r eceives a prefix of this order. Our specification separates safety requirem ents from performance and fault-tolerance requirements. The safety requirem ents are expressed by an abstract, global state machine. To present the per formance 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 pro vided that the execution stabilizes to a situation in which the failure-sta tus stops changing and corresponds to a consistently partitioned system. Be cause consensus is not required in every execution, the specification is no t subject to the existing impossibility results for partitionable systems. Our specification has a simple implementation, based on the membership algo rithm of Cristian 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 manage s the view-change activity to build a shared sequence of messages, i.e., th e per-view total orders of the group service are combined to give a univers al total order. We prove the correctness and analyze the performance and fa ult-tolerance of the resulting application.