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.

Published in:
2009 28Th Ieee International Symposium On Reliable Distributed Systems, Proceedings, 3-11
Presented at:
28th IEEE International Symposium on Reliable Distributed Systems, Niagara Falls, NY, Sep 27-30, 2009
Ieee Computer Soc Press, Customer Service Center, Po Box 3014, 10662 Los Vaqueros Circle, Los Alamitos, Ca 90720-1264 Usa

 Record created 2010-11-30, last modified 2019-03-16

Publisher's version:
Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)