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