Total ordering algorithms
Louise E. Moser, Peter Michael Melliar-Smith, Vivek Agrawala · 1991
We present novel efficient algorithms for placing a total order on messages in an asynchronous faulttolerant distributed system.These algorithms are resilient to fewer than r~/3 and r~/2 faulty processors in a system with n-processors, and are intended for use in a local area network that is based on broadcast communication, such as an Ethernet or a token ring.For each algorithms partial correctness and probabilistic termination can be demonstrated; we can also show that there does not exist a total ordering algorithm that is guaranteed to terminate.A comparison of the complexity of the two algorithms is given.