Research Overview
The project aims at building the theoretical underpinning for the design and analysis of efficient transactional-memory (TM) systems. One of the major objectives of the project is to come up with a coherent view of the theory of TM computing, shedding light on the fundamental issues underlying their design.
Nowadays, the TM programming paradigm currently provides probably the most promising simplification to the problem of writing concurrent programs which is currently the major obstacle in taking full advantage of modern multi-core architectures. Therefore, deep understanding of the capabilities and the properties of TM systems is highly desirable, albeit not an easy task. Many difficulties are encountered: several, sometimes contradictory, performance parameters must be taken into consideration, and different trade-offs should be identified. Many of these difficulties come from the lack of commonly accepted, precise definitions and rules to describe and govern such systems. However, the explosive growth of multi-core machines makes it imperative to understand how to overcome these difficulties as soon as possible.
This project aspires to be a highly successful endeavour in this direction. It aims at formulating precisely the semantics of TM systems, generating a common framework for specifying algorithms and comparing their performance, proposing appropriate correctness criteria, safety and liveness properties to capture the needs of modern distributed applications, studying important trade-offs, exploring different complexity measures that are of interest, designing and analyzing new efficient implementations to overcome all intrigued complications that may arise, understanding inherent limitations, and proving optimality results.
The project will act as a mediator between the current state-of-the-art TM systems and the lack of hindsight to evaluate them and discover whether they can cover the needs of modern applications.
ESR Activity
To date, the project has employed several Early Stage Researchers (ESRs) network-wide, which work on the aforementioned goals set by Transform. The personal webpages of the ESRs, listed below, contain more detail on their individual research projects and directions.
| ESR Personal Pages |
|
| EPFL ESR1: | Mihai Letia |
| EPFL ESR2: | Victor Bushkov |
| Technion ESR1: | Sandeep Hans |
| Technion ESR2: | David Sainz |
| TUB ESR1: | Srivatsan Ravi |
| UR1 ESR1: | Tyler Crain |
| UR1 ESR2: | Eleni Kanellou |
| FORTH ESR2: | Md Forhad Rabbi |
| FORTH ESR3: | Dmytro Dziuma |
| FORTH ESR4: | Kasra Amirtahmasebi |
Transform Publications
In the context of Transform, key scientist as well as ESRs
of the project have made several publications of obtained
results. A selection is presented here.
- Sharing a Sequential Program: Correctness and Relative Efficiency. Petr Kuznetsov, Srivatsan Ravi, PODC 2012.
- Towards a Universal Construction for Transaction-Based Multiprocess Programs. Tyler Crain, Damien Imbs, Michel Raynal, ICDCN 2012.
- A speculation-friendly binary search tree. Tyler Crain, Vincent Gramoli, Michel Raynal, PPOPP 201.2
- On the liveness of transactional memory. Victor Bushkov, Rachid Guerraoui, Michał Kapałka, PODC 2012.
- Transactions are Back - but How Different They Are? Sandeep Hans, Hagit Attiya, TRANSACT 2012.
- A Contention-Friendly, Non-Blocking Skip List. Tyler Crain, Vincent Gramoli, Michel Raynal, DISC 2012.
- STM Systems: Enforcing Strong Isolation between Transactions and Nontransactional Code. Tyler Crain, Eleni Kanellou, Michel Raynal, ICA3PP 2012.
- What is Safe in Transactional Memory. Hagit Attiya, Sandeep Hans, Petr Kuznetsov, Srivatsan Ravi, WTTM 2012.
- A Single-Version STM that Is Multi-Version Permissive. Hagit Attiya, Eschar Hillel, Theory of Computing Systems, May 2012
- Read invisibility, virtual world consistency and permissiveness are compatible. Tyler Crain, Damien Imbs, Michel Raynal, SPAA 2011.
- Transactional scheduling for read-dominated workloads. Hagit Attiya, Alessia Milani, J. of Parallel and Distr. Computing, Oct. 2012.
- Read invisibility, virtual world consistency and permissiveness are compatible. Tyler Crain, Damien Imbs, Michel Raynal, ICA3PP 2011.
- Towards a universal construction for transaction-based multiprocess programs. Tyler Crain, Damien Imbs, Michel Raynal, Theoretical Computer Science, Sep. 2012.
- Stretching transactional memory. Aleksandar Dragojević, Rachid Guerraoui, Michał Kapałka, ACM SIGPLAN Notices, May 2009.
- Universal constructions that ensure disjoint-access parallelism and waitfreedom. Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani, Corentin Tranvers, PODC 2012.
- Reducing contention in STM. Panagiota Fatourou, Mykhailo Iaremko, Eleftherios Kosmas, George Papadakis, WTTM 2012.
- Revisiting the Combining Synchronization Technique. Panagiota Fatourou, Nikolaos Kallimanis, PPoPP 2012.
- Composing Relaxed Transactions. Vincent Gramoli, Rachid Guerraoui, Mihai Letia, EPFL Archive.
- From sequential to concurrent: correctness and relative efficiency. Vincent Gramoli, Petr Kuznetsov, Srivatsan Ravi, PODC 2012.
- Sharing a Sequential Program: Correctness and Concurrency Analysis. Vincent Gramoli, Petr Kuznetsov, Srivatsan Ravi, CoRR, arXiv:1203.4751, 2012.
- On the correctness of Transactional Memory. Rachid Guerraoui, Michal Kapalka, PPoPP 2008.
- On the Cost of Concurrency in Transactional Memory. Petr Kuznetsov, Srivatsan Ravi, OPODIS 2011.
- Transactional Memory Repair. Victor Bushkov, Rachid Guerraoui, WTTM 2012.
- The complexity of updating snapshot objects. Hagit Attiya, Faith Ellen, Panagiota Fatourou, Journal of Parallel and Distributed Computing, Dec. 2011.
- The Cost of Privatization. Hagit Attiya, Eschar Hillel, DISC 2010.
- A Single-Version STM that is Multi-version Permissive. Hagit Attiya, Eschar Hillel, ICDCN 2011.
- Non-blocking binary search trees. Faith Ellen, Panagiota Fatourou, Eric Ruppert, Franck van Breugel, PODC 2010.
- A highly-efficient wait-free universal construction. Panagiota Fatourou, Nikolaos Kallimanis, SPAA 2011
- The Many Faces of Transactional Software Composition Vincent Gramoli, Rachid Guerraoui, EPFL Archive