14:00
18:00

Adnane Khattabi thesis: "On Improving the Complexity of Linearizable and Wait-free Implementations of Concurrent Objects by Relaxing their Specifications"

In a distributed context, the different problems of synchronicity between processes are modeled using shared objects. When a new shared object is implemented, it relies on base objects consisting of preexisting implementations, as building blocks. In seeking to maximize the efficiency of these implementations, a new research field has emerged in recent years, with a focus on the possible trade-off between the accuracy of an implementation and its complexity.
We investigate in this thesis how defining relaxed shared objects where the operations are allowed a certain margin of error can result in improved theoretical complexity results. We consider the case study of well-known shared objects, namely: the counter, max register, and FIFO queue.

 

Amphi G (Bât A29)