The inherent cost of nonblocking commitment

ABSTRACT

A commitment protocol orchestrates the execution of a distributed transaction, allowing each participant to “vote” on the transaction and then applying a pre-specified rule to decide the outcome (commit or abort). A nonblocking commitment protocol is able to correctly terminate a transaction at all operational participants in the presence of any number of benign processor failures. Herein, we derive strong lower bounds for both nonblocking protocols and their less fault-tolerant blocking counterparts. Results on message complexity are both surprising and encouraging: the message complexities of the two classes of protocols are identical. Results on time complexity were less encouraging: nonblocking protocols are approximately 50% more expensive. However, we show how to overlap nonblocking executions of interfering transactions and thereby reduce their extra cost.

REFERENCES

• 1: Stephen Cook , Cynthia Dwork, Bounds on the time for parallel RAM's to compute simple functions, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.231-233, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802196]
• 2: D. Dolev, "The Byzantine Generals Strike Again," J. Of Algorithms, vol. 3, no. 1, 1982.
• 3: Danny Dolev , H. Raymond Strong, Polynomial algorithms for multiple processor agreement, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.401-407, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802215]
• 4: Danny Dolev , Ruediger Reischuk, Bounds on information exchange for Byzantine Agreement, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.132-140, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806690]
• 5: D. Dolev and H.R. Strong, "Requirements for Agreement in a Distributed System," Proc. 2nd International Symposium on Distributed Databases, 1982.
• 6: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588060]
• 7: Leslie Lamport, Using Time Instead of Timeout for Fault-Tolerant Distributed Systems., ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.2, p.254-280, April 1984 [doi>10.1145/2993.2994]
• 8: L. Lamport and P.M. Melliar-Smith, "Synchronizing Clocks in the Presence of Faults," Technical Report Op.60, Computer Science Laboratory, SRI International, 1981.
• 9: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 10: N. Lynch, M. Fischer, and R. Fowler, "A Simple and Efficient Byzantine Generals Algorithm," Proc. 2nd IEEE Symposium on Reliability in Distributed Software and Data-base Systems, 1982.
• 11: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 12: D. Skeen, "A Decentralized Termination Protocol," Proc. 1st IEEE Symposium on Reliability in Distributed Software and Database Systems, 1981.
• 13: D. Skeen, "Crash Recovery in a Distributed Database System," Technical Report UCB/BRL M82/45, Department of Electrical Engineering and Computer Science, University of California, Berkeley, 1982.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

General Terms:
Performance