Consensus-based fault-tolerant total order multicast

While Total Order Broadcast (or Atomic Broadcast) primitives have received a lot of attention, this paper concentrates on Total Order Multicast to Mul tiple Groups in the context of asynchronous distributed systems in which pr ocesses may suffer crash failures. "Multicast to Multiple Groups" means tha t each message is sent to a subset of the process groups composing the syst em, distinct messages possibly having distinct destination groups. "Total O rder" means that all message deliveries must be totally ordered. This paper investigates a consensus-based approach to solve this problem and proposes a corresponding protocol to implement this multicast primitive. This proto col is based on two underlying building blocks, namely, Uniform Reliable Mu lticast and Uniform Consensus. Its design characteristics lie in the two fo llowing properties: The first one is a Minimality property, more precisely, only the sender of a message and processes of its destination groups have to participate in the total order multicast of the message. The second prop erty is a Locality property: No execution of a consensus has to involve pro cesses belonging to distinct groups (i.e., consensus is executed on a "per group" basis). This Locality property is particularly useful when one is in terested in using the Total Order Multicast primitive in large-scale distri buted systems. In addition to a correctness proof, an improvement that redu ces the cost of the protocol is also suggested.