5th Workshop on the Theory of Transactional Memory
TransForm/EuroTM WTTM 2013

Invited speakers

   
A Programming Language Perspective on Transactional Memory Consistency
Hagit Attiya - Technion, Israel

Several consistency conditions have been suggested for Transactional memory (TM), yet none of them was proved to formalize the intuitive semantics of atomic blocks, the interface through which a TM is used in a programming language. We formalize the intuitive expectations of a programmer as observational refinement between a concrete TM and an abstract TM: every user-observable behavior of a program using the former can be reproduced if the program uses the latter. This allows to reason about the behavior of a program using the intuitive semantics formalized by the abstract TM and carry the reasoning to the concrete TM. This talk describes, under specific choices of a programming language and notions of observable behavior, which variants of well-known consistency conditions are sufficient for observational refinement and which are necessary. This is joint work with Alexey Gotsman, Sandeep Hans and Noam Rinetzky.

Transactional memory schedulers for diverse distributed computing environments
Costas Busch - Louisiana State University, US

We examine transactional memory schedulers (contention managers) for diverse distributed computing platforms ranging from small scale tightly-coupled multicore systems to larger scale distributed networked multiprocessors. The differences in the distributed computing models require unique algorithmic approaches and evaluation metrics for each case in order to solve efficiently the respective transactional memory scheduling problems. In tightly-coupled systems, the performance emphasis is on the makespan of the transactions, while on networked processors the emphasis is on the message communication complexity. We present efficient scheduling algorithms for these models which can be analyzed formally with provable performance guarantees. In tightly-coupled systems we give an algorithm which groups the transactions together into time windows, allowing multiple transactions per thread to be included in the same window; this permits more flexible scheduling decisions and gives good provable performance bounds with small makespan. In networked systems we present an approach based on distributed directories for arbitrary network topologies which schedules the transactions with small overall communication cost by allowing the shared objects to follow short distance network paths. We also discuss hybrid models, as for example NUMA architectures, which have a well defined structure that combines features from both aforementioned models. We will also present interesting open problems in transactional memory scheduling for various computing platforms.

STM contention management: from multiprocessors to distributed systems
Danny Hendler - Ben-Gurion University, Israel

Transaction collisions are resolved by consulting a contention manager. The effectiveness of contention management has a large impact on the performance of transactional memory implementations, especially when workloads are characterized by high contention. Distributed software transactional memory (DSTM) systems extend the reach of the transactional memory programming model to distributed applications. The design space for DSTM contention management is wider and more complex than that of multiprocessor STMs. Moreover, distributed contention management is intimately connected with the data coherency mechanisms used by the DSTM implementation. In this talk, I will survey contention management techniques used by multiprocessor STM implementations. I will then describe the key approaches underlying contemporary DSTM implementations and the data coherency and contention management mechanisms they use, focusing on replicated DSTMs.

Hybrid implementations of concurrent objects
Michel Raynal - IRISA/University of Rennes 1, France

This talk will focuse on "hybrid implementations" of concurrent objects. Roughly speaking, ``hybrid'' means that lock-based code and mutex-free wait-free) code can be merged in the same implementation. After having defined the notion of a hybrid implementation, the talk will present hybrid implementations of concurrent objects, where each implementation has its own features. If time permits, the talk will also present the notion of an abortable object and will show how a starvation-free implementation of a concurrent object can be systematically obtained from an abortable non-blocking version of the same object. The content of this talk can be found in Chapter 6 of the book "Concurrent Programming: Algorithms, Principles and Foundations" that has recently been published (Springer, 2012, ISBN: 978-3-642-32026-2).