Abstract
Reaching agreement in a distributed system is a fundamental issue of both theoretical and practical importance. Consensus and non-blocking atomic commitment are two wellknown versions of this paradigm. The Consensus problem considers a fixed collection of processors each of which has an initial value drawn from some domain V , and processors must eventually decide on the same value1; moreover, the decision value must be the initial value of some processor. The non-blocking atomic commitment (NB-AC) problem arises in distributed database systems to ensure the consistent termination of transactions. Each process that participates in the processing of a database transaction arrives at an initial opinion (vote) about whether to commit the transaction or abort it. Processes must eventually reach a common decision (commit or abort). The decision to commit may be reached only if all processes initially vote to commit. In this case, “commit” must be reached if there is no failure.
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
M. Ben-Or, M. (1983): Another advantage of free choice: Completely asynchronous agreement protocols. PODC, 27–30
Chandra, T. D., Hadzilacos, V, Toueg, S. (1996): The weakest failure detector for solving consensus. JACM 43(4), 685–722
Chandra, T. D., Toueg, S. (1996): Unreliable failure detectors for asynchronous systems. JACM. 43(2), 225–267
Charron-Bost, B. (2001): Agreement problems in fault-tolerant distributed systems. (SOFSEM, LNCS, vol. 2234), 10–32
Charron-Bost, B. (2001): The weakest failure detector for solving atomic commitment. Unpublished Notes
Charron-Bost, B., Le Fessant, F. (2002):Validity conditions in agreement problems and time complexity. Tech. Rep. RR-4526, INRIA-Rocquencourt
Charron-Bost, B., Schiper, A. (2000): Uniform consensus is harder than consensus. Tech. Rep. DSC/2000/028, EPFL
Charron-Bost, B., Toueg, S. (2001): Comparing the atomic commitment and consensus problems. Unpublished Notes
Dolev, D., Reischuk, R., Strong, H. R. (1990): Early stopping in Byzantine agreement. JACM 37(4), 720–741
Dwork, C., Lynch, N. A., Stockmeyer, L. (1988): Consensus in the presence of partial synchrony. JACM 35(2), 288–323
Fischer, M. J., Lynch, N. A., Paterson, M. S. (1985): Impossibility of distributed consensus with one faulty process. JACM 32(2), 374–382
Gray, J. (1987): A comparison of the byzantine agreement problem and the transaction commit problem. (Fault Tolerant Distributed Computing, LNCS vol. 448), 10–17
Guerraoui, R. (1995): Revisiting the relationship between non-blocking atomic commitment and consensus. (WDAG, LNCS vol. 972), 87–100
Guerraoui, R. (2002): Non-blocking atomic commitment in asynchronous systems with failure detectors. Distributed Computing 15(1)
Guerraoui, R., Kouznetsov, P. (2002): On the weakest failure detector for non-blocking atomic commit. International Conference on Theoretical Computer Science
Hadzilacos, V. (1987): On the relationship between the atomic commitment and consensus problems. (Fault Tolerant Distributed Computing, LNCS vol. 448), 201–208
Keidar, I., Rajsbaum, S. (2002):A simple proof of the uniform consensus synchronous lower bound. IPL, To appear
Lamport, L. (2000): Lower bounds on consensus. Unpublished manuscript
Merritt, M. J (1985): Unpublished Notes
Skeen, D. (1982): Nonblocking commit protocols. ACM SIGMOD Conf. on Management of Data, 133–147
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Charron-Bost, B. (2003). Comparing the Atomic Commitment and Consensus Problems. In: Schiper, A., Shvartsman, A.A., Weatherspoon, H., Zhao, B.Y. (eds) Future Directions in Distributed Computing. Lecture Notes in Computer Science, vol 2584. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-37795-6_6
Download citation
DOI: https://doi.org/10.1007/3-540-37795-6_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00912-2
Online ISBN: 978-3-540-37795-5
eBook Packages: Springer Book Archive