Mechanizing Asynchronous Distributed Algorithms in Rocq: The Echo Algorithm as a Case Study

Dans les vastes réseaux invisibles qui alimentent notre monde moderne, les ordinateurs échangent constamment des informations pour résoudre des problèmes ensemble. Ces systèmes, connus sous le nom d'algorithmes distribués, sont les moteurs invisibles derrière tout, des transactions bancaires mondiales au routage du trafic Internet. Contrairement à un ordinateur unique qui suit un ensemble strict et linéaire d'instructions, un système distribué est une collection de machines indépendantes qui doivent se coordonner sans chef central. Ils opèrent dans un environnement asynchrone, ce qui signifie qu'il n'existe pas d'horloge unique pour les synchroniser ; les messages voyagent à des vitesses imprévisibles, et l'ordre dans lequel ils arrivent peut varier considérablement. Ce manque de calendrier global crée un défi unique : comment pouvons-nous être certains qu'un système se comportera correctement lorsque la chronologie des événements est chaotique et imprévisible ? Pendant des décennies, les mathématiciens et les informaticiens se sont appuyés sur la vérification formelle, une méthode rigoureuse utilisant la logique pour prouver qu'un système ne peut pas échouer, plutôt que de simplement le tester pour voir s'il fonctionne la plupart du temps.

Une équipe de chercheurs a maintenant appliqué cette logique rigoureuse à un problème classique de l'informatique connu sous le nom d'algorithme d'Écho (Echo algorithm). Cet algorithme est une méthode fondamentale pour qu'un réseau d'ordinateurs se mette d'accord sur une structure, construisant essentiellement une carte de leurs connexions afin qu'un ordinateur central, l'initiateur, puisse communiquer avec tous les autres nœuds. Le processus est simple en concept : l'initiateur envoie un signal, ou un « jeton », à ses voisins. Ces voisins transmettent le jeton à leurs propres voisins, et finalement, le signal se propage à travers tout le réseau. Une fois qu'un nœud a reçu le jeton et a entendu en retour de tous ses voisins, il envoie une réponse, ou un « écho », vers l'origine. L'initiateur attend d'avoir reçu les échos de tout le monde avant de déclarer la tâche terminée. Bien que l'idée semble directe, prouver que ce processus fonctionne correctement sous chaque scénario possible de délais et de réordonnancement de messages est notoirement difficile. Les chercheurs, travaillant avec un assistant de preuve spécialisé appelé Rocq, ont réussi à construire une preuve formelle qui démontre la fiabilité de l'algorithme, montrant spécifiquement que si l'initiateur décide que la tâche est terminée, le réseau a effectivement été entièrement exploré.

Le cœur de ce travail réside dans la création d'un jumeau numérique de l'algorithme suffisamment précis pour ne laisser aucune place à l'ambiguïté. Les chercheurs ont modélisé l'ensemble du réseau comme un état unique et évolutif. Cet état comprend le statut actuel de chaque ordinateur individuel et une collection de tous les messages circulant actuellement entre eux. Dans ce modèle, le mouvement des messages n'est pas régi par une horloge, mais par un ensemble de règles permettant à n'importe quel message d'être livré à n'importe quel moment, reflétant la réalité chaotique des réseaux asynchrones. Les chercheurs ont ensuite défini un ensemble de règles logiques, ou invariants, qui doivent toujours être respectés, peu importe la façon dont les messages sont mélangés. Ces règles agissent comme des garde-fous, garantissant que le système n'entre jamais dans un état où un ordinateur pense avoir terminé le travail alors qu'une partie du réseau est encore en attente.

La découverte la plus significative de cette étude est une preuve conditionnelle concernant le moment de la décision. Les chercheurs ont prouvé que si l'ordinateur initiateur atteint un état où il croit que la tâche est terminée, alors chaque autre ordinateur du réseau doit posséder un chemin de connexions clair et fini menant de nouveau à cet initiateur. En d'autres termes, le réseau a réussi à former une structure en arbre enracinée à l'initiateur, sans boucles ni îles déconnectées. Cette preuve est remarquable car elle est vraie quel que soit l'ordre dans lequel les messages arrivent. Elle tient compte de scénarios complexes et désordonnés où les messages pourraient se croiser sur la même connexion, ou bien où un ordinateur pourrait recevoir un second signal après avoir déjà commencé à travailler. Les chercheurs ont montré que même dans ces situations enchevêtrées, la logique de l'algorithme empêche l'initiateur de prendre une décision prématurée. S'il reste un message flottant dans le réseau destiné à un ordinateur qui n'a pas encore commencé, les compteurs internes de l'initiateur l'empêcheront de déclarer la victoire.

Pour y parvenir, l'équipe a dû séparer le problème en couches de logique distinctes. Ils ont d'abord établi des faits structurels, s'assurant que chaque connexion qu'un ordinateur établit est valide et qu'aucun ordinateur ne pointe vers lui-même. Ils ont ensuite prouvé une couche causale, montrant que si un ordinateur a envoyé un signal, il doit avoir un ordinateur parent qui lui a envoyé un signal auparavant, créant ainsi une chaîne remontant jusqu'au début. Enfin, ils ont abordé la couche de comptabilité, qui suit le nombre de messages envoyés et reçus. Cette comptabilité est la clé de la preuve : elle lie l'état local d'un seul ordinateur à l'état global de l'ensemble du réseau. Les chercheurs ont démontré qu'un ordinateur ne peut pas terminer son travail tant qu'il n'a pas reçu de réponses de tous ses voisins, et que cette exigence remonte la chaîne de connexions jusqu'à l'initiateur. Si même un seul ordinateur est encore en attente d'un message, le compteur de l'initiateur le reflétera, empêchant la décision finale.

Ce travail n'est pas une simulation ou un test sur un réseau de taille spécifique ; c'est une preuve mathématique qui s'applique à tout graphe fini listé satisfaisant des hypothèses spécifiques. Les chercheurs ont utilisé un outil appelé Rocq, un assistant de preuve formelle, pour vérifier chaque étape de leur logique. Le code résultant, qui contient plus de cent quarante déclarations logiques distinctes, a été vérifié par l'ordinateur lui-même comme étant exempt d'erreurs. Cela signifie que la preuve n'est pas seulement un argument humain qui pourrait contenir une faille cachée, mais une garantie vérifiée par machine. Les chercheurs n'ont pas prouvé que l'algorithme finira toujours, car cela nécessiterait de supposer que les messages seront éventuellement livrés, une condition qu'ils ont délibérément écartée pour garder la preuve concentrée sur la sécurité. Au lieu de cela, ils ont prouvé que si l'algorithme se termine, il se termine correctement.

Cette réussite souligne un changement dans la manière dont nous pouvons vérifier des systèmes complexes. En décomposant le problème en composants réutilisables, les chercheurs ont créé une méthode qui pourrait potentiellement être appliquée à d'autres algorithmes distribués à l'avenir, bien que l'artéfact actuel ne soit pas un cadre de vérification plug-in pour des algorithmes arbitraires et nécessiterait une refonte pour d'autres cas. Bien que le présent travail se concentre spécifiquement sur l'algorithme d'Écho, la méthode consistant à séparer les règles structurelles de la logique de comptabilité offre un modèle pour aborder d'autres problèmes où le timing est incertain. La preuve confirme que même dans un monde de délais imprévisibles, il est possible de construire des systèmes mathématiquement certains de se comporter comme prévu. Les chercheurs ont mis leur code et leurs preuves à la disposition d'autrui pour inspection et développement, fournissant une base solide pour les travaux futurs visant à assurer la fiabilité des réseaux numériques qui soutiennent la société moderne.