## On Obstruction-Free Transactions

This paper studies obstruction-free software transactional memory systems (OFTMs). These systems are appealing, for they combine the atomicity property of transactions with a liveness property that ensures the commitment of every transaction that eventually encounters no contention. We precisely define OFTMs and establish two of their fundamental properties. First, we prove that the consensus number of such systems is 2. This indicates that OFTMs cannot be implemented with plain read/write shared memory, on the one hand, but, on the other hand, do not require powerful universal objects, such as compare-and-swap. Second, we prove that OFTMs cannot ensure disjoint-accessparallelism (in a strict sense). This may result in artificial “hot spots” and thus limit the performance of OFTMs.

Published in:
Spaa'08: Proceedings Of The Twentieth Annual Symposium On Parallelism In Algorithms And Architectures, 304-313
Presented at:
20th ACM Symposium on Parallelism in Algorithms and Architectures, Munich, Germany, June 14-16, 2008
Year:
2008
Publisher:
ACM
Keywords:
Laboratories: