Name
Abstract | ||
|---|---|---|
Databases and other transaction-processing systems use concurrency control and recovery algorithms to ensure that transactions are atomic (i.e., serializable and recoverable). We present a new algorithm based on locking that permits more concurrency than existing commutativity-based algorithms. The algorithm exploits type-specific properties of objects; necessary and sufficient constraints on lock conflicts are derived directly from a data type specification. In addition, the algorithm permits operations to be both partial and non-deterministic, and it permits the lock mode for an operation to be determined by its results as well as its name and arguments. We give a complete formal description of the algorithm, encompassing both concurrency control and recovery, and prove that the algorithm satisfies hybrid atomicity , a local atomicity property that combines aspects of static and dynamic atomic algorithms. We also show that the algorithm is optimal in the sense that no hybrid atomic locking scheme can permit more concurrency. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1016/0022-0000(91)90031-Y | Journal of Computer and System Sciences |
Keywords | Field | DocType |
abstract data type,hybrid concurrency control,satisfiability,algorithms,data bases,data type,hybrid systems,queueing theory,concurrency control,recovery | Timestamp-based concurrency control,Two-phase commit protocol,Isolation (database systems),Concurrency control,Computer science,Multiversion concurrency control,Distributed concurrency control,Non-lock concurrency control,Optimistic concurrency control,Distributed computing | Journal |
Volume | Issue | ISSN |
43 | 1 | Journal of Computer and System Sciences |
Citations | PageRank | References |
60 | 32.63 | 33 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maurice Herlihy | 1 | 8623 | 920.94 |
| William E. Weihl | 2 | 2614 | 903.11 |