Crash-tolerant causal broadcast in O(n) messages

Causal broadcast is a communication abstraction designed for asynchronous systems. It ensures that the messages broadcast by the processes are delivered in their broadcast causality order, namely, if the broadcast of a message m causally precedes the broadcast of a message m^′, no process delivers m^′ unless it has previously delivered m. Several algorithms implementing causal broadcast have been proposed for asynchronous systems prone to any number of process crashes. These algorithms rely on an underlying Reliable Broadcast abstraction, whose message cost is n². This paper presents a simple causal broadcast algorithm whose cost is n messages per causal broadcast. This is obtained at the cost of protocol messages whose size can be up to n application messages.