Master 2013 2014
Stages de la spécialité SAR
Removing the performance bottlenecks of transactional memory

Site :Equipe Regal
Lieu :LIP6, Université Pierre et Marie Curie, site Jussieu
Encadrant : Marc Shapiro, or Tyler Crain
Dates :du 31/03/2014 au 31/08/2014
Rémunération :oui
Mots-clés : Parcours SAR autre qu’ATIAM, recherche


To take advantage of the processing power of today’s multi-core CPUs, programmers must refactor their code into multiple threads that execute in parallel. However, to share and access data concurrently among concurrent threads, both correctly and efficiently, is extremely difficult. Transactional Memory (TM) [3] has been proposed as a high-level abstraction to simplify this task, whereby a transaction appears to execute with no interference, and the underlying TM system relieves the programmer from worrying about synchronization, while allowing concurrency where possible.

Although TMs appear promising, its scalability is still limited [2], in part because they guarantee strong consistency. This has a high memory, processing, and synchronization cost, which is wasted in the common case where conflicts do not occur.

We believe that, for many applications, such strong consistency is not required. We note that several systems and applications successfully use weakened consistency (e.g., SI databases, or NoSQL and key-value stores). A previous work applied Snapshot Isolation to TMs, but found that it too does not scale well either [1] ; we believe that SI is still too strong.

Conflict-free Data Types (CRDTs) [5] represent an interesting intermediate approach, as they require no synchronisation at all, which benefits performance and scalability, while still providing strong enough abstractions to create interesting applications. CRDTs are guaranteed correct thanks to some simple mathematical properties, which enable concurrent updates without any synchronisation. CRDT logic centres on a high-level merge function that considers the logical state of two replicas, and is commutative, associative and idempotent.

We propose to design a new generation of concurrent data structures that will scale well on modern, large-scale, NUMA architectures, based on the principle of CRDTs.

Multicore parallel processing applications may be able to apply some of the same ideas. This Masters’ internship aims to explore and develop TM implementations for shared-memory objects that provide weak transactions, beyond Snapshot Isolation (e.g., NMSI [4]), and leveraging the merge semantics of CRDTs [6].

Snapshot Isolation, despite being weaker than serializability, still has fundamental synchronisation bottlenecks. As SI requires a monotonic order of snapshots, every transaction must synchronise with every other one. Instead, NMSI ensures consistent, but not monotonically-ordered snapshots, maximising concurrency and minimising communication requirements.

Existing CRDT algorithms cannot be applied blindly to CDSes, because the assumptions and trade-offs are different. CRDT logic centres on a high-level merge function that considers the logical state of two replicas, whereas a multicore implements consistency in hardware or in low-level system software with opaque writes to memory. However, we can still leverage the commutativity, associativity and idempotence of merge to remove synchronisation bottlenecks, and to buffer updates to implement isolation cheaply without copying large amounts of state.

Highly scalable TM algorithms will be created by redesign and re-implementing current protocols, removing the scalability limiting synchronization operations, while keeping the scalable concepts. Target applications include ``big data’’ graph processing and constraint solving problems with backtrack.

The research will take place at Université Pierre et Marie Curie (UPMC-Paris 6), Laboratoire d’Informatique de Paris 6 (LIP6), in the Latin Quarter in the centre of Paris.

Requirements : - Enrolled in a Master’s in Computer Science / Informatics or a related field. - Excellent academic record. - Motivated by experimental research. - Skills in algorithms, data structures, concurrency, distributed computing, high-performance computing, operating systems, distributed systems, databases, or a related area.

Please provide a CV, a list of courses and your marks, an essay relevant to the topic (1 to 4 pages), and at least two references (whom we will contact ourselves for a recommendation).

Contact : Marc Shapiro or Tyler Crain


[1] Victor Bushkov, Dmytro Dziuma, Panagiota Fatourou, and Rachid Guerraoui. Snapshot isolation does not scale either. In W. on the Theory of Trans. Mem. (WTTM), Jerusalem, Israel, October 2013.

[2] Calin Cascaval, Colin Blundell, Maged Michael, Harold W. Cain, Peng Wu, Stefanie Chiras, and Siddhartha Chatterjee. Software transactional memory : Why is it only a research toy ? ACM Queue, 6 (5) : 46—58, September 2008.

[3] Transactional memory : Architectural support for lock-free data structures. In Int. Conf. on Comp. Arch. (ISCA), pages 289—300, San Diego CA, USA, May 1993.

[4] Masoud Saeida Ardekani, Pierre Sutra, and Marc Shapiro. Non-Monotonic Snapshot Isolation : scalable and strong consistency for geo-replicated transactional systems. In Symp. on Reliable Dist. Sys. (SRDS), pages 163—172, Braga, Portugal, October 2013.

[5] Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. Conflict-free replicated data types. In Int. Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 386—400, Grenoble, France, October 2011.

[6] Marek Zawirski, Annette Bieniusa, Valter Balegas, Sérgio Duarte, Carlos Baquero, Marc Shapiro, and Nuno Preguiça. SwiftCloud : Fault-tolerant geo-replication integrated all the way to the client machine. Rapport de recherche RR-8347, Institut National de la Recherche en Informatique et Automatique (Inria), August 2014.