Abstract
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 ⋄ P and ⋄ S, and our matching algorithm can be adapted to such failure detectors.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aguilera, M.K., Toueg, S.: A simple bivalency proof that t-resilient consensus requires t+1 rounds. Inform. Proces. Lett. 71(3-4), 155-158 (1999)
Chandra, T.D., Toueg, S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43(2), 225-267 (1996)
Charron-Bost, B., Guerraoui, R., Schiper, A.: Synchronous system and perfect failure detector: solvability and efficiency issues. In: Proceedings of the IEEE International Conference on Dependable Systems and Networks (DSN), pp. 523-532 New York (2000)
Charron-Bost, B., Schiper, A.: Uniform consensus harder than consensus. DSC Technical Report 2000-28, Department of Communication Systems, Swiss Federal Institute of Technology, Lausanne (2000)
Dutta, P., Guerraoui, R., Pochon, B.: Tight bounds on early local decisions in uniform consensus. In: Proceedings of the 17th International Conference on Distributed Computing (DISC), Sorrento, Italy (2003)
Dwork, C., Lynch, N.A., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288-323 (1988)
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374-382 (1985)
Gafni, E.: Round-by-round fault detectors: Unifying synchrony and asynchrony. In: Proceedings of the 17th ACM Symposium on Principles of Distributed Computing (PODC-17), pp. 143-152 Puerto Vallarta, Mexico (1998)
Guerraoui, R.: Indulgent algorithms. In: Proceedings of the 19th ACM Symposium on Principles of Distributed Computing (PODC-19), pp. 289-298 Portland, OR (2000)
Hurfin, M., Raynal, M.: A simple and fast asynchronous consensus protocol based on a weak failure detector. Distribut. Comput. 12(4), 209-223 (1999)
Keidar, I., Rajsbaum, S.: A simple proof of the uniform consensus synchronous lower bound. Inform. Process. Lett. 85(1), 47-52 (2003); A preliminary version appeared in SIGACT News 32(2), 45-63 (2001)
Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. Program. Languages Syst. 4(3), 382-401 (1982)
Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann (1996)
Mostefaoui, A., Raynal, M.: Leader-based consensus. Parallel Proce. Lett. 11(1), 95-107 (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is partially supported by the Swiss National Science Foundation (project number 510-207).
Rights and permissions
About this article
Cite this article
Dutta, P., Guerraoui, R. The inherent price of indulgence. Distrib. Comput. 18, 85–98 (2005). https://doi.org/10.1007/s00446-005-0124-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00446-005-0124-9