K-set agreement in distributed system

Le k-accord dans un système distribué Les systèmes distribués sont constitués de processus qui collaborent et sont à la base de nombreux services modernes, allant de la banque en ligne aux médias sociaux. Un défi central dans ces systèmes est d'atteindre un consensus pour tous les ordinateurs ou processus. Ce défi est relevé par les algorithmes d'accord, ils jouent un rôle important dans l'assurance du bon fonctionnement d'un système distribué. Ces algorithmes aident à assurer et maintenir la cohérence et fiabilité dans le système. Dans cette thèse, notre préoccupation portait sur le problème du k-accord. Ce problème est une généralisation du problème de consensus conventionnel, il se concentre sur l'obtention d'un accord parmi les processus, où l'accord porte sur au plus k valeurs, k = 1 étant le consensus. La tâche devient complexe lorsque certains processus sont défaillants : soit en tombant en panne (il cesse prématurément et de façon définitive son exécution), soit en se comportant de manière imprévisible. Ces derniers sont appelés comportements Byzantins. Notre objectif est de clarifier les conditions sous lesquelles le k-accord peut être résolu et de délimiter ses limites de résolution. Nous reconnaissons l'importance de la propriété de validité dans la détermination de la résolution et nous nous concentrons sur la propriété de validité forte (Strong Validity en anglais). Cette propriété est vitale lorsqu'il s'agit de relever les défis posés par les processus Byzantins, qui sont connus pour leurs comportements arbitraires. Une réalisation clé de notre recherche est la cartographie quasi-complète de la résolution de l'accord du k-accord. Grâce à de nouveaux algorithmes améliorés, nous avons amélioré l'efficacité du k-accord, en particulier dans des environnements caractérisés par des comportements Byzantins et des délais de transmission des messages limités. Ces environnements sont incorporés dans le système de transmission de messages synchrones Byzantins, et peut être authentifié ou non. Bien que notre principal intérêt était le système de transmission de messages synchrones Byzantins, nous avons également exploré des environnements asynchrones caractérisés par l'imprévisibilité des transmissions de messages et des éventuelles pannes de processus. Ici, nous avons étendu les solutions pour relever ces défis, comblant les lacunes laissées par les études précédentes. En résumé, notre étude offre une analyse exhaustive sur l'accord de k-accord au sein d'un système de transmission de messages synchrones Byzantins, à travers des algorithmes innovants et optimaux.