Abstract
The unbeatability of a consensus protocol, introduced by Halpern, Moses and Waarts in [15], is a stronger notion of optimality than the accepted notion of early stopping protocols. Using a novel knowledge-based analysis, this paper derives the first practical unbeatable consensus protocols in the literature, for the standard synchronous message-passing model with crash failures. These protocols strictly dominate the best known protocols for uniform and for non-uniform consensus, in some case beating them by a large margin. The analysis provides a new understanding of the logical structure of consensus, and of the distinction between uniform and nonuniform consensus. Finally, the first (early stopping and) unbeatable protocol that treats decision values “fairly” is presented. All of these protocols have very concise descriptions, and are shown to be efficiently implementable.
A full version of this paper with complete proofs is available on arXiv.org [2].
Part of the results of this paper were announced in [1].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Castañeda, A., Gonczarowski, Y.A., Moses, Y.: Brief announcement: Pareto-optimal solutions to consensus and set consensus. In: PODC, pp. 113–115 (2013)
Castañeda, A., Gonczarowski, Y.A., Moses, Y.: Unbeatable consensus (September 2014), http://arXiv.org
Charron-Bost, B., Schiper, A.: Uniform consensus is harder than consensus. J. Algorithms 51(1), 15–37 (2004)
Coan, B.: A communication-efficient canonical form for fault-tolerant distributed protocols. In: Proc. 5th ACM Symp. on Principles of Distributed Computing, pp. 63–72 (1986)
Dolev, D., Reischuk, R., Strong, H.R.: Early stopping in Byzantine agreement. Journal of the ACM 34(7), 720–741 (1990)
Dolev, D., Strong, H.R.: Requirements for agreement in a distributed system. In: Schneider, H.J. (ed.) Distributed Data Bases, pp. 115–129. North-Holland (1982)
Dolev, D.: Beep protocols (personal communication)
Dutta, P., Guerraoui, R., Pochon, B.: The time-complexity of local decision in distributed agreement. SIAM J. Comput. 37(3), 722–756 (2007)
Dwork, C., Moses, Y.: Knowledge and common knowledge in a Byzantine environment: crash failures. Information and Computation 88(2), 156–186 (1990)
Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M.Y.: Reasoning about Knowledge. MIT Press (2003)
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty processor. Journal of the ACM 32(2), 374–382 (1985)
Gafni, E., Guerraoui, R., Pochon, B.: The complexity of early deciding set agreement. SIAM J. Comput. 40(1), 63–78 (2011)
Hadzilacos, V.: On the relationship between the atomic commitment and consensus problems. In: Simons, B., Spector, A. (eds.) Fault-Tolerant Distributed Computing. LNCS, vol. 448, pp. 201–208. Springer, Heidelberg (1990)
Halpern, J.Y., Moses, Y.: Knowledge and common knowledge in a distributed environment. Journal of the ACM 37(3), 549–587 (1990), a preliminary version appeared in PODC (1984)
Halpern, J.Y., Moses, Y., Waarts, O.: A characterization of eventual byzantine agreement. SIAM J. Comput. 31(3), 838–865 (2001)
Herlihy, M., Moses, Y., Tuttle, M.R.: Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions. In: PODC, pp. 231–238 (2011)
Keidar, I., Rajsbaum, S.: A simple proof of the uniform consensus synchronous lower bound. Inf. Process. Lett. 85(1), 47–52 (2003)
Moses, Y., Tuttle, M.R.: Programming simultaneous actions using common knowledge. Algorithmica 3, 121–169 (1988)
Moses, Y.: Knowledge and Distributed Coordination (in preparation)
Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. Journal of the ACM 27(2), 228–234 (1980)
Raynal, M.: Optimal early stopping uniform consensus in synchronous systems with process omission failures. In: SPAA, pp. 302–310. ACM Press (2004)
Wang, X., Teo, Y.M., Cao, J.: A bivalency proof of the lower bound for uniform consensus. Inf. Process. Lett. 96(5), 167–174 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Castañeda, A., Gonczarowski, Y.A., Moses, Y. (2014). Unbeatable Consensus. In: Kuhn, F. (eds) Distributed Computing. DISC 2014. Lecture Notes in Computer Science, vol 8784. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45174-8_7
Download citation
DOI: https://doi.org/10.1007/978-3-662-45174-8_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-45173-1
Online ISBN: 978-3-662-45174-8
eBook Packages: Computer ScienceComputer Science (R0)