Supervision : Marc SHAPIRO

Protocoles efficaces pour le consensus généralisé et la réplication partielle

Un objet accédé par plusieurs processus est dit partagé. Dans un système réparti, un tel objet est généralement répliqué, c'est-à-dire que l'on place des copies physiques de l'objet logique sur plusieurs machines. La réplication permet d'accroître la disponibilité et les performances ; cette technique joue un rôle primordial dans les systèmes d'information modernes. Toutefois, si l'objet subit des écritures, la réplication pose le problème de la cohérence des répliques. Le thème principal de cette thèse est la gestion de la cohérence en présence d'accès concurrents, de dysfonctionnement du réseau, ou de défaillances matérielles et logicielles. Pour cela, la primitive d'ordonnancement des opérations, dit consensus (résolu entre autres par l'algorithme Paxos), occupe une place centrale. La latence du consensus détermine donc les performances du système dans son ensemble ; son amélioration constitue un sujet de choix de la recherche en algorithmique répartie. Des travaux récents généralisent le consensus en prenant en compte l'existence de classes d'équivalence d'ordonnancement, ce qui permet de diminuer la latence lorsque les opérations sont, soit commutatives, soit pré-ordonnées par le réseau. Ainsi, l'extension de Paxos au consensus généralisé, dénommé Generalized Paxos, n'ordonne pas les opérations dans ces cas-là. Cependant, lorsqu'une collision a lieu, c'est-à-dire que deux répliques reçoivent des opérations non-commutatives dans des ordres différents, Generalized Paxos entre dans une phase de recouvrement, dont la latence est bien supérieure à celle de Paxos. Dans la première partie de la thèse nous présentons le protocole FGGC de consensus généralisé que nous avons conçu pour minimiser le coût du recouvrement. Profitant pleinement de la liberté d'ordonnancement permise par le consensus généralisé, FGGC présente une latence optimale (deux étapes de communication si les processus reçoivent les opérations non-commutatives dans le même ordre, et trois autrement) au cours d'une exécution sans faute. De plus, FGGC est optimal par rapport aux fautes : il tolère $f

1 PhD graduated 2014

2006-2021 Publications