Amélioration de complexité d'implémentations linéarisables et wait-free d'objets concurrents en relaxant leurs spécifications. ; On improving complexity of linearizable and wait-free implementations of concurrent objects by relaxing their specifications
Titel:
Amélioration de complexité d'implémentations linéarisables et wait-free d'objets concurrents en relaxant leurs spécifications. ; On improving complexity of linearizable and wait-free implementations of concurrent objects by relaxing their specifications
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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 ...