The Inherent Price of Indulgence
This paper presents a tight lower bound on the time complexity of indulgent consensus algorithms, i.e., consensus algorithms that use unreliable failure detectors. We state and prove our tight lower bound in the unifying framework of round-by-round fault detectors. We show that any P -based t-resilient consensus algorithm requires at least t+2 rounds for a global decision even in runs that are synchronous. We then prove the bound to be tight by exhibiting a new P-based t-resilient consensus algorithm 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 knew of (which requires 2t + 2 rounds). We contrast our lower bound with the well-known t + 1 round tight lower bound on consensus for the synchronous model, pointing out the price of indulgence.
Publisher's version.pdf
Publisher's version
openaccess
1.28 MB
Adobe PDF
5d094a8eabf5e25b2541be311f03b9e1
IC_TECH_REPORT_200231.pdf
openaccess
296.34 KB
Adobe PDF
677739b5f957b6c1727192b0da675df0