Generating Fast Atomic Commit from Hyperfast Consensus | SpringerLink
Skip to main content
Springer Nature Link
Log in

Generating Fast Atomic Commit from Hyperfast Consensus

  • Conference paper
Dependable Computing (LADC 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3747))

Included in the following conference series:

  • 327 Accesses

Abstract

This work introduces a highly modular derivation of fast non-blocking atomic commit protocols. Modularity is achieved by the use of consensus protocols as completely independent services. Fast decision is obtained by the use of consensus protocols that decide in one communication step in good scenarios. Two original non-blocking atomic commit protocols are presented. One of the presented protocols outperforms existing equivalent solutions that are based on the use of failure detectors. In the presence of a low resiliency rate, f ≤ 1, it behaves as the classical 2PC and 3PC, exhibiting the same message complexities. In the general case, when one considers the number of tolerated crashes as f < n/2, it exhibits a complexity of 2nf + 3n point to point messages. The best known algorithm exhibits a complexity of 4nf + 3n point to point messages.

This work is supported by CNPQ/Brazil and by the cooperation project CAPES/COFECUB 497/05.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Brasileiro, F., Greve, F., Mostefaoui, A., Raynal, M.: Consensus in One Communication Step is Possible. In: PaCT (International Conference on Parallel Computing Technologies). LNCS, vol. 1800, pp. 1258–1265. Springer, Heidelberg (2001)

    Google Scholar 

  2. Charon-Bost, B., Schiper, A.: Uniform Consensus is Harder than Consensus. Technical Report, École Polytechnique Fédérale de Lausane, Switzerland, DSC/2000/028 (May 2000)

    Google Scholar 

  3. Chandra, T., Hadzilacos, V., Toueg, S.: The Weakest Failure Detector for Solving Consensus. Journal of the ACM 43(4), 685–722 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  4. Chandra, T., Toueg, S.: Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the ACM 43(2), 225–267 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  5. Dutta, P., Guerraoui, R., Pochon, B.: Fast non-blocking atomic commit: an inherent trade-off. Inf. Process. Lett. 91(4), 195–200 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  6. Fischer, M., Lynch, N., Paterson, M.: Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM 32(2), 374–382 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  7. Greve, F., Hurfin, M., Raynal, M., Tronel, F.: Primary Component Asynchronous Group Membership as an Instance of a Generic Agreement Framework. In: ISADS 2001: 5th International Symposium on Autonomous Decentralized Systems, pp. 93–100 (March 2001)

    Google Scholar 

  8. Gray, J., Lamport, L.: Consensus on Transaction Commit, Technical Report, Microsoft Corporation, MSR-TR-2003-96 (January 2004)

    Google Scholar 

  9. Guerraoui, R., Larrea, M., Schiper, A.: Reducing the Cost for Non-Blocking in Atomic Commitment. In: 16th International Conference on Distributed Computing Systems, Hong-Kong, pp. 692–697 (May 1996)

    Google Scholar 

  10. Greve, F.: Réponses efficaces au besoin d’accord dans un groupe, PhD Thesis, Univ. of Rennes I (November 2002)

    Google Scholar 

  11. Guerraoui, R., Schiper, A.: The Generic Consensus Service. IEEE Transactions on Software Engineering 27(1), 29–41 (2001)

    Article  MathSciNet  Google Scholar 

  12. Guerraoui, R., Schiper, A.: The Decentralized Non-Blocking Atomic Commitment Protocol. In: 14th IEEE International Symposium on Parallel and Distributed Processing, San Antonio, pp. 2–9 (October 1995)

    Google Scholar 

  13. Guerraoui, R.: Revisiting the Relationship Between Non-Blocking Atomic Commitment and Consensus. In: Hélary, J.-M., Raynal, M. (eds.) WDAG 1995, vol. 972, Springer, Heidelberg (1995)

    Chapter  Google Scholar 

  14. Hadzilacos, V., Toueg, S.: Distributed Systems, ch Fault Tolerant Broadcasts ans Related Problems, pp. 97–145 (1993)

    Google Scholar 

  15. Hurfin, M., Tronel, F.: A Solution to Atomic Commitment Based on an Extended Consensus Protocol. In: 6th IEEE Workshop on Future Trends of Distributed Computing Systems, pp. 98–103 (1997)

    Google Scholar 

  16. Gray, J.: Notes on Database Operating Systems. In: Flynn, M.J., Jones, A.K., Opderbeck, H., Randell, B., Wiehle, H.R., Gray, J.N., Lagally, K., Popek, G.J., Saltzer, J.H. (eds.) Operating Systems. LNCS, vol. 60, pp. 10–17. Springer, Heidelberg (1978)

    Google Scholar 

  17. Keidar, I., Dolev, D.: Increasing the Resilience of Atomic Commit, at No Additional Cost. In: ACM PODS 1995: Principles of Database Systems, pp. 245–254 (May 1995)

    Google Scholar 

  18. Keidar, I., Rajsbaum, S.: On the Cost of Fault-Tolerant Consensus when There are No Faults: a Tutorial, MIT Technical Report, MIT-LCS-TR-821, Preliminary version in SIGACT News, Distributed Computing Column, 32(2), 45–63 (2001)

    Google Scholar 

  19. Lamport, L.: The part-time parliament. ACM Transactions on Computer Systems 16(2), 133–169 (1998)

    Article  Google Scholar 

  20. Lamport, L.: Paxos Made Simple. ACM SIGACT News, Distributed Computing Column 32(4), 18–25 (2001)

    Google Scholar 

  21. Lamport, L.: Lower Bounds for Asynchronous Consensus, Technical Report, Microsoft Corporation, MSR-TR-2004-72 (July 2004)

    Google Scholar 

  22. Raynal, M.: Revisiting the Non-Blocking Atomic Commitment Problem in Distributed Systems. In: 2nd Workshop on Fault-Tolerant Parallel and Distributed Systems (1997)

    Google Scholar 

  23. Skeen, D.: NonBlocking Commit Protocols. In: ACM SIGMOD International Conference on Management of Data, pp. 133–142. ACM Press, New York (1981)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Federal University of Bahia, Brazil

    Fabíola Gonçalves Pereira Greve

  2. GET/ENST-Bretagne, 35512, Cesson-Sévigné, France

    Jean-Pierre Le Narzul

  3. IRISA, Campus de Beaulieu, 35042, Rennes, France

    Jean-Pierre Le Narzul

Authors
  1. Fabíola Gonçalves Pereira Greve
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jean-Pierre Le Narzul
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Pontifícia Universidade Católica do Paraná (PUCPR), PPGIA, Paraná, Brazil

    Carlos Alberto Maziero

  2. Dept. Engenharia Informática/CISUC Universidade de Coimbra - Polo II, 3030-397, Coimbra, Portugal

    João Gabriel Silva

  3. Universidade Federal da Bahia (UFBA), Prédio do CPD, Campus de Ondina, Av. Ademar de Barros, CEP 40.170-110, Salvador, BA, Brazil

    Aline Maria Santos Andrade  & Flávio Morais de Assis Silva  & 

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Greve, F.G.P., Le Narzul, JP. (2005). Generating Fast Atomic Commit from Hyperfast Consensus. In: Maziero, C.A., Gabriel Silva, J., Andrade, A.M.S., de Assis Silva, F.M. (eds) Dependable Computing. LADC 2005. Lecture Notes in Computer Science, vol 3747. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11572329_18

Download citation

  • DOI: https://doi.org/10.1007/11572329_18

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-29572-3

  • Online ISBN: 978-3-540-32092-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation