A Dynamic View-Oriented Group Communication Service

Roberto De Prisco, Alan Fekete, Nancy Lynch and Alex Shvartsman

View-oriented group communication services are widely used for fault-tolerant distributed computing. For applications involving coherent data, it is important to know when a process has a {\em primary\/} view of the current group membership, usually defined as a view containing a majority out of a {\em static\/} universe of processes. For high availability in a system where processes can join and leave routinely, some researchers have suggested defining primary views {\em dynamically\/}, depending on having enough members in common with recent views.

We present a new formal automaton specification, \dvs, for the safety guarantees made by a practical group communication service providing a dynamic notion of primary view. We demonstrate the value of \dvs\ by showing both how it can be implemented and how it can be used in an application. First, we present based on a group membership algorithm of Lotem, Keidar and Dolev; our version integrates communication with the membership service, uses information from the application processes saying when a view has been prepared for computation by the application, and uses a static view-oriented service internally. We prove that this algorithm implements \dvs. Second, we present an application algorithm that is a variant of an algorithm of Amir, Dolev, Keidar, Melliar-Smith and Moser, modified to use \dvs\ instead of a static service. We prove that it implements a (non-group-oriented) totally-ordered-broadcast service.

In the Proceedings of PODC'98