COMMUTATIVITY-BASED CONCURRENCY-CONTROL FOR ABSTRACT DATA-TYPES

Two novel concurrency algorithms for abstract data types are presented that 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 each other and with other algorithms, as long as the other algorithms also ensure dynamic atomicity. The algorithms are quite general, permitting operations to be both partial and nondeterministic. The results returned by operations can be used in determining conflicts, thus allowing higher levels of concurrency than 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, thus illustrating the subtle interactions between concurrency control and recovery. A general correctness condition that must be satisfied by the combination of a recovery method and a conflict relation is identified.