Commitment ordering for guaranteeing serializability across dist

Details Commitment ordering for guaranteeing serializability across dist Commitment ordering for guaranteeing serializability across dist

1994-12-05

1996-04-02

Kriess, Kevin A.

Boots, shoes, and leggings

395600, 364DIG2, 3649747, 364969, G06F 1214, G06F 1216

Patent

active

055049001

ABSTRACT:
Serializability across distributed transactions is guaranteed by selectively committing and aborting or delaying transactions to enforce an order of commitment that is the same as an order of performance of conflicting component operations of the transactions. A first memory access operation in a first transaction, for example, conflicts with a second memory access operation in a second transaction when the two memory access operations reference the same memory location and at least one of the operations is a write operation. The transaction processing system may permit a second transaction to read data written by a write operation of a first transaction before the first transaction is committed. In this case, depending on the respective order in which the two conflicting operations occur, the order of commitment is enforced, possibly by aborting either of the two transactions, to ensure that the order of commitment is the same as the order of the operations. The conflicts, for example, are detected when the addresses are determined during preparation of the transactions. The component operations may be scheduled for most efficient use of the computer system capabilities. In a multiprocessor system in which a global coordinator communicates with a plurality of transaction processors by way of "prepare" and "commit" commands, the commitment order is referenced to delay acknowledging that a transaction has been "prepared" until the transaction's "abort set" has been minimized.

REFERENCES:
patent: 4224664 (1980-09-01), Trinchieri
patent: 4249241 (1981-02-01), Aberle et al.
patent: 4627019 (1986-12-01), Ng
patent: 4881166 (1989-11-01), Thompson et al.
patent: 5193188 (1993-03-01), Franaszek et al.
patent: 5212788 (1993-05-01), Lomet et al.
patent: 5263156 (1993-11-01), Bowen et al.
Vassos Hadzilacos, "A Knowledge Theoretic Analysis of Atomic Commitment Protocols," Proc. of the Sixth ACM Symposium on Principles of Database Systems, Association for Computing Machinery, New York, NY, Mar. 23-25, 1987, pp. 129-134.
Joseph Y. Halpern, "Using Reasoning about Knowledge to Analyze Distributed Systems," Research Report RJ 5522 (56421) Mar. 3, 1987, Computer Science, IBM Almaden Research Center, San Jose, California, 1987.
Lampson et al., "Crash Recovery in a Distributed Data Storage System," Technical Report, Xerox, Palo Alto Research Center, Palo Alto, California, 1986.
Litwin et al., "Flexible Concurrency Control Using Value Dates," in Integration of Information Systems: Bridging Heterogeneous Databases, ed. A. Gupta, IEEE Press, IEEE, New York, NY, 1989, pp. 144-145.
Weihl, "Distributed Version Management for Read-Only Actions," IEEE Transactions on Software Engineering, vol. SE-13, No. 1, IEEE, New York, NY, Jan. 1987, pp. 55-64.
Christos Papadimitriou, The Theory of Database Concurrency Control, Computer Science Press, Inc., Rockville, Maryland, (1986), pp. 93-158, 201-224.
Vassos Hadzilacos, "A Theory of Reliability in Database Systems," Journal of the ACM, vol. 35, No. 1, January, 1988, pp. 121-145, Association for Computing Machinery, New York, New York.
Agrawal et al., "Modular Synchronization in Multiversion Databases: Version Control and Concurrency Control," Proc. of the 1989 ACM SIGMOD Int. Conf. on Management of Data, pp. 408-417, Portland, Oregon, June, 1989, Association for Computing Machinery, New York, N.Y.
Kung et al., "On Optimistic Methods for Concurrency Control," ACM Transactions on Database Systems, vol. 6, No. 2, (Jun. 1981), pp. 213-226, Association for Computing Machinery, New York, NY.
Chan et al., "Implementing Distributed Read-Only Transactions," IEEE Transactions on Software Engineering, vol. SE-11, No. 2, (Feb. 1985), pp. 205-212. IEEE, New York, N.Y.
Garcia-Molina et al., "Node Autonomy in Distributed Systems," (1988), pp. 158-166, IEEE, New York, N.Y.
Calton Pu, "Transactions across Heterogeneous Databases: The Super-database Architecture," pp. 1-18, (Jun. 1988), Department of Computer Science, Columbia, University, New York, N.Y.
Elmagarmid et al., "A Paradigm for Concurrency Control in Heterogeneous Distributed Database Systems," (1990), pp. 17-46, IEEE, New York, N.Y.
J. Puustjarvi, "Distributed Management of Transactions in Heterogeneous Distributed Database Systems", BIT, vol. 31,, No. 2, (1991), pp. 407-420.
Silberschatz et al., "Database Systems: Achievements and Opportunities," Communications of the ACM, vol. 34, No. 10, Association for Computing Machinery, New York, N.Y., Oct. 1991, pp. 110, 120.
Agrawal et al., "Performance Characteristics of Protocols With Ordered Shared Locks," Proceedings of the Seventh IEEE International Conference on Data Engineering, Institute of Electrical and Electronics Engineers, Pisctaway, New Jersey, Apr. 1991, pp. 592-601.
Agrawal et al, "Locks with Constrained Sharing," Proceedings of the Ninth ACM Symposium on Principles of Database Systems, Association for Computing Machinery, New York, N.Y., Apr. 1990, pp. 85-93.
Georgakopoulos et al., "On Serializability of Multidatabase Transactions through Forced Local Conflicts," Proceedings of the Seventh Int. Conf. on Data Engineering, Kobe, Japan, Apr. 1991.
Georgakopoulos et al., "Transaction Management in Multidatabase Systems," Technical Report #UH-CS-89-20, Department of Computer Science, University of Houston, Sep. 1989.
Jim Gray, "Operating Systems: An Advanced Course", Lecture Notes in Computer Science 60, (1978), pp. 394-395, 430-458.
Bernstein et al., Concurrency Control and Recovery in Database Systems, Addison-Wesley (1987), pp. 58-78.
L. Hobbs et al., Rdb/VMS--A Comprehensive Guide, Digital Press, Digital Equipment Corporation, Maynard, Mass., 1991.
Calton Pu, "Superdatabases for Composition of Heterogeneous Databases," 4th Int. Conf. on Data Engineering, Los Angeles, California, Feb. 1-5, 1988, pp. 548-555.
OS/Texas-11 Programming Manual, Digital Equipment Corporation, Apr. 20, 1972.
J. Eliot B. Moss, Nested Transactions, The MIT Press, 1985.
Breitart et al., "Reliable Management in a Multidatabase System," Proc. of the ACM SIGMOD conf. on Management of data, Atlantic City, New Jersey, Jun., 1990, pp. 215-224.
David Lomet, "Consistent Timestamping for Transactions in Distributed Systems", TR CRL 90/3, Digital Equipment Corp. CRL, Sep., 1990.
Amit Sheth, James Larson, "Federated Database Systems", ACM Computing Surveys, col. 22, No. 3, Sep., 1990, pp. 183-236.
Y. Breitbart, "Multidatabase Inoperability," Sigmond Record, vol. 19, No. 3, Sep. 1990, pp. 53-60.
Database System Concepts, Korth and Silberschatz, McGraw-Hill Inc., 1986, 1991, pp. 491-502.

Affiliated with

Also associated with

Rating

Commitment ordering for guaranteeing serializability across dist does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Commitment ordering for guaranteeing serializability across dist, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Commitment ordering for guaranteeing serializability across dist will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2024159