Fondamentaux des Systèmes Distribués

Introduction aux systèmes distribués

Un système distribué, dans sa définition générale, est composé de processus qui n’ont pas de mémoire partagée et sont hétérogènes.

Dans un programme distribué, les processus peuvent être asynchrones, communiquent par passage de messages et peuvent exécuter des instructions internes. Dans un système distribué, les messages peuvent arriver en erreur et être retransmis.

Synchronisation et gestion du temps

• Synchronisation des horloges : Elle peut se baser sur une horloge externe, utiliser l’horloge d’un processus du système comme référence, ou ne pas être nécessaire.
• Horloges physiques : Une horloge comprend une partie oscillante et un compteur ; elle peut dériver en fréquence, notamment à cause de l’altitude.
• Temps UTC : Le temps universel coordonné combine le temps solaire et le temps atomique international. Il peut être ajusté par une leap second (seconde intercalaire).
• NTP : Le protocole Network Time Protocol permet de synchroniser les horloges via un réseau.
• Temps logique : Il permet d’ordonner certaines actions au sein d’un système distribué.

Algorithmes et structures de communication

• Arbre couvrant : Permet de limiter le nombre de messages échangés et de vérifier l’achèvement d’opérations.
• Rondes : Mécanisme utilisable dans un système distribué synchronisé.
• Broadcast : Opération consistant à diffuser un message d’un nœud source vers tous les autres nœuds du réseau.
• Algorithme d’inondation : L’arbre construit a une hauteur au moins égale à l’excentricité de la racine dans le graphe initial.
• Algorithme Echo : Initié par les feuilles de l’arbre, il permet notamment de compter le nombre de nœuds.

Algorithmes de routage et de graphes

• Dijkstra : Utilise l’algorithme Echo pour construire un arbre couvrant en largeur.
• Bellman-Ford : Algorithme asynchrone ayant une moins bonne complexité en messages que Dijkstra.
• Gallager-Humblet-Spira (GHS) : Construit un arbre couvrant minimum, utilise l’algorithme Echo et nécessite log n étapes (n = nombre de nœuds). L’arête bleue y est utilisée et varie selon les fragments.

Communication radio

• Lien radio : Lien partagé sujet aux collisions. Les stations à portée tentent de décoder le signal si la puissance est suffisante.
• TDMA : Technique d’accès multi-canaux.
• Aloha : Technique qui n’écoute pas le médium avant l’envoi.
• CSMA/CA : Approche où les stations écoutent le médium avant d’émettre.