Fast Indulgent Consensus with Zero Degradation

This paper describes a new consensus algorithm for the asynchronous message passing system model augmented with an unreliable failure detector abstraction: channels are reliable, processes can fail by crashing, and the detection of crashes are not reliable. Our algorithm (a) matches all known consensus lower bounds on (1) failure detection, i.e., \Omega, (2) resilience, i.e., a majority of correct processes, and (3) latency, i.e., two communication steps for a global decision in nice runs (when no process crashes and the failure detection is reliable), and (b) has the following zero degradation flavor: in every stable run of the algorithm (when all failures are initial crashes, and failure detection is reliable), two communication steps are sufficient to reach a global decision. The zero degradation flavor is particularly important when consensus is used in a repeated form: failures in one consensus instance do not impact performance of future consensus instances. We describe our algorithm informally as well as in a detailed way, and then we give two additional variants of our algorithm, both preserving the zero degradation flavor: (1) a variant that reaches a global decision in one communication step in stable runs if all correct processes propose the same privileged value, and (2) a variant that uses a S failure detector (instead of \Omega ). Roughly speaking, these variants convey the very fact that our technique to obtain zero degradation can be applied in various contexts.