Consensus-Based Fault-Tolerant
Udo Fritzke, Philippe Ingels, Achour Mostéfaoui, Michel Raynal · 2001
While Broadcast (or Atomic Broadcast ) primitives have received a lot of attention, this paper concentrates on to Multiple in the context of asynchronous distributed systems in which processes may suffer crash failures. Multicast to Multiple Groups means that each message is sent to a subset of the process groups composing the system, distinct messages possibly having distinct destination groups. Total Order 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 protocol is based on two underlying building blocks, namely, Uniform Reliable and Uniform Consensus. Its design characteristics lie in the two following 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 property is a Locality property: No execution of a consensus has to involve processes belonging to distinct groups (i.e., consensus is executed on a per basis). This Locality property is particularly useful when one is interested in using the primitive in large-scale distributed systems. In addition to a correctness proof, an improvement that reduces the cost of the protocol is also suggested. Index Terms—Asynchronous systems, consensus, groups, reliable multicast, total order, group multicast.