Abstract FR:

Un objet partagé est un objet accédé logiquement par plusieurs processus à la fois. Le placement sur plusieurs machines d'une copie physique d'un objet partagé est appelée réplication. La réplication permet d'accroître la disponibilité et les performances d'accès des objets partagés dans un système réparti. Cette technique joue un rôle primordiale dans les systèmes d'information modernes. Toutefois, la réplication pose le problèmes de la gestion de la cohérence des répliques en présence d'accès concurrents en écriture, de disfonctionnalités du réseau, ou de défaillances matérielles et logicielles. Consensus est la primitive de communication centrale à la construction d'objets partagés dans un système réparti. La complexité en temps, ou latence, de consensus détermine par conséquent les performances du système dans son ensemble. L'amélioration de la latence de consensus a fait l'objet de nombreux travaux dans la communauté des systèmes répartis. En particulier, l'algorithme Paxos constitue une solution efficace et bien connue à consensus. Dans un article récent, Lamport améliore Paxos. En prenant en compte la commutativité des opérations. La nouvelle primitive de communication obtenue, dénommée Genereralized Paxos, réduit la latence de Paxos lorsque les accès concurrents sont soit commutatifs soit spontanément ordonnés par le réseau. Cependant lorsqu'une collision a lieu, c'est à dire que deux répliques reçoivent des opérations concurrentes et non-commutatives dans des ordres différents, la latence de Generalized Paxos est supérieure à celle de Paxos. Dans la première partie de cette thèse nous présentons un nouvel algorithme pour résoudre le consensus: FGGC. FGGC réduit le délai de recouvrement de Generalized Paxos lorsqu'une collision a lieu. Au cours des exécutions sans faute, la latence de FGGC est optimale: deux étapes de communication si les processus reçoivent les opérations non-commutatives dans le même ordre, et trois dans le cas inverse. Par ailleurs, notre algorithme est optimal au regard des fautes: il tolère f<n/2 fautes où n est le nombre de répliques, et utilise seulement f+1 processus pour progresser. Les processus répartis accèdent rarement le même objet. Il est donc intéressant de répliquer partiellement les objets partagés. La réplication partielle améliore la proximité et donc les performances des accès aux objets partagés, et utilise les ressources de stockage de manière économe. Dans la seconde partie de cette thèse nous traitons de la réplication partielle. Nous présentons deux protocoles de consensus permettant l'accés transparent aux objets répliqués partiellement. Nos protocoles sont authentiques, à savoir, si un commande accède un ensemble O d'objets simultanément, alors seules les répliques des objets inclus dans O exécutent des pas de calcul pour traiter cette commande. Le premier protocole que nous décrivons est sensible a un effet de bord: le convoyage, entre opérations concurrentes qui ralentit leur exécution. Notre deuxième protocole améliore les performances en diminuant l'effet de convoyage. Une évaluation montre l'efficacité de notre approche.