One-step Consensus with Zero-Degradation

Abstract

In the asynchronous distributed system model, consensus is obtained in one communication step if all processes propose the same value. Assumingf \lt n/3, this is regardless of the failure detector output. A zero-degrading protocol reaches consensus in two communication steps in every stable run, i.e., when the failure detector makes no mistakes and its output does not change. We show that no leaderbased consensus protocol can be simultaneously one-step and zero-degrading. We propose two approaches to circumvent the impossibility result and present corresponding consensus protocols. Further, we present an atomic broadcast protocol that has a latency of 3d in every stable run and a latency of 2d in case of no collisions. Finally, we evaluate its performance in a cluster of workstations.