Reliable and total order broadcast in the crash-recovery model

This paper addresses the problems of broadcasting messages in a reliable and totally ordered manner assuming a crash-recovery model, i.e., a model where processes and channels may crash and possibly recover. We present a suite of specifications of reliable and total order broadcast abstractions for this model and we describe algorithms that implement those specifications. The properties of broadcast abstractions are first given separately and then composed: this provides a comprehensive design space for broadcast semantics. The algorithms we give are efficient both in terms of time-complexity (communication steps) and log-complexity (disk accesses).