Concurrency control protocols for management of replicated data items in

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.