Reliable and Total Order Broadcast in the Crash-Recovery Model

This paper addresses the problem of broadcasting messages in a reliable and totally ordered manner when processes and channels may crash and recover, or crash and never recover. We present a suite of specifications of reliable and total order broadcast primitives and we describe algorithms that implement those specifications. Our approach is modular and incremental. It is modular in the sense that the properties of broadcast primitives are first given separately and then composed: this provides a comprehensive design space for broadcast semantics. It is incremental in the sense that a broadcast algorithm implementing a given specification is obtained by transforming an algorithm that implements a weaker specification: this gives an automatic way to improve the resilience of broadcast primitives. We derive specific reliable and total order broadcast algorithms and we discuss their performance and optimality. Keywords:reliable broadcast, total order broadcast, modularity,transformation, optimisation, crash-recovery model.