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.