Byzantine-Resistant total ordering algorithms

Multicast group communication protocols are used extensively in fault-toler ant distributed systems. For many such protocols, the acknowledgments for i ndividual messages define a causal order on messages. Maintaining the consi stency of information, replicated on several processors to protect it again st faults, is greatly simplified by a total order on messages. We present a lgorithms that incrementally convert a causal order on messages into a tota l order and that tolerate both crash and Byzantine process faults. Varying compromises between latency to message ordering and resilience to faults yi eld four distinct algorithms. All of these algorithms use a multistage voti ng strategy to achieve agreement on the total order and exploit the random structure of the causal order to ensure probabilistic termination. (C) 1999 Academic Press.