The inherent price of indulgence
An indulgent algorithm is a distributed algorithm that tolerates asynchronous periods of the network when process crash detection is unreliable. This paper presents a tight bound on the time complexity of indulgent consensus algorithms. We consider a round-based eventually synchronous model, and we show that any t-resilient consensus algorithm in this model, requires at least t + 2 rounds for a global decision even in runs that are synchronous. We contrast our lower bound with the well-known t + 1 round tight bound on consensus in the synchronous model. We then prove the bound to be tight by exhibiting a new t-resilient consensus algorithm in the eventually synchronous model that reaches a global decision at round t + 2 in every synchronous run. Our new algorithm is in this sense significantly faster than the most efficient indulgent algorithm we know of, which requires 2t + 2 rounds in synchronous runs. Our lower bound applies to round-based consensus algorithms with unreliable failure detectors such as lozenge P and lozenge S, and our matching algorithm can be adapted to such failure detectors.
distributed algorithms fault tolerance consensus time complexity