Abstract | ||
---|---|---|
Two novel concurrency control algorithms for abstract data types are presented. The algorithms ensure serializability of transactions by using conflict relations based on the commutativity of operations. It is proved that both algorithms ensure a local atomicity property called dynamic atomicity. This means that the algorithms can be used in combination with any other algorithms that also ensure dynamic atomicity. The algorithms are quite general, permitting operations to be both partial and nondeterministic., They permit the results returned by operations to be used in determining conflicts, thus permitting higher levels of concurrency than is otherwise possible. The descriptions and proofs encompass recovery as well as concurrency control. The two algorithms use different recovery methods: one uses intentions lists, and the other uses undo logs. It is shown that conflict relations that work with one recovery method do not necessarily work with the other. A general correctness condition that must be satisfied by the combination of a recovery method and a conflict relation is identified.<> |
Year | DOI | Venue |
---|---|---|
1988 | 10.1109/12.9728 | System Sciences, 1988. Vol.II. Software Track, Proceedings of the Twenty-First Annual Hawaii International Conference |
Keywords | Field | DocType |
higher level,recovery method,abstract data types,general correctness condition,commutativity-based concurrency control,conflict relation,local atomicity property,dynamic atomicity,novel concurrency algorithm,different recovery method,abstract data type,concurrency control,nondeterministic,serializability,satisfiability,commutativity,parallel processing,algorithm design and analysis,computer science,concurrent computing,database systems | Atomicity,Timestamp-based concurrency control,Serializability,Isolation (database systems),Programming language,Concurrency control,Computer science,Parallel computing,Multiversion concurrency control,Real-time computing,Non-lock concurrency control,Optimistic concurrency control | Journal |
Volume | Issue | ISSN |
37 | 12 | 0018-9340 |
ISBN | Citations | PageRank |
0-8186-0842-0 | 160 | 49.70 |
References | Authors | |
51 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
William E. Weihl | 1 | 2614 | 903.11 |