Roberto De Prisco, Alan Fekete, Nancy Lynch, and Alex Shvartsman. A Dynamic View-Oriented Group Communication Service. Proceedings of the 17th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC'98), Puerto Vallarta, Mexico, June-July, 1998.

Abstract

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 view of the current group membership that is primary, usually defined as a view containing a majority out of a static universe of processes. For high availability in a system where processes can join and leave routinely, some researchers have suggested defining primary views in a dynamic way, depending on having enough members in common with recent views.

We present a new formal specification, DVS, for the safety guarantees made by a practical group communication service providing a dynamic notion of primary view. The specification is a simple automaton, with only seven kinds of actions. We demonstrate the value of the DVS specification by showing both how it can be implemented and how it can be used in an application. Both pieces are shown formally, with assertional proofs.

First, we consider an implementation that is a variant of the group membership algorithm of Lotem, Keidar, and Dolev [LKD97]. Our variant integrates communication with the membership service, uses information from the application processes saying when a view has been adequately prepared for computation by the application, and uses a static view-oriented service internally. We prove that this algorithm implements DVS, in the sense of trace inclusion.

Second, we consider an application algorithm that is a variant of an algorithm in [ADMM94,FLS97,KD96], modified to use DVS instead of a static view-oriented service. We show that it implements a (non-group-oriented) totally-ordered-broadcast service.

Because of its simplicity, we believe that DVS will be easy to use for other applications.

References

[LKD97] E. Lotem, I Keidar and D. Dolev, ``Dynamic voting for consistent primary components'', in Proc. of the 16th Annual ACM Symposium on Principles of Distributed Computing, Santa Barbara, CA, August 1997, pp. 63-71.

[ADMM94] Y. Amir, D. Dolev, P. Melliar-Smith and L. Moser, ``Robust and Efficient Replication Using Group Communication'', Technical Report 94-20, Department of Computer Science, Hebrew University, 1994.

[FLS97] A. Fekete, N. Lynch and A. Shvartsman ``Specifying and using a partitionable group communication service'', in Proc. of the 16th annual ACM Symposium on Principles of Distributed Computing, Santa Barbara, CA, August 1997, pp. 53-62.

[KD96] I. Keidar and D. Dolev, ``Efficient Message Ordering in Dynamic Networks'', in Proc. of 15th Annual ACM Symp. on Principles of Distributed Computing, pp. 68-76, 1996.