Extending Multiversion Time-Stamping Protocols to Exploit Type Information

Atomic transactions are a widely accepted approach to implementing and reasoning about fault-tolerant distributed programs. This paper shows how multiversion time-stamping protocols for atomicity can be extended to induce fewer delays and restarts by exploiting semantic information about objects such as queues, directories, or counters. This technique relies on static preanalysis of conflicts between operations, and incurs no additioiwal runtime overhead. This technique is deadlock-free, and it is applicable to objects of arbitrary type.