An optimal early stopping uniform consensus protocol in synchronous distributed systems with orderly crash failures

Most existing consensus protocols for synchronous distributed systems are designed to tolerate crash failures of processes. It has been proved that there is no n-process stopping consensus protocol for synchronous distributed systems that tolerates up to t crash failures, in which all non-faulty processes always decide by the end of round t, where t < n-1 and n is the total number of processes, t is the maximum number of failures that can occur. Furthermore, the well-known lower bound, min (t+1, f+2), has been proved for early stopping synchronous consensus protocols, where f ≤ t, and f is the number of failures that actually occur in the system. In this paper, we propose a consensus protocol for synchronous distributed systems with orderly crash failures [4], which is both time and message efficient than those existing protocols applied in this failure model. The proposed protocol achieves uniform consensus and tolerates up to t failures, in which all non-faulty processes always make decision and stop immediately by the end of f+1 rounds, where t < n, f ≤ t. When there is no failure, the protocol can achieve uniform consensus and stop within one round. We prove that the lower bounds of early stopping protocols for both consensus and uniform consensus in orderly crash failure model are f+1 rounds, which ensure our proposed protocol is optimal.