Guerraoui, Rachid
Kapalka, Michal
On Obstruction-Free Transactions
Spaa'08: Proceedings Of The Twentieth Annual Symposium On Parallelism In Algorithms And Architectures
Spaa'08: Proceedings Of The Twentieth Annual Symposium On Parallelism In Algorithms And Architectures
Spaa'08: Proceedings Of The Twentieth Annual Symposium On Parallelism In Algorithms And Architectures
Spaa'08: Proceedings Of The Twentieth Annual Symposium On Parallelism In Algorithms And Architectures
Transactional memory
obstruction-freedom
consensus number
impossibility
2008
2008
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.
ACM
Spaa'08: Proceedings Of The Twentieth Annual Symposium On Parallelism In Algorithms And Architectures
Conference Papers
000266217200043