On the restricted use of concurrent object

pdf file containing PhD proposal

Name and electronical address of PhD advisors : Colette Johnen (johnen@labri.fr), Alessia Milani (milani@labri.fr)

Laboratory, institution and University : LaBRI, CNRS, UMR 5800,  Université Bordeaux

Address : Bat A30, 351 cours de la libération, 33405 Talence Cedex, France

Mots clés - Keywords :
algorithmique répartie, programmation concurent, mémoire partagée, tolerance aux fautes, Complexité
distributed algorithmic, concurrent computing, Multiprocessors sharing memory, fault tolerant, Complexity

Thématique de la thèse - Thesis thematics : algorithmique distribuée - distributed algorithmic

Project Description

The current revolution of multi-core architectures demands to gain better understanding of the complexity of concurrent objects implementations.

We are interested in fault-tolerant implementations, which allow a process that does not prematurely halt to complete its operations despite the behaviour of the other processes in the system. These implementations are called wait-free. The aim of this thesis is to study the space and time complexity of wait-free implementations that adapt to contention.

Concurrent objects play a key role in the design of concurrent applications. The current revolution of multi-core architectures demands to gain better understanding of the complexity of concurrent objects implementations. We are interested in fault-tolerant implementations, which allow a process that does not prematurely halt to complete its operations despite the behaviour of the other processes in the system. These implementations are called wait-free.

It is known that in an asynchronous read-write shared memory system several fundamental concurrent objects cannot be implemented in a deterministic and fault-tolerant way (e.g. consensus). The difficulty stems from handling executions where processes concurrently operate on the object.

One way to circumvent this impossibility is to only guarantee progress (using reads and writes) in the absence of contention. These implementations are called obstruction-free.
Alternatively, a process is guaranteed to complete, but stronger (and more expensive) synchronization primitives can be applied in the presence of contention.
Today, several bounds have been proved on the complexity of obstruction-free implementations for concurrent objects (e.g.[1,2,3]). On the other hand, the understanding of the complexity of concurrent objects implementations that adapt to contention is still premature (e.g.[4]).

Références