Solving Agreement Problems with Weak Ordering OraclessSolving Agreement • September 11th, 2002
Abstract. Agreement problems, such as consensus, atomic broadcast, and group membership, are central to the implementation of fault-tol- erant distributed systems. Despite the diversity of algorithms that have been proposed for solving agreement problems in the past years, almost all solutions are Crash-Detection Based (CDB ). We say that an algorithm is CDB if it uses some information about the status crashed /not crashed of processes. In this paper, we revisit the issue of non-CDB algorithms considering ordering oracles. Ordering oracles have a theoretical interest as well as a practical interest. To illustrate their use, we present solutions to consensus and atomic broadcast, and evaluate the performance of the atomic broadcast algorithm in a cluster of workstations.
