TY - GEN
T1 - On partial wait-freedom in transactional memory
AU - Kuznetsov, Petr
AU - Ravi, Srivatsan
N1 - Publisher Copyright:
Copyright 2015 ACM.
PY - 2015/1/4
Y1 - 2015/1/4
N2 - Transactional memory (TM) is a convenient synchronization tool that allows concurrent threads to declare sequences of instructions on shared data as speculative transactions with "all-or-nothing" semantics. It is known that dynamic transactional memory cannot provide wait-free progress ensuring that every transaction commits in a finite number of its own steps. In this paper, we explore the costs of providing wait-freedom to only a subset of transactions. We require that read-only transactions commit in the wait-free manner, while updating transactions are guaranteed to commit only if they run in the absence of concurrency. We show that this kind of partial wait-freedom, combined with attractive requirements like read invisibility or disjoint-access parallelism, incurs considerable complexity costs.
AB - Transactional memory (TM) is a convenient synchronization tool that allows concurrent threads to declare sequences of instructions on shared data as speculative transactions with "all-or-nothing" semantics. It is known that dynamic transactional memory cannot provide wait-free progress ensuring that every transaction commits in a finite number of its own steps. In this paper, we explore the costs of providing wait-freedom to only a subset of transactions. We require that read-only transactions commit in the wait-free manner, while updating transactions are guaranteed to commit only if they run in the absence of concurrency. We show that this kind of partial wait-freedom, combined with attractive requirements like read invisibility or disjoint-access parallelism, incurs considerable complexity costs.
KW - D.4.1 [operating systems]: [concurrency, synchronization, multiprocessing]
KW - F.1.2 [modes of computation]: [parallelism and concurrency]
KW - Theory
U2 - 10.1145/2684464.2684473
DO - 10.1145/2684464.2684473
M3 - Conference contribution
AN - SCOPUS:84978720977
T3 - ACM International Conference Proceeding Series
BT - ICDCN 2015 - Proceedings of the 16th International Conference on Distributed Computing and Networking
PB - Association for Computing Machinery
T2 - 16th International Conference on Distributed Computing and Networking, ICDCN 2015
Y2 - 4 January 2015 through 7 January 2015
ER -