A lightweight solution to uniform atomic broadcast for asynchronous systems

Chandra and Toueg (1993) proposed a new approach to overcome the impossibility of reaching deterministically Consensus-and by corollary Atomic Broadcast-in asynchronous systems subject to crash failures. They augment the asynchronous system with a possibly Unreliable Failure Detector which provides some information about the operational state of processes. In this paper, we present an extension of the Consensus problem that we call Uniform Prefix Agreement. This extension enables all the processes to propose a flow of messages during an execution-instead of one as in the Consensus problem-and uses all these proposed messages to compose its decision value. Prefix Agreement is based on an Unreliable Failure Detectors. We use repeated executions of Prefix Agreement to build an efficient and lightweight Uniform Atomic Broadcast algorithm. This paper describes the Uniform Prefix Agreement and Uniform Atomic Broadcast algorithms.