Nuno Miguel Rei Carvalho

A Generic and Distributed Dependable Software Transactional Memory

Thesis submitted for the PhD in Computer Science and Engineering, Instituto Superior Técnico (IST), Universidade Técnica de Lisboa

Abstract

A Software Transactional Memory (STM) is an abstraction that aims at simplifying the development of concurrent programs. When using STMs, the programmers are not required to manage explicitly concurrency control, for instance, by using low-level synchronization mech- anisms such as locks. Instead, programmers only need to identify the sequences of operations that need to be executed in isolation, using the concept of a transaction. Concurrency control is then performed by the runtime support, in a transparent manner to the programmer.

This thesis addresses the problem of implementing distributed dependable STMs. A dis- tributed STM provides the abstraction of a global address space, that can be accessed from threads in different nodes as a local STM. Furthermore, a dependable STM ensures that multi- ple copies of the data are maintained, and kept consistent, such that data is not lost if a node fails. These features need to be added to STMs to address the high availability and scalability requirements posed by realistic production environments (e.g. the F ́enixEDU system).

One of the most challenging problems in the management of replicated data is to reduce the cost of preserving replica consistency, a task that requires coordination among replicas. Given that the costs of executing an in-memory transaction are much smaller than executing transactions in other settings (such as in database systems), there is the risk that coordination costs become prohibitively expensive. Therefore, the thesis proposes several novel replication protocols suitable for building dependable distributed STMs. The results reported in the thesis, show that it is unlikely that a single replication protocol can outperform all the other protocols, for all workloads that characterize STMs environments. Therefore, the thesis also proposes a generic architecture that allows multiple replication proto- cols to coexist in a seamless manner in the same STM. This architecture opens the door to build adaptive solutions that can dynamically and automatically select the best replication protocol for a given deployment and workload, thus paving the way to the implementation of autonomic distributed dependable STMs that offer good performance in a wide range of scenarios.

Selected Publications

A Generic and Distributed Dependable Software Transactional Memory
Nuno Miguel Rei Carvalho
PhD Thesis. Departamento de Engenharia Informática, Instituto Superior Técnico (IST), Universidade Técnica de Lisboa
September, 2011.
Available pdf.
A Generic Framework for Replicated Software Transactional Memories.
N. Carvalho, P. Romano, and L. Rodrigues.
In proceedings of the 10th IEEE International Symposium on Network Computing and Applications (IEEE NCA11), Cambridge (MA), USA, August 2011.
(short paper).
Available BibTeX, abstract (html) and report (pdf).
SCert: Speculative Certification in Replicated Software Transactional Memories.
N. Carvalho, P. Romano and L. Rodrigues.
In proceedings of the 4th Annual International Systems and Storage Conference (SYSTOR 2011), Haifa, Israel, May 2011.
Available BibTeX, abstract (html) and report (pdf).
Asynchronous Lease-based Replication of Software Transactional Memory.
N. Carvalho, P. Romano and L. Rodrigues.
In proceedings of the ACM/IFIP/USENIX 11th Middleware Conference, Bangalore, India, Nov 2010.
Available BibTeX, abstract (html) and report (pdf).
Versioned Transactional Shared Memory for the FenixEDU Web Application.
N. Carvalho, J. Cachopo, L. Rodrigues, and A. Rito Silva.
Second Workshop on Dependable Distributed Data Management (in conjunction with Eurosys 2008), Glasgow, Scotland, March 31, 2008.
Available BibTeX, abstract (html) and report (pdf).

Contact information

O Nuno Carvalho is a researcher at Fujitsu Laboratories of Europe Limited.

Luís Rodrigues