Asynchronous Fault-Tolerant Total Ordering Algorithms

Abstract

Two novel efficient algorithms for placing a total order on messages in an asynchronous fault-tolerant distributed system are presented. The algorithms are resilient to fewer than ${n / 3}$ and ${n / 2}$ faulty processes in an n-process system. Partial correctness and probabilistic termination are demonstrated; it is also shown that there does not exist a total ordering algorithm that is guaranteed to terminate. A comparison of the complexity of the algorithms is given.