On improving 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.First, we study the possible improvement in step complexity of the relaxed implementation of the counter and max register objects compared to their exact implementations. In the classical shared memory model, we investigate the extent to which allowing wait-free linearizable implementations of these objects to return approximate values, rather than accurate ones, may improve their step complexity.We consider the k-multiplicative-accurate max register and the k-multiplicative-accurate counter, where read operations are allowed to err by a multiplicative factor of k. We give a wait-free linearizable k-multiplicative-accurate counter implementation for k ≥ n with constant amortized step complexity where n is the number of processes. We also show that by bounding the execution, we are able to implement the k-multiplicative-accurate counter for k≥√ n in a wait-free linearizable manner and with a worst-case step complexity of O(min(log(log(m+1)), n)) where m represents the bound on the number of CounterIncrement operations during an execution. Both implementations offer an exponential improvement on the complexities of their exact counterparts in the state of the art.Then, we show that relaxing the semantics of max registers by allowing inaccuracy of even a constant multiplicative factor yields an exponential improvement in the worst-case step complexity of the bounded variant and in the amortized step complexity of the unbounded one.For the sake of gauging the limitations of these relaxations, we study the lower bounds of the complexity of the k-multiplicative-accurate counter and max register in both their bounded and unbounded variations. We obtain the result that when the approximation parameter k does not depend on the number of processes, relaxing counter semantics by allowing inaccuracy of a multiplicative factor cannot asymptotically reduce the amortized step complexity of unbounded counters by more than a logarithmic factor. We also prove that our bounded k-multiplicative-accurate max register is optimal and matches the lower bound.When it comes to the FIFO queue, designing efficient wait-free implementations remains a challenge despite its usage in many distributed applications. Most of the FIFO queue implementations in the literature rely on concurrency constraints: not all processes are allowed to execute either/or Enqueue and Dequeue operations.In this thesis, we investigate whether it is possible to implement a logarithmic worst-case step complexity wait-free implementation that does not suffer from concurrency constraints. Therefore, we present a wait-free FIFO queue implementation that supports n enqueuers and k dequeuers where the worst-case step complexity of an Enqueue operation is in O(log n) and where the complexity of the Dequeue operation depends on the level of concurrency during the execution and is O(k log n) in the worst-case scenario.We then rely on the relaxation of the FIFO queue semantics to show that allowing concurrent Dequeue operations to retrieve the same element results in an implementation with O(log n) worst-case step complexity for both the Enqueue and Dequeue operations.