On improving complexity of linearizable and wait-free implementations of concurrent objects by relaxing their specifications.

Dans un contexte distribué, les différents problèmes de synchronicité entre processus sont modélisés à l'aide d'objets partagés. Lorsqu'un nouvel objet partagé est implémenté, on s'appuie souvent sur des objets de base préexistants. En cherchant à maximiser l'efficacité de ces implémentations, un nouveau domaine de recherche a émergé ces dernières années, centré sur le compromis possible entre la précision d'une implémentation et sa complexité.Nous étudions dans cette thèse la définition d’objets partagés relaxés où les opérations ont le droit à une certaine marge d'erreur, et comment cela peut améliorer la complexité de leurs implémentations. Nous considérons le cas d'objets partagés connus : counter, max register, et FIFO queue.Tout d'abord, nous étudions la possibilité d’améliorer la complexité des implémentations relaxée du counter et max register par rapport à leurs implémentations exactes. Dans le modèle de mémoire partagée classique, nous étudions dans quelle mesure permettre aux implémentations linéarisables et wait-free de ces objets de retourner des valeurs approximatives, plutôt que des valeurs précises, peut améliorer leur complexité.Nous considérons le k-multiplicatif max register et le k-multiplicatif counter, où les opérations de lecture sont autorisées à se tromper d'un facteur multiplicatif de k. Nous présentons une implémentation du k-multiplicatif counter wait-free linéarisable pour k ≥ n avec une complexité de pas amortie constante où n est le nombre de processus. Nous montrons également qu'en bornant l'exécution, nous sommes capables d'implémenter le counter k-multiplicatif pour k≥√ n d'une manière linéarisable wait-free avec une complexité de pas dans le pire des cas de O(min(log(log( m+1)), n)) où m représente la limite du nombre d'opérations CounterIncrement lors d'une exécution. Les deux implémentations offrent une amélioration exponentielle de la complexité de leurs équivalents exacts dans l'état de l'art.Ensuite, nous montrons que la relaxation de la sémantique du max register en autorisant l'imprécision d'un facteur multiplicatif constant produit une amélioration exponentielle de la complexité de pas dans le pire des cas pour la variante bornée, et de la complexité de pas amortie pour la variante non bornée.Afin de mesurer les limites de ces relaxations, nous étudions les bornes inférieures de la complexité du counter et max register k-multiplicatif. Nous obtenons le résultat que lorsque le paramètre d'approximation k ne dépend pas du nombre de processus, assouplir la sémantique du counter en autorisant l'imprécision d'un facteur multiplicatif ne peut asymptotiquement réduire la complexité des pas amortis des compteurs non bornés de plus d'un facteur logarithmique. Nous prouvons également que notre max register k-multiplicatif borné est optimal.En ce qui concerne la FIFO queue, la conception d'implémentations efficaces wait-free est complexe malgré son utilisation dans de nombreuses applications distribuées. La plupart des implémentations des FIFO queue dans la littérature s'appuient sur des contraintes de concurrence : tous les processus ne sont pas autorisés à exécuter des opérations de Enqueue et de Dequeue.Dans cette thèse, nous étudions la possibilité d'implémenter la FIFO queue d’une façon wait-free avec une complexité logarithmique dans le pire des cas sans contraintes de concurrence. Par conséquent, nous présentons une implémentation qui prend en charge n enqueuers et k dequeuers où la complexité dans le pire des cas d'une opération Enqueue est en O (log n) et où la complexité de l'opération Dequeue dépend du niveau de concurrence et est O(k log n) dans le pire des cas.Nous nous appuyons ensuite sur l'assouplissement de la sémantique de la FIFO queue pour montrer que le fait d'autoriser des opérations Dequeue concurrentes à retourner le même élément engendre une implémentation avec une complexité en O (log n) dans le pire des cas pour les opérations Enqueue et Dequeue.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