Breaching the Wall of Impossibility Results on Disjoint-Access Parallel TM.
Sebastiano Peluso, Roberto Palmieri, Paolo Romano, Binoy Ravindran, Francesco Quaglia · International Conference on Distributed Computing · 2014
Transactional Memory (TM) is a powerful abstraction for synchronizing activities of different threads through transactions. TM implementations guaranteeing Disjoint-Access Parallelism (DAP) are highly desirable on current multi-core architectures because they can exploit low-level parallelism. Unfortunately, a number of results have been proved concerning the impossibility of implementing TMs that guarantee different variants of the DAP property, as well as alternative consistency and liveness criteria. This paper looks for a breach in the wall of existing impossibility results, by attempting to identify the strongest consistency and liveness guarantees that a TM can ensure while remaining scalable — by ensuring DAP — and maximizing efficiency in read-dominated workloads — by having invisible and wait-free readonly transactions. We show that implementing such a TM is indeed possible if one adopts as consistency criterion Extended Update Serializability, combined with a weaker variant of real-time order, which we name Witnessable Real Time Order. Interestingly the resulting semantics share a number of similarities with classic TM safety criteria like Opacity and Virtual World Consistency, while allowing for scalable and efficient implementations. Along the path of designing this protocol, we report two impossibility results related to ensuring realtime order in a weakly DAP TM that guarantees wait-free read-only transactions considering different progress criteria and both visible and invisible read-only transactions. Finally, we also provide a lower bound on the space complexity of a strictly DAP TM that ensures a very weak consistency criterion, called Consistent View. We leverage this result to prove that the proposed protocol is optimal in terms of per object version spatial utilization.