Nonblocking commit protocols

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Nonblocking commit protocols

Full text

Pdf (1.00 MB)

Source

International Conference on Management of Data archive
Proceedings of the 1981 ACM SIGMOD international conference on Management of data table of contents

Ann Arbor, Michigan

SESSION: Transaction management II table of contents

Pages: 133 - 142

Year of Publication: 1981

ISBN:0-89791-040-0

Author

Dale Skeen

University of California, Berkeley, California

Sponsor

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 139, Citation Count: 83

Additional Information:

abstract references cited by collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/582318.582339 What is a DOI?

ABSTRACT

Protocols that allow operational sites to continue transaction processing even though site failures have occurred are called nonblocking. Many applications require nonblocking protocols. This paper investigates the properties of nonblocking protocols. Necessary and sufficient conditions for a protocol to be nonblocking are presented and from these conditions a method for designing them is derived. Both a central site nonblocking protocol and a decentralized nonblocking protocol are presented.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Peter A. Alsberg , John D. Day, A principle for resilient sharing of distributed resources, Proceedings of the 2nd international conference on Software engineering, p.562-570, October 13-15, 1976, San Francisco, California, United States
	2	{GRAY79} Gray, J. N., "Notes on Database Operating Systems," in Operating Systems: An Advanced Course, Springer-Verlag, 1979.
	3	{HAMM79} Hammer, M. and Shipman, D., "Reliability Mechanisms for SDD-1: A System for Distributed Databases," Computer Corporation of America, Cambridge, Mass., July 1979.
	4	{LAMP76} Lampson, B. and Sturgis, H., "Crash Recovery in a Distributed Storage System," Tech. Report, Computer Science Laboratory, Xerox Parc, Palo Alto, California, 1976.
	5	{LIND79} Lindsay, B.G. et al., "Notes on Distributed Databases", IBM Research Report, no. RJ2571 (July 1979).
	6	Raymond A. Lorie, Physical integrity in a large segmented database, ACM Transactions on Database Systems (TODS), v.2 n.1, p.91-104, March 1977 [doi>10.1145/320521.320540]
	7	{ROTH77} Rothnie, J. B., Jr. and Goodman, N., "A Survey of Research and Development in Distributed Database Management," Proc. Third Int. Conf. on Very Large Databases, IEEE, 1977.
	8	{SKEE81a} Skeen, D., "A Formal Model of Crash Recovery in a Distributed System", IEEE Transactions on Software Engineering, (to appear).
	9	{SKEE81b} Skeen, D., "Crash Recovery in a Distributed Database System," Ph. D. Thesis, EECS Dept., University of California, Berkeley (in preparation).
	10	{STON79} Stonebraker, M., "Concurrency Control and Consistency of Multiple Copies in Distributed INGRES," IEEE Transactions on Software Engineering, May 1979.
	11	{SCHA78} Schapiro, R. and Millstein, R., "Failure Recovery in a Distributed Database System," Proc. 1978 COMPCON Conference, September 1978.
	12	{SVOB79} Svobodova, L., "Reliability Issues in Distributed Information Processing Systems," Proc. 9th IEEE Fault Tolerant Computing Conference, Madison, Wisc., June 1979.

CITED BY 83

	C. Mohan , B. Lindsay , R. Obermarck, Transaction management in the R* distributed database management system, ACM Transactions on Database Systems (TODS), v.11 n.4, p.378-396, Dec. 1986
	H. Breitwieser , M. Leszak, A distributed transaction processing protocol based on majority consensus, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.224-237, August 18-20, 1982, Ottawa, Canada
	Ramesh Gupta , Jayant Haritsa , Krithi Ramamritham, Revisiting commit processing in distributed database systems, ACM SIGMOD Record, v.26 n.2, p.486-497, June 1997
	Panduranga Rao Adusumilli , Lawrence J. Osborne, An integrated solution for managing replicated data in distributed systems, Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing: states of the art and practice, p.351-357, February 14-16, 1993, Indianapolis, Indiana, United States
	B Walter, A turnable protocol for symmetric surveillance in distributed systems, ACM SIGCOMM Computer Communication Review, v.16 n.3, p.368-376, Aug. 5, 1986
	David Wong, Partition detection and optimistic commit for dynamically reconfigurable distributed databases, Proceedings of the 1988 ACM SIGSMALL/PC symposium on ACTES, p.69-82, May 04-06, 1988, Cannes, France
	Derek L. Eager , Kenneth C. Sevcik, Achieving robustness in distributed database systems, ACM Transactions on Database Systems (TODS), v.8 n.3, p.354-381, Sept. 1983
	S. H. Son , J. L. Pfaltz, Reliability mechanisms for ADAMS, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1390-1397, January 1989, Pasadena, California, United States
	Eliezer Levy , Henry F. Korth , Abraham Silberschatz, An optimistic commit protocol for distributed transaction management, ACM SIGMOD Record, v.20 n.2, p.88-97, June 1991
	C. Mohan , R. Strong , S. Finkelstein, Method for distributed transaction commit and recovery using Byzantine Agreement within clusters of processors, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.89-103, August 17-19, 1983, Montreal, Quebec, Canada
	David Cheung , Tiko Kameda, Site optimal termination protocols for a distributed database under network partitioning, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.111-121, August 1985, Minaki, Ontario, Canada
	D. Agrawal , A. El Abbadi, Efficient solution to the distributed mutual exclusion problem, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.193-200, June 1989, Edmonton, Alberta, Canada
	Herbert Kuss, Logical design of a reliable transaction management in a distributed multiple processor system, Proceedings of the 1983 ACM SIGSMALL symposium on Personal and small computers, p.109-116, December 07-09, 1983, San Diego, California, United States
	Michael Rabinovich , Edward D. Lazowska, A fault-tolerant commit protocol for replicated databases, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.139-148, June 02-05, 1992, San Diego, California, United States
	Jian Tang, Voting class — an approach to achieving high availability for replicated data, Proceedings of the second international symposium on Databases in parallel and distributed systems, p.146-156, July 02-04, 1990, Dublin, Ireland
	A. Segall , O. Wolfson, Transaction commitment at minimal communication cost, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.112-118, March 23-25, 1987, San Diego, California, United States
	Yousef J. Al-Houmaily , Panos K. Chrysanthis, Dealing with incompatible presumptions of commit protocols in multidatabase systems, Proceedings of the 1996 ACM symposium on Applied Computing, p.186-195, February 17-19, 1996, Philadelphia, Pennsylvania, United States
	Gregory Chockler , Dahlia Malkhi, Active disk paxos with infinitely many processes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Idit Keidar , Danny Dolev, Efficient message ordering in dynamic networks, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.68-76, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Philip A. Bernstein , Nathan Goodman, An algorithm for concurrency control and recovery in replicated distributed databases, ACM Transactions on Database Systems (TODS), v.9 n.4, p.596-615, Dec. 1984
	S. H. Son, An Adaptive Checkpointing Scheme for Distributed Databases with Mixed Types of Transactions, IEEE Transactions on Knowledge and Data Engineering, v.1 n.4, p.450-458, December 1989
	C. Mohan , B. Lindsay, Efficient commit protocols for the tree of processes model of distributed transactions, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.76-88, August 17-19, 1983, Montreal, Quebec, Canada
	K. V. S. Ramarao, Commitment in a partitioned distributed database, ACM SIGMOD Record, v.17 n.3, p.371-378, June 1988
	B. Bhargava , T. Mueller , J. Riedl, Experimental analysis of layered Ethernet software, Proceedings of the 1987 Fall Joint Computer Conference on Exploring technology: today and tomorrow, p.559-568, December 1987, Dallas, Texas, United States
	Rachid Guerraoui, Indulgent algorithms (preliminary version), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.289-297, July 16-19, 2000, Portland, Oregon, United States
	Richard P. King , Nagui Halim , Hector Garcia-Molina , Christos A. Polyzois, Management of a remote backup copy for disaster recovery, ACM Transactions on Database Systems (TODS), v.16 n.2, p.338-368, June 1991
	Divyakant Agrawal , Amr El Abbadi, An efficient and fault-tolerant solution for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.1-20, Feb. 1991
	Akhil Kumar, A New Algorithm for the Decentralized Aggregation Problem, Distributed and Parallel Databases, v.7 n.4, p.415-427, Oct. 1999
	M. Stonebraker, Future Trends in Database Systems, IEEE Transactions on Knowledge and Data Engineering, v.1 n.1, p.33-44, March 1989
	D. Agrawal , A. El Abbadi , R. C. Steinke, Epidemic algorithms in replicated databases (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.161-172, May 11-15, 1997, Tucson, Arizona, United States
	Christos A. Polyzois , Hector Garcia-Molina, Evaluation of remote backup algorithms for transaction processing systems, ACM SIGMOD Record, v.21 n.2, p.246-255, June 1, 1992
	Eric C. Cooper, Analysis of distributed commit protocols, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida
	Nathan Goodman , Dale Skeen , Arvola Chan , Umeshwar Dayal , Stephen Fox , Daniel Ries, A recovery algorithm for a distributed database system, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
	Jo-Mei Chang, Simplifying distributed database systems design by using a broadcast network, ACM SIGMOD Record, v.14 n.2, June 1984
	Idit Keidar , Sergio Rajsbaum, A simple proof of the uniform consensus synchronous lower bound, Information Processing Letters, v.85 n.1, p.47-52, 16 January 2003
	Michel Raynal , Mukesh Singhal, Mastering Agreement Problems in Distributed Systems, IEEE Software, v.18 n.4, p.40-47, July 2001
	M. L. Liu , D. Agrawal , A. El Abbadi, The Performance of Two Phase Commit Protocols in the Presence of Site Failures, Distributed and Parallel Databases, v.6 n.2, p.157-182, April 1998
	Francis Chin , K. V. S. Ramarao, Optimal termination protocols for network partitioning, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
	C. Mohan , B. Lindsay, Efficient commit protocols for the tree of processes model of distributed transactions, ACM SIGOPS Operating Systems Review, v.19 n.2, p.40-52, April 1985
	Idit Keidar , Sergio Rajsbaum, On the cost of fault-tolerant consensus when there are no faults: preliminary version, ACM SIGACT News, v.32 n.2, June 2001
	P. Krishna Reddy , Masaru Kitsuregawa, Speculative Locking Protocols to Improve Performance for Distributed Database Systems, IEEE Transactions on Knowledge and Data Engineering, v.16 n.2, p.154-169, February 2004
	Rachid Guerraoui, Non-blocking atomic commit in asynchronous distributed systems with failure detectors, Distributed Computing, v.15 n.1, p.17-25, January 2002
	T. V. Lakshman , V. K. Wei, Distributed Computing on Regular Networks with Anonymous Nodes, IEEE Transactions on Computers, v.43 n.2, p.211-218, February 1994
	O. T. Satyanarayanan , D. Agrawal, Efficient Execution of Read-Only Transactions in Replicated Multiversion Databases, IEEE Transactions on Knowledge and Data Engineering, v.5 n.5, p.859-871, October 1993
	Eliezer Levy , Henry F. Korth , Abraham Silberschatz, A theory of relaxed atomicity (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.95-110, August 19-21, 1991, Montreal, Quebec, Canada
	K. V. S. Ramarao, On the complexity of commit protocols, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.235-244, March 25-27, 1985, Portland, Oregon, United States
	Weijia Jia , Jörg Kaiser , Edgar Nett, RMP: Fault-Tolerant Group Communication, IEEE Micro, v.16 n.2, p.59-67, April 1996
	Sang Hyuk Son , Ashok K. Agrawala, Distributed Checkpointing for Globally Consistent States of Databases, IEEE Transactions on Software Engineering, v.15 n.10, p.1157-1167, October 1989
	P. Ancilotti , B. Lazzerini , C. A. Prete , M. Sacchi, A Distributed Commit Protocol for a Multicomputer System, IEEE Transactions on Computers, v.39 n.5, p.718-724, May 1990
	David Cheung , Tiko Kameda, Site optimal termination protocols for a distributed database under network partitioning, ACM SIGOPS Operating Systems Review, v.20 n.3, p.17-27, July, 1986
	André Schiper, Early consensus in an asynchronous system with a weak failure detector, Distributed Computing, v.10 n.3, p.149-157, April 1997
	Partha Dutta , Rachid Guerraoui , Bastian Pochon, Fast non-blocking atomic commit: an inherent trade-off, Information Processing Letters, v.91 n.4, p.195-200, 31 August 2004
	Rachid Guerraoui , André Schiper, The Generic Consensus Service, IEEE Transactions on Software Engineering, v.27 n.1, p.29-41, January 2001
	Jayant R. Haritsa , Krithi Ramamritham , Ramesh Gupta, The PROMPT Real-Time Commit Protocol, IEEE Transactions on Parallel and Distributed Systems, v.11 n.2, p.160-181, February 2000
	C. Mohan , R. Strong , S. Finkelstein, Method for distributed transaction commit and recovery using Byzantine Agreement within clusters of processors, ACM SIGOPS Operating Systems Review, v.19 n.3, p.29-43, July 1985
	M. Hurfin , A. Mostéfaoui , M. Raynal, A Versatile Family of Consensus Protocols Based on Chandra-Toueg's Unreliable Failure Detectors, IEEE Transactions on Computers, v.51 n.4, p.395-408, April 2002
	Fernando Pedone , Rachid Guerraoui , André Schiper, The Database State Machine Approach, Distributed and Parallel Databases, v.14 n.1, p.71-98, July 2003
	Omar Bakr , Idit Keidar, Evaluating the running time of a communication round over the internet, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Wenbing Zhao , Louise E. Moser , P. Michael Melliar-Smith, Unification of Transactions and Replication in Three-Tier Architectures Based on CORBA, IEEE Transactions on Dependable and Secure Computing, v.2 n.1, p.20-33, January 2005
	Michel Hurfin , Michel Raynal, A simple and fast asynchronous consensus protocol based on a weak failure detector, Distributed Computing, v.12 n.4, p.209-223, September 1999
	Gregory Chockler , Dahlia Malkhi, Active disk Paxos with infinitely many processes, Distributed Computing, v.18 n.1, p.73-84, July 2005
	Svend Frølund , Rachid Guerraoui, Implementing E-Transactions with Asynchronous Replication, IEEE Transactions on Parallel and Distributed Systems, v.12 n.2, p.133-146, February 2001
	I-Ling Yen , Farokh B. Bastani , David J. Taylor, Design of Multi-Invariant Data Structures for Robust Shared Accesses in Multiprocessor Systems, IEEE Transactions on Software Engineering, v.27 n.3, p.193-207, March 2001
	Santosh K. Shrivastava, To CATOCS or not to CATOCS, that is the …, ACM SIGOPS Operating Systems Review, v.28 n.4, p.11-14, Oct. 1994
	Gildas Avoine , Serge Vaudenay, How to safely close a discussion, Information Processing Letters, v.102 n.4, p.138-142, May, 2007
	Edmond Lau , Samuel Madden, An integrated approach to recovery and high availability in an updatable, distributed data warehouse, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Jim Gray , Leslie Lamport, Consensus on transaction commit, ACM Transactions on Database Systems (TODS), v.31 n.1, p.133-160, March 2006
	Satoshi Itaya , Naohiro Hayashibara , Tomoya Enokido , Makoto Takizawa, HAMS: scalable peer-to-peer multimedia streaming model in heterogeneous networks, Journal of Computer and System Sciences, v.72 n.7, p.1211-1225, November 2006
	Youhei Tanaka , Naohiro Hayashibara , Tomoya Enokido , Makoto Takizawa, A mobile agent model for fault-tolerant manipulation on distributed objects, Cluster Computing, v.10 n.1, p.81-93, March 2007
	Ada Wai-Chee Fu , David Wai-Lok Cheung, A Transaction Replication Scheme for a Replicated Database with Node Autonomy, Proceedings of the 20th International Conference on Very Large Data Bases, p.214-225, September 12-15, 1994
	Hector Garcia-Molina , Christos A. Polyzois , Robert B. Hagmann, Two Epoch Algorithms for Disaster Recovery, Proceedings of the 16th International Conference on Very Large Data Bases, p.222-230, August 13-16, 1990
	Mihalis Yannakakis, Perspectives on database theory, ACM SIGACT News, v.27 n.3, p.25-49, Sept. 1996
	Satoshi Itaya , Tomoya Enokido , Makoto Takizawa, Scalable multimedia streaming model in heterogeneous networks, International Journal of High Performance Computing and Networking, v.5 n.1/2, p.62-74, November 2007
	Keiji Ozaki , Tomoya Enokido , Makoto Takizawa, Coordination protocols for a reliable sensor, actuator, and device network (SADN), Mobile Information Systems, v.4 n.2, p.147-161, April 2008
	Ailixier Aikebaier , Tomoya Enokido , Makoto Takizawa, A distributed coordination protocol in an order-heterogeneous group, International Journal of Web and Grid Services, v.4 n.1, p.5-23, May 2008
	Laurent George , Pascale Minet, Preserving the consistency of distributed objects with real-time transactions, Proceedings of the 8th international conference on New technologies in distributed systems, June 23-27, 2008, Lyon, France
	Gregory Chockler , Seth Gilbert , Nancy Lynch, Virtual infrastructure for collision-prone wireless networks, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	R. Guerraoui , N. Lynch, A general characterization of indulgence, ACM Transactions on Autonomous and Adaptive Systems (TAAS), v.3 n.4, p.1-19, November 2008
	Sebastian Obermeier , Stefan Böttcher , Martin Hett , Panos K. Chrysanthis , George Samaras, Blocking reduction for distributed transaction processing within MANETs, Distributed and Parallel Databases, v.25 n.3, p.165-192, June 2009
	J. Robert Ensor , John D. Gabbe, Transactional blackboards, Proceedings of the 9th international joint conference on Artificial intelligence, p.340-344, August 18-23, 1985, Los Angeles, California
	Youhei Tanaka , Tomoya Enokido , Makoto Takizawa, Transactional agents on distributed object systems, International Journal of High Performance Computing and Networking, v.6 n.2, p.148-159, July 2009
	C. K. Baru , G. Fecteau , A. Goyal , H. Hsiao , A. Jhingran , S. Padmanabhan , G. P. Copeland , W. G. Wilson, DB2 parallel edition, IBM Systems Journal, v.34 n.2, p.292-322, 1995
	Ailixier Aikebaier , Makoto Takizawa, A protocol for reliably, flexibly, and efficiently making agreement among peers, International Journal of Web and Grid Services, v.5 n.4, p.356-371, December 2009

Collaborative Colleagues:

Dale Skeen: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player