Abstract: Chandra and Toueg proposed in 1991 a new approach to overcome the impossibility of reaching deterministically Consensus in asynchronous systems subject to crash failures. They augment the asynchronous system with a possibly Unreliable Failure Detector that provides some information about the processes that may have crashed during an execution of the system.

In this report we present an extension of the Consensus problem that enhances its performance. This extension, that we call Uniform Prefix Agreement, 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. We use our extension to build an efficient and lightweight Uniform Atomic Broadcast algorithm by taking advantage of this improvement. This paper describes the Uniform Prefix Agreement and Uniform Atomic Broadcast algorithms and provides the proofs of their correctness. Performance measurements quantifying this improvement are currently under investigation.

Keywords: Uniform Atomic Broadcast, Uniform Reliable Broadcast, Uniform Prefix Agreement, Asynchronous Systems, Unreliable Failure Detectors, crash failures