An optimal early stopping uniform consensus protocol in synchronous distributed systems with orderly crash features
Xianbing Wang, Jiannong Cao · 2004
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/spl les/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