Modèles de synchronisation et de défaillance

Les modèles de synchronisation et de défaillance spécifient ce qu'un algorithme distribué peut supposer concernant les délais de message et les vitesses de processeur, ainsi que la manière dont les composants sont autorisés à tomber en panne.

Definition

Un modèle de synchronisation fixe les hypothèses concernant les bornes supérieures du temps de livraison des messages et de la vitesse relative des processus, tandis qu'un modèle de défaillance fixe l'ensemble des manières dont les processus et les canaux peuvent s'écarter de leur comportement spécifié.

Scope

Ce sujet couvre les modèles de synchronisation synchrones, asynchrones et partiellement synchrones ; la taxonomie des défaillances, allant des pannes (fail-stop) aux fautes arbitraires (byzantines), en passant par les omissions et les problèmes de synchronisation ; et l'abstraction des détecteurs de défaillance qui relie les systèmes asynchrones et le raisonnement basé sur les délais d'attente (timeout). Ces modèles constituent les axiomes à partir desquels sont dérivés les résultats de possibilité et d'impossibilité.

Core questions

• Quelles bornes sur le délai et la vitesse un algorithme peut-il supposer, et comment les délais d'attente (timeouts) en dépendent-ils ?
• Quelles classes de défaillance — panne (crash), omission, synchronisation, byzantine — un protocole doit-il masquer ?
• Comment les systèmes asynchrones peuvent-ils être augmentés de détecteurs de défaillance pour contourner les résultats d'impossibilité ?

Key theories

Synchronisation partielle

Les systèmes réels ne sont ni entièrement synchrones ni entièrement asynchrones ; le modèle partiellement synchrone suppose des bornes sur le délai et la vitesse qui sont valables à terme ou sont inconnues, ce qui est suffisant pour résoudre le consensus tout en restant réaliste.

Hiérarchie des modèles de défaillance

Les défaillances vont des pannes (crashes) bénignes de type « fail-stop », en passant par les omissions d'envoi/réception et les violations de synchronisation, jusqu'au comportement byzantin arbitraire ; la gravité des défaillances qu'un protocole doit tolérer dicte le facteur de réplication et la complexité des messages requis.

Détecteurs de défaillance non fiables

Un détecteur de défaillance abstrait fournit des indications potentiellement incorrectes sur les processus qui sont tombés en panne ; la caractérisation du détecteur le plus faible suffisant pour résoudre le consensus réconcilie la rigueur asynchrone avec les implémentations pratiques basées sur les délais d'attente (timeouts).

Clinical relevance

Les systèmes de production choisissent implicitement un modèle de synchronisation et de défaillance chaque fois qu'ils définissent des délais d'attente (timeouts), choisissent un facteur de réplication ou décident de se défendre contre des participants malveillants ; des hypothèses erronées sont une cause fréquente d'incidents de type « split-brain » et de perte de données.

History

Après que le modèle asynchrone se soit avéré trop faible pour un consensus tolérant aux pannes, Dwork, Lynch et Stockmeyer ont introduit la synchronisation partielle en 1988, et Chandra et Toueg ont formalisé les détecteurs de défaillance non fiables en 1996, fournissant ainsi les outils de modélisation qui rendent possible un accord pratique tolérant aux pannes.

Debates

Les délais d'attente (timeouts) sont-ils une hypothèse de synchronisation ou un détecteur de défaillance ?

Une perspective considère les délais d'attente (timeouts) comme encodant une borne de synchronisation (éventuelle) ; une autre les considère comme une implémentation d'un détecteur de défaillance abstrait. Les deux cadres sont largement équivalents mais mettent l'accent sur des frontières de conception différentes entre le modèle de réseau et l'algorithme.

Key figures

• Cynthia Dwork
• Nancy Lynch
• Larry Stockmeyer
• Tushar Chandra
• Sam Toueg

Seminal works

• dwork1988
• chandra1996
• lynch1996

Frequently asked questions

Pourquoi la détection fiable des défaillances ne peut-elle pas être implémentée dans un système purement asynchrone ?

Sans bornes sur le délai des messages, un processus arbitrairement lent mais actif est indiscernable d'un processus en panne, de sorte que tout détecteur doit parfois se tromper. C'est pourquoi les systèmes asynchrones sont augmentés d'hypothèses de synchronisation ou de détecteurs non fiables.