European Commission CORDIS

Marie Curie Actions  Seventh Framework Programme (FP7)
TRANSFORM
Research

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: Waheed Ghumman
EPFL ESR3: Victor Bushkov
Technion ESR1: Sandeep Hans
Technion ESR2: David Sainz
TUB ESR1: Srivatsan Ravi
UR1 ESR1: Tyler Crain
UR1 ESR2: Eleni Kanellou
FORTH ESR1: Mykhailo Iaremko
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.

  1. Wait-Free Universal Constructions that ensure Timestamp-Ignoring Disjoint-Access Parallelism. Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani, Corentin Travers, WTTM 2013.
  2. Snapshot Isolation Does Not Scale Either. Victor Bushkov, Dmytro Dziuma, Panagiota Fatourou, Rachid Guerraoui, WTTM 2013.
  3. Safety of Deferred Update in Transactional Memory. Hagit Attiya, Sandeep Hans, Petr Kuznetsov, Srivatsan Ravi, CoRR, vol. abs/1301.6297, 2013.
  4. Abort Free SemanticTM by Dependency Aware Scheduling of Transactional Instructions. Shlomi Dolev, Panagiota Fatourou, Eleftherios Kosmas, TRANSACT 2013.
  5. RELSTM: A Proactive Transactional Memory Scheduler. Hagit Attiya, David Sainz, TRANSACT 2013.
  6. A Programming Language Perspective on Transactional Memory Consistency. Hagit Attiya, Alex Gotsman, Sandeep Hans, Noam Rinetzky, PODC 2013.
  7. A Contention-Friendly Binary Search Tree. Tyler Crain, Vincent Gramoli, Michel Raynal, Euro-Par 2013.
  8. No Hot Spot Non-Blocking Skip List. Tyler Crain, Vincent Gramoli, Michel Raynal, ICDCS 2013.
  9. Composing Relaxed Transactions. Vincent Gramoli, Rachid Guerraoui, Mihai Letia, IPDPS 2013.
  10. Towards a Universal Construction for Transaction-Based Multiprocess Programs. Tyler Crain, Damien Imbs, Michel Raynal, ICDCN 2012.
  11. A speculation-friendly binary search tree. Tyler Crain, Vincent Gramoli, Michel Raynal, PPOPP 2012
  12. On the liveness of transactional memory. Victor Bushkov, Rachid Guerraoui, Michał Kapałka, PODC 2012.
  13. Transactions are Back - but How Different They Are? Sandeep Hans, Hagit Attiya, TRANSACT 2012.
  14. A Contention-Friendly, Non-Blocking Skip List. Tyler Crain, Vincent Gramoli, Michel Raynal, DISC 2012.
  15. STM Systems: Enforcing Strong Isolation between Transactions and Nontransactional Code. Tyler Crain, Eleni Kanellou, Michel Raynal, ICA3PP 2012.
  16. What is Safe in Transactional Memory. Hagit Attiya, Sandeep Hans, Petr Kuznetsov, Srivatsan Ravi, WTTM 2012.
  17. A Single-Version STM that Is Multi-Version Permissive. Hagit Attiya, Eschar Hillel, Theory of Computing Systems, May 2012
  18. Brief Announcement: Read invisibility, virtual world consistency and permissiveness are compatible. Tyler Crain, Damien Imbs, Michel Raynal, SPAA 2011.
  19. Transactional scheduling for read-dominated workloads. Hagit Attiya, Alessia Milani, J. of Parallel and Distr. Computing, Oct. 2012.
  20. Read invisibility, virtual world consistency and permissiveness are compatible. Tyler Crain, Damien Imbs, Michel Raynal, ICA3PP 2011.
  21. Towards a universal construction for transaction-based multiprocess programs. Tyler Crain, Damien Imbs, Michel Raynal, Theoretical Computer Science, Sep. 2012.
  22. Virtual world consistency: A condition for STM systems (with a versatile protocol with invisible read operations). Damien Imbs, Michel Raynal, Theoretical Computer Science, 2012.
  23. Universal constructions that ensure disjoint-access parallelism and wait-freedom. Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani, Corentin Travers, PODC 2012.
  24. Reducing contention in STM. Panagiota Fatourou, Mykhailo Iaremko, Eleftherios Kosmas, George Papadakis, WTTM 2012.
  25. Revisiting the Combining Synchronization Technique. Panagiota Fatourou, Nikolaos Kallimanis, PPoPP 2012.
  26. Composing Relaxed Transactions. Vincent Gramoli, Rachid Guerraoui, Mihai Letia, EPFL Archive.
  27. Brief Announcement: From sequential to concurrent: correctness and relative efficiency. Vincent Gramoli, Petr Kuznetsov, Srivatsan Ravi, PODC 2012.
  28. From sequential to concurrent: correctness and relative efficiency. Vincent Gramoli, Petr Kuznetsov, Srivatsan Ravi, CoRR, vol. abs/1203.4751, 2012.
  29. On the Cost of Concurrency in Transactional Memory. Petr Kuznetsov, Srivatsan Ravi, OPODIS 2011.
  30. On the Cost of Concurrency in Transactional Memory. Petr Kuznetsov, Srivatsan Ravi, CoRR, vol. abs/1103.1302, 2011.
  31. Transactional Memory Repair. Victor Bushkov, Rachid Guerraoui, WTTM 2012.
  32. The complexity of updating snapshot objects. Hagit Attiya, Faith Ellen, Panagiota Fatourou, Journal of Parallel and Distributed Computing, Dec. 2011.
  33. Single-Version STMs can be Multi-version Permissive. Hagit Attiya, Eschar Hillel, ICDCN 2011.
  34. A highly-efficient wait-free universal construction. Panagiota Fatourou, Nikolaos Kallimanis, SPAA 2011
  35. The Many Faces of Transactional Software Composition Vincent Gramoli, Rachid Guerraoui, EPFL Archive
  36. Inherent Limitations on Disjoint-Access Parallel Implementations of Transactional Memory Hagit Attiya, Eshcar Hillel, Alessia Milani, Theor. Comp. Sys., Nov. 2011
  37. Non-blocking binary search trees. Faith Ellen, Panagiota Fatourou, Eric Ruppert, Franck van Breugel, PODC 2010.
  38. The Cost of Privatization. Hagit Attiya, Eschar Hillel, DISC 2010.
  39. Transactional scheduling for read-dominated workloads. Hagit Attiya, Alessia Milani, OPODIS 2009.