Database concurrency control using time warp

Abstract

Concurrency control in a distributed database refers to mechanisms which permit multiple transactions to operate on the database simultaneously while ensuring that the database appears consistent to each transaction. Problems which need to be addressed include avoiding or recovering from deadlocked transactions and making transactions operate on a consistent database atomically. Considerable research has been done in this area and concurrency control mechanisms based on two-phase locking and two-phase commit [Hammer80], timestamps [Rosenkrantz78] [Thomas79], multiversion data objects [Reed78] and conflict analysis [Bernstein80a] [Bernstein80b] have been proposed. Each approach offers different advantages and incurs different costs. In this paper we investigate an optimistic algorithm for synchronising distributed database transactions that is based on Time Warp (TW) described by Jefferson [Jefferson85]. The database is assumed to consist of a set of long lived abstract data objects that are operated upon concurrently by a changing set of short lived objects, i.e. transactions. First, a brief outline of the TW algorithm is given, then the characteristics of a concurrency control (CC) algorithm based on TW is presented and finally, we discuss problems and advantages of this CC algorithm, and experience with a particular implementation.