Dynamic Group Communication

Group communication is the basic infrastructure for implementing fault-tolerant replicated servers. While group communication is well understood in the context of static systems (in which all processes are created at the start of the computation), current specifications of dynamic group communication (in which processes can be added and removed during the computation) are not satisfactory. The paper proposes new specifications for dynamic reliable broadcast (which we call reliable multicast), dynamic atomic broadcast (which we call atomic multicast) and group membership. In the special case of a static system, our specifications are identical to the well known static specifications. The specification of group membership is derived from the specification of atomic multicast. The paper also shows how to solve atomic multicast, group membership and reliable broadcast. The solution of atomic multicast is close to the (static) atomic broadcast solution based on reduction to consensus. Group membership is solved using atomic multicast. In the context of reliable multicast, we introduce the notion of thrifty solution, and show that such a solution can be obtained by relying on a thrifty generic multicast algorithm