Data processing: database and file management or data structures – Database design – Data structure types
Patent
1997-10-17
1999-12-07
Lintz, Paul R.
Data processing: database and file management or data structures
Database design
Data structure types
707 8, 709104, G06F 1730
Patent
active
059999314
ABSTRACT:
The invention provides protocols for managing transactions operating on replicated data items at multiple physical sites in a distributed database system. The protocols make use of dynamically changing sets of data items referred to as "virtual sites" and a replication graph or other suitable globally consistent representation of the relationships between the transactions and the virtual sites. Illustrative embodiments of the invention include a static global serializability (SGS) protocol, a commit-oriented protocol (COP) and a multiversion optimistic protocol (MOP). The SGS protocol broadcasts the data access set of a given transaction to all physical sites, and applies the Thomas Write Rule (TWR) to write-write conflicts on secondary copies of data items. The COP protocol defers testing of the replication graph until a transaction is ready to commit, and each transaction is allowed to proceed at its origination site independently of other transactions that are executing at other sites. The MOP protocol uses two versions of each data item to ensure global multiversion serializability. The two versions are the current version of the data item, and a "last certified version" of the data item. All read-only transactions read the last certified version, and can therefore proceed without delay. The protocols ensure global serializability while substantially reducing communication overhead relative to conventional protocols.
REFERENCES:
patent: 4432057 (1984-02-01), Daniell et al.
patent: 5459871 (1995-10-01), Van Den Berg
patent: 5504899 (1996-04-01), Raz
patent: 5504900 (1996-04-01), Raz
patent: 5701480 (1997-12-01), Raz
patent: 5734817 (1998-03-01), Roffe et al.
patent: 5781910 (1998-07-01), Gostanian et al.
patent: 5835766 (1998-11-01), Iba et al.
A.A. Helal, A.A. Heddaya and B.B. Bhargawa, "Replication Techniques in Distributed Systems," Kluwer Academic Publishers, 1996.
C. Pu and A. Leff, "Replica Control in Distributed Systems: an Asynchronous Approach," Proceedings of ACM-SIGMOD 1991 International Conference on Management of Data, Denver, Colorado, pp. 377-386, May 1991.
J. Sidell, P.M. Aoki, S. Barr, A. Sah, C. Staelin, M. Stonebraker and A. Yu, "Data Replication in Mariposa," Proceedings of the Twelfth International Conference on Data Engineering, New Orleans, Louisiana, 1996.
E. Holler, "Multiple Copy Update," Lecture Notes in Computer Science, Distributed Systems-Architecture and Implementation: An Advanced Course, Springer-Verlag, Berlin, 1981.
H.F. Korth, E. Levy and A. Silberschatz, "A Formal Approach to Recovery by Compensating Transactions," Proceedings of the Sixteenth International Conference on Very Large Databases, Brisbane, Australia, pp. 95-106, Aug., 1990.
J. Gray, P. Helland, P. O'Neil and D. Shasha, "The Dangers of Replication and a Solution," Proceedings of ACM-SIGMOD 1996 International Conference on Management of Data, Montreal, Quebec, pp. 173-182, 1996.
P. Chundi, D.J. Rosenkrantz and S.S. Ravi, "Deferred Updates and Data Placement in Distributed Databases," Proceedings of the Twelfth International Conference on Data Engineering, New Orleans, Louisiana, 1996.
H.F. Korth and T.I. Imielinski, "Introduction to Mobile Computing," in Mobile Computing, pp. 1-39, Kluwer Academic Publishers, 1996.
Y. Breitbart, H. Garcia-Molina and A. Silberschatz, "Overview of Multidatabase Transaction Management," VLDB Journal, 1(2), 1992.
C.A. Ellis, "Consistency and Correctness of Duplicate Database Systems," Operating Systems Review, 11(5), Nov. 1977.
R.H. Thomas, "A Solution to the Concurrency Control Problem for Multiple Copy Databases," CompCon78, 1978.
T. Minoura, "A New Concurrency Control Algorithm for Distributed Database Systems," Proceedings of the Fourth Berkeley Workshop on Distributed and Computer Networks, pp. 221-234, Aug. 1979.
H.F. Korth et al., "A Framework for Understanding Distributed (Deadlock Detection) Algorithms," ACM 0-89791-097, pp. 192-201, 1983.
J. Gray, P. Homan, R. Obermack and H. Korth, "A Strawman Analysis of Probability of Waiting and Deadlock," IBM Research Report, IBM Research Laboratory, San Jose, CA, Feb. 1981.
K.M. Chandy and J. Misra, "Distributed Deadlock Detection," ACM Transactions on Computer Systems, vol. 1, No. 2, pp. 144-156, May 1983.
E. Gelenber and K. Sevcik, "Analysis of Update Synchronization for Multiple Copy Databases," Proceedings of the Third Berkeley Workshop on Distributed Databases and Computer Networks, pp. 69-90, Aug. 1978.
Y. Breitbart and H.F. Korth, "Replication and Consistency: Being Lazy Helps Sometimes," Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Tucson, Arizona, May 1997.
Breitbart Yuri
Korth Henry F.
Silberschatz Abraham
Colbert Ella
Lintz Paul R.
Lucent Technologies - Inc.
LandOfFree
Concurrency control protocols for management of replicated data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Concurrency control protocols for management of replicated data , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Concurrency control protocols for management of replicated data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-835941