ATOMIC BROADCAST: FROM SIMPLE MESSAGE DIFFUSION TO BYZANTINE AGREEMENT

Abstract

In loosely coupled distributed systems subject to random communication delays and component failures, atomic brocrdcart protocols can be used to implement the abstraction of a A-common sfomge, a replicated storage that displays at any clock time the same contents to every correct processor and that requires A time units to complete replicated updates. We term a broadcast protocol atomic if (1) it delivers every message broadcast by a correct sender to all correct receivers within some known time bound (ferminution), (2) it ensures that every message whose broadcast is initiated by a sender is either delivered to all correct receivers or to none of them (ofomicify), and (3) it guarantees that all delivered messages from all senders are delivered in the same order at all receiving nodes (order). This paper presents a famib of atomic broadcast protocols that are tolerant of increasingly general fault classes: ommm fuulfs, which cause a component (processor or communication link) never to deliver a requested service, riming fuulfs, which cause a component to deliver a requested service either too early or too late, and Byanfine fuults, which lead to the delivery of a service other 'than the one requested. The protocols work for arbitrary point-to-point network topologies, can tolerate any number of faults up to network partitioning, use a small number of messages, and achieve in many wes the best possible termination times.