New asynchronous atomic broadcast protocols

Abstract

Summary form only given. Three protocols are presented for atomically broadcasting updates to the global state of a highly available service implemented by a team of replicated processes. The protocols are designed for asynchronous systems where no upper bounds exist on message transmission and process scheduling delays. The first protocol, the Majority Agreement protocol, ensures that all team members that are currently joined to a majority group agree on a unique history of global state updates. The protocol does not prevent processes joined to minority groups from disagreeing with the history of the majority. For certain applications, such disagreement is unacceptable. For these, a second protocol, called Strict Agreement, which guarantees that any correct team member (whether joined to a majority or minority group) has at any time a consistent view of the history of broadcast updates, is proposed. The price paid by the first two protocols for ensuring history unicity is that processes joined to minority groups cannot broadcast updates. This can be unacceptable for certain other applications, for which the cost of freezing activity in minority groups is higher than the cost of compensating for actions taken by members of these groups while isolated from a team member majority. For this last class of applications, a third protocol, called Group Agreement, which sacrifices the unique history requirement in exchange for making state updates available even to processes joined to minority groups, is proposed. The tradeoffs between safety and timeliness properties in distributed systems are made apparent by the protocols.