Modèles de systèmes distribués

Les modèles de systèmes distribués sont les hypothèses abstraites — concernant l'architecture, la synchronisation, la communication et les défaillances — qui définissent ce sur quoi un algorithme distribué peut s'appuyer et ce qu'il doit tolérer.

Definition

Un système distribué est une collection d'ordinateurs indépendants qui communiquent uniquement par l'échange de messages et qui apparaît à ses utilisateurs comme un système cohérent unique ; un modèle de système est l'ensemble des hypothèses concernant les processus, les canaux de communication, la synchronisation et les défaillances sous lesquelles un tel système est analysé.

Scope

Ce domaine couvre les modèles architecturaux et physiques des systèmes distribués (clients, serveurs, pairs et organisations multiniveaux), les modèles de synchronisation qui distinguent l'exécution synchrone de l'exécution asynchrone, les modèles de défaillance fondamentaux (panne, omission, temporisation et byzantin), et les abstractions de communication telles que le passage de messages, la mémoire partagée, l'invocation à distance et les intergiciels (middleware). Ces modèles encadrent chaque résultat dans le domaine : un algorithme correct sous un modèle peut s'avérer impossible sous un autre, de sorte que l'explicitation du modèle est un prérequis pour raisonner sur la correction et la performance.

Sub-topics

• Passage de messages et mémoire partagée
• Invocation à distance et intergiciel
• Modèles de systèmes et d'architectures
• Modèles de synchronisation et de défaillance

Core questions

• Quelles hypothèses concernant la synchronisation, la communication et les défaillances un algorithme distribué donné requiert-il ?
• En quoi les modèles synchrones et asynchrones diffèrent-ils, et pourquoi cette distinction modifie-t-elle ce qui est calculable ?
• Quelles classes de défaillances de processus et de canaux un protocole doit-il tolérer pour être correct ?
• Quand un système devrait-il être structuré autour du passage de messages plutôt que d'une abstraction de mémoire partagée ou d'invocation à distance ?

Key theories

Modèles synchrones versus asynchrones

Dans un modèle synchrone, il existe des bornes connues pour le délai des messages et la vitesse relative des processeurs, permettant l'utilisation de temporisations (timeouts) pour détecter les défaillances ; dans un modèle asynchrone, de telles bornes n'existent pas, ce qui rend la détection des défaillances fondamentalement peu fiable et est à la base de nombreux résultats d'impossibilité.

Hiérarchie des modèles de défaillance

Les défaillances de processus et de canaux sont classées du bénin au sévère — panne (fail-stop), omission, temporisation et arbitraire (byzantine) — des garanties plus fortes étant nécessaires pour masquer les défaillances plus graves ; le modèle choisi détermine à la fois la résilience atteignable et le coût d'un protocole.

Abstractions de communication

Le calcul distribué est construit sur un petit ensemble de primitives d'interaction — passage de messages asynchrone et synchrone, mémoire partagée distribuée et invocation de procédure ou de méthode à distance — chacune avec des sémantiques distinctes pour la livraison, l'ordonnancement et la défaillance qui façonnent la conception de niveau supérieur.

Clinical relevance

Le choix du bon modèle est la première décision de conception dans tout système réel : les plateformes cloud, les bases de données et les services de coordination déclarent tous un modèle de synchronisation (souvent partiellement synchrone) et un modèle de défaillance, et ces choix déterminent les garanties de cohérence, de disponibilité et de tolérance aux pannes que le système peut promettre.

History

Les premières recherches sur les systèmes distribués dans les années 1970 et 1980 visaient à identifier les hypothèses minimales sous lesquelles la coordination distribuée est possible, produisant la dichotomie synchrone/asynchrone et une taxonomie des défaillances. Ces modèles ont été consolidés dans des manuels par Lynch, Attiya et Welch, Tanenbaum et van Steen, et Coulouris et ses collègues, devenant le vocabulaire partagé de l'ensemble du domaine.

Debates

Dans quelle mesure le modèle asynchrone est-il réaliste pour les systèmes pratiques ?

Le modèle asynchrone pur est prouvé comme étant le plus difficile à programmer et exclut la détection fiable des défaillances, pourtant la plupart des réseaux réels ne sont que sporadiquement lents ; les modèles partiellement synchrones et les détecteurs de défaillances sont apparus comme un compromis pragmatique qui conserve la rigueur tout en admettant les temporisations.

Key figures

• Leslie Lamport
• Nancy Lynch
• Andrew S. Tanenbaum
• Maarten van Steen

Seminal works

• lynch1996
• tanenbaum2017
• attiya2004

Frequently asked questions

Pourquoi le modèle de synchronisation est-il si important ?

Parce qu'il détermine si les temporisations peuvent être fiables. Dans un modèle synchrone, des délais bornés permettent à un processus de conclure en toute sécurité qu'un pair silencieux a échoué ; dans un modèle asynchrone, un processus lent et un processus en panne sont indiscernables, ce qui est la cause profonde de plusieurs résultats d'impossibilité célèbres.

Qu'est-ce qu'une défaillance byzantine ?

Une défaillance byzantine (arbitraire) est une défaillance dans laquelle un composant défectueux peut se comporter de n'importe quelle manière, y compris en envoyant des messages contradictoires ou malveillants. La tolérer est beaucoup plus coûteux que de tolérer de simples pannes et nécessite des protocoles d'accord spécialisés.