Relaxed Atomic Broadcast: State-Machine Replication Using Bounded Memory

Atomic broadcast is a useful abstraction for implementing fault-tolerant distributed applications such as state-machine replication. Although a number of algorithms solving atomic broadcast have been published, the problem of bounding the memory used by these algorithms has not been given the attention it deserves. It is indeed impossible to solve repeated atomic broadcast with bounded memory in a system (non-synchronous or not equipped with a perfect failure detector) in which consensus is solvable with bounded memory. The intuition behind this impossibility is the inability to safely garbage-collect unacknowledged messages, since a sender process cannot tell whether the destination process has crashed or is just slow.The usual technique to cope with this problem is to introduce a membership service, allowing the exclusion of a slow or silent process from the group and safely discarding unacknowledged messages sent to this process. In this paper,we present a novel solution that does not rely on a membership service. We relax the specification of atomic broadcast so that it can be implemented with bounded memory, while being strong enough to still be useful for applications that use atomic broadcast, e.g., state-machine replication.