Dans un système distribué, il n'y a pas d'horloge commune, pas de mémoire partagée, et une partie du système peut tomber sans que le reste le sache.
⏱️ Durée : environ 100 minutes · 🎓 Niveau : avancé · 🏅 Badge : Explorateur du distribué
🎬 L'histoire
HashBox ouvre un second centre de données à Montréal pour se rapprocher de ses utilisateurs canadiens. Deux jours plus tard, un formateur de Lyon et une formatrice de Montréal modifient le même cours à quelques secondes d'écart. Résultat : la modification de l'un écrase celle de l'autre, et le journal des événements montre l'inscription de Léo avant la création du cours, ce qui est impossible.
« Tu viens de rencontrer les trois difficultés fondamentales, dit Sam. Les machines ne s'accordent pas sur l'heure. Les messages se perdent ou arrivent en retard. Et quand une réponse ne vient pas, tu ne sais pas si l'autre est tombé, lent, ou si c'est le réseau. Il faut raisonner autrement. »
Tu apprends les propriétés d'un système distribué, ses modèles de pannes, pourquoi aucune horloge ne suffit, et comment les horloges logiques de Lamport et les horloges vectorielles ordonnent les événements.
🎯 Ta mission
À la fin, je serai capable de :
- énumérer les difficultés propres au distribué (pannes partielles, latence, absence d'horloge globale)
- décrire les modèles de pannes (arrêt, omission, byzantine) et de synchronie
- expliquer le problème des deux généraux et ses conséquences
- implémenter des horloges de Lamport et vectorielles
- décider si deux événements sont causalement liés ou concurrents
🧩 Défi d'échauffement (5 XP)
Deux amis décident de se retrouver au café, chacun dans une ville différente, uniquement par SMS qui peuvent se perdre. Ada envoie « on se retrouve à 18 h ? », Bob répond « ok ». Ada est-elle sûre que Bob a reçu son message ? Bob est-il sûr qu'Ada a reçu son « ok » ? Combien de SMS faut-il pour que les deux soient certains ? Existe-t-il un nombre qui fonctionne ?
💡 Le concept
Qu'est-ce qu'un système distribué ?
Un ensemble de machines indépendantes qui coopèrent en échangeant des messages pour offrir un service unique. Raisons de le faire : capacité (partager la charge), disponibilité (survivre aux pannes), latence (se rapprocher des utilisateurs), organisation (équipes indépendantes).
Le prix : un ensemble de difficultés qui n'existent pas sur une seule machine.
Les huit erreurs classiques (« fallacies »)
Les développeurs croient souvent que :
- le réseau est fiable ;
- la latence est nulle ;
- la bande passante est infinie ;
- le réseau est sûr ;
- la topologie ne change pas ;
- il y a un seul administrateur ;
- le coût de transport est nul ;
- le réseau est homogène.
Tout est faux. Un système distribué correct commence par refuser ces hypothèses.
Trois difficultés fondamentales
| Difficulté | Conséquence |
|---|---|
| Pannes partielles | une partie du système tombe pendant que le reste fonctionne ; on ne sait pas toujours laquelle |
| Asynchronie | les messages ont un délai variable, non borné ; on ne peut pas distinguer « lent » de « mort » |
| Pas d'horloge ni de mémoire communes | pas d'ordre global évident des événements |
La question « le serveur est-il tombé ? » n'a pas de réponse sûre : un délai dépassé signifie « je n'ai pas eu de réponse », pas « il est mort ».
Les modèles de pannes
| Modèle | Comportement du nœud défaillant |
|---|---|
| Arrêt sur panne (crash-stop) | s'arrête définitivement |
| Reprise après panne (crash-recovery) | s'arrête puis redémarre (peut avoir perdu sa mémoire) |
| Omission | perd des messages (envoi ou réception) |
| Partition réseau | des groupes de nœuds ne peuvent plus communiquer entre eux |
| Byzantine | comportement arbitraire, y compris malveillant |
Plus le modèle de panne est sévère, plus les algorithmes sont coûteux. La plupart des systèmes d'entreprise supposent crash-recovery + partitions.
Les modèles de synchronie
| Modèle | Hypothèse |
|---|---|
| Synchrone | délais bornés connus, horloges précises |
| Asynchrone | aucune borne sur les délais |
| Partiellement synchrone | des bornes existent mais sont inconnues, ou valables « finalement » |
Le monde réel est partiellement synchrone : on conçoit des algorithmes sûrs même en asynchrone (jamais de mauvais résultat), et vivants quand le réseau se comporte bien.
Le problème des deux généraux
Deux armées doivent attaquer simultanément pour gagner, en communiquant par messagers qui peuvent être interceptés. Aucun protocole fini ne garantit l'accord : celui qui envoie le dernier message ne sait jamais s'il est arrivé. On peut réduire la probabilité de désaccord, jamais l'annuler : c'est l'impossibilité fondamentale derrière les confirmations, les délais, les transactions distribuées.
Pas d'horloge commune
Les horloges physiques dérivent (millisecondes par jour) et ne sont synchronisées (NTP) qu'à quelques millisecondes près, parfois bien plus. Trier des événements de machines différentes par heure physique donne des ordres faux.
La relation « s'est produit avant » (Lamport)
On note a → b (a précède causalement b) si :
aetbsont sur le même processus etavient avantb;aest l'envoi d'un message etbsa réception ;- transitivité :
a → cetc → b⟹a → b.
Si ni a → b ni b → a, les événements sont concurrents (a ‖ b) : aucun ne peut avoir influencé l'autre.
Horloges de Lamport (logiques)
Chaque processus tient un compteur L.
- événement local ou envoi :
L ← L + 1(le message porteL) ; - réception d'un message portant
Lm:L ← max(L, Lm) + 1.
Propriété : a → b ⟹ L(a) < L(b). Mais la réciproque est fausse : L(a) < L(b) ne prouve pas que a → b (ils peuvent être concurrents).
Horloges vectorielles
Chaque processus tient un vecteur de compteurs (un par processus).
- événement local ou envoi :
V[i] += 1; - réception de
Vm:V ← max terme à terme(V, Vm)puisV[i] += 1.
Comparaison :
Va ≤ Vbpartout etVa ≠ Vb⟹a → b;- ni l'un ni l'autre ⟹ concurrents.
Les horloges vectorielles caractérisent exactement la causalité (iff). Elles servent à détecter les conflits d'écriture concurrente (Dynamo, Riak).
Idées-forces
- Concevoir pour la panne : timeouts, reprises, idempotence (mission 4).
- Ne jamais supposer un ordre global : utiliser la causalité, un journal ordonné, ou un consensus (mission 7).
- Mesurer : latence, taux d'erreur, retries.
🧠 Astuce : devant un incident distribué, demande-toi toujours : que sait réellement chaque nœud à cet instant ? Souvent, personne ne connaît l'état global.
🔍 Exemple pas à pas
Problème : (1) simuler le problème des deux généraux, (2) implémenter les horloges de Lamport et vectorielles sur un scénario à trois processus, (3) montrer qu'une horloge physique décalée donne un ordre faux alors que l'horloge vectorielle capture la causalité.
import random
# ---------------- 1. les deux généraux ----------------
def deux_generaux(p_perte, k, essais=100000, graine=1):
# protocole à k messages alternés A→B, B→A, ... ; le dernier expéditeur attaque sans attendre de confirmation
rng = random.Random(graine)
les_deux = desaccord = personne = 0
for _ in range(essais):
livres = 0
for i in range(k):
if rng.random() < p_perte: break # ce message est perdu : la chaîne s'arrête
livres += 1
if livres == k: les_deux += 1 # tous reçus : les deux attaquent
elif livres == k - 1: desaccord += 1 # seul le dernier est perdu : l'expéditeur attaque seul
else: personne += 1 # une perte plus tôt : personne n'attaque (cohérent)
return les_deux / essais, desaccord / essais, personne / essais
p = 0.2
print("k messages | les deux attaquent | DÉSACCORD | personne n'attaque")
for k in (1, 2, 4, 8, 16):
a, d, n = deux_generaux(p, k)
theorique_d = p * ( - p) ** (k - )
()
(d - theorique_d) <
deux_generaux(p, )[] >
deux_generaux(p, )[] < deux_generaux(p, )[]
:
():
.nom, .i = nom, noms.index(nom)
.lamport, .vecteur, .journal = , [] * (noms), []
():
.lamport += ; .vecteur[.i] +=
.journal.append((description, .lamport, (.vecteur), heure_physique));
():
.evenement(description, heure_physique)
{: .lamport, : (.vecteur)}
():
.lamport = (.lamport, message[])
.vecteur = [(a, b) a, b (.vecteur, message[])]
.evenement(description, heure_physique)
():
va == vb:
(a <= b a, b (va, vb)):
(a >= b a, b (va, vb)):
NOMS = [, , ]
lyon, mtl, paris = (Processus(n, NOMS) n NOMS)
m1 = lyon.envoyer(, )
mtl.recevoir(m1, , )
m2 = mtl.envoyer(, )
paris.evenement(, )
paris.recevoir(m2, , )
evts = {d: (l, v, h) p (lyon, mtl, paris) d, l, v, h p.journal}
creation, inscription, prix = evts[], evts[], evts[]
(, , creation[], , inscription[], )
inscription[] < creation[]
compare(creation[], inscription[]) ==
creation[] < inscription[]
compare(prix[], inscription[]) ==
()
prix[] < inscription[] compare(prix[], inscription[]) ==
d, l, v, h ((e p (lyon, mtl, paris) e p.journal), key= e: e[]):
()
Lecture :
- Deux généraux : quel que soit
k, le désaccord n'est jamais nul : il vautp(1 − p)^(k−1). Exiger plus de confirmations réduit le désaccord mais réduit aussi la probabilité d'attaquer. On ne gagne jamais la certitude : on choisit un compromis entre sûreté et activité. - Horloge physique : Montréal a huit secondes de retard ; trier par heure physique place l'inscription de Léo avant la création du cours. C'est faux.
- Lamport respecte la causalité (
création → inscriptionimpliqueL(création) < L(inscription)), mais il ordonne aussi des événements concurrents (prixetinscription) sans le dire. - Vecteurs : ils distinguent « avant » de « concurrents » : le changement de prix de Paris est concurrent à l'inscription. C'est exactement l'information nécessaire pour détecter un conflit.
✍️ À toi, avec aide (10 XP)
Trois processus A, B, C ont produit ces événements avec leurs horloges vectorielles [A, B, C] :
| Événement | Vecteur |
|---|---|
| e1 (A) | [1, 0, 0] |
| e2 (A, envoi à B) | [2, 0, 0] |
| e3 (B, réception de e2) | [2, 1, 0] |
| e4 (C) | [0, 0, 1] |
| e5 (B, envoi à C) | [2, 2, 0] |
| e6 (C, réception de e5) | [2, 2, 2] |
Écris relation(x, y) et affiche la relation pour toutes les paires. Combien de paires sont concurrentes ? Lesquelles ?
💡 Indice 1
Utilise la fonction compare de l'exemple.
💡 Indice 2
Utilise itertools.combinations pour les paires.
💡 Indice 3
e4 n'a aucune relation causale avec e1, e2, e3, e5 (sauf par e6).
✅ Réponse
from itertools import combinations
V = {"e1": (1, 0, 0), "e2": (2, 0, 0), "e3": (2, 1, 0), "e4": (0, 0, 1), "e5": (2, 2, 0), "e6": (2, 2, 2)}
def compare(va, vb):
if va == vb: return "égaux"
if all(a <= b for a, b in zip(va, vb)): return "avant"
if all(a >= b for a, b in zip(va, vb)): return "après"
return "concurrents"
concurrentes = [(x, y) for x, y in combinations(V, 2) compare(V[x], V[y]) == ]
x, y combinations(V, ):
()
(, concurrentes)
concurrentes == [(, ), (, ), (, ), (, )]
🚀 À toi, en solo (20 XP)
Détecteur de conflits avec versions vectorielles. Implémente un petit magasin clé-valeur répliqué sur 3 nœuds où chaque valeur porte un vecteur de version (comme Dynamo) :
ecrire(noeud, cle, valeur, contexte): l'écriture incrémente le compteur du nœud dans le vecteur du contexte lu ;- chaque nœud garde, pour une clé, l'ensemble des versions non dominées (frères) ;
fusionner(noeud_a, noeud_b): échange de versions (anti-entropie) : une version dominée (strictement avant) est supprimée, deux versions concurrentes sont toutes deux conservées ;lire(noeud, cle)renvoie les frères et un contexte (le maximum des vecteurs) ;- scénario : deux clients lisent la même version puis écrivent chacun de leur côté (sur deux nœuds différents) pendant une partition ; après fusion, la lecture renvoie deux frères ; un client résout le conflit en écrivant avec le contexte fusionné : un seul reste.
✅ Pistes de correction
def domine(va, vb): # va ≤ vb partout et différent
return all(a <= b for a, b in zip(va, vb)) and va != vb
class Noeud:
def __init__(self, i, n=3):
self.i, self.n, self.donnees = i, n, {} # cle -> liste de (valeur, vecteur)
def ecrire(self, cle, valeur, contexte=None):
v = list(contexte or (0,) * self.n); v[self.i] += 1; v = tuple(v)
versions = [(val, vec) for val, vec in self.donnees.get(cle, []) if not domine(vec, v)]
self.donnees[cle] = versions + [(valeur, v)]
return v
def lire(self, cle):
versions = self.donnees.get(cle, [])
contexte = tuple((c) c (*[v _, v versions])) versions (,) * .n
(val val, _ versions), contexte
():
cle (a.donnees) | (b.donnees):
toutes = ({(val, vec) val, vec a.donnees.get(cle, []) + b.donnees.get(cle, [])})
gardees = [(val, vec) val, vec toutes (domine(vec, autre) _, autre toutes)]
a.donnees[cle] = gardees; b.donnees[cle] = (gardees)
n0, n1, n2 = Noeud(), Noeud(), Noeud()
n0.ecrire(, ); fusionner(n0, n1); fusionner(n0, n2)
valeur, contexte = n1.lire(); valeur == []
n0.ecrire(, , contexte)
n2.ecrire(, , contexte)
fusionner(n0, n2)
frères, ctx = n0.lire()
(, frères)
frères == [, ]
n1_apres = n0.ecrire(, , ctx)
frères, _ = n0.lire()
(, frères, n1_apres)
frères == []
⚠️ Pièges classiques
| Piège | Pourquoi c'est un problème | Comment l'éviter |
|---|---|---|
| Trier des événements par heure physique entre machines | Ordre faux, effets de causalité inversés | Horloges logiques/vectorielles, ou journal ordonné par un consensus |
| Supposer qu'un délai dépassé signifie une panne | On ne sait pas si c'est lent, mort ou le réseau | Raisonner en incertitude : retries idempotents, détecteurs de pannes |
| Appliquer « le dernier gagne » sans réfléchir | Écriture perdue silencieusement | Détecter les conflits (vecteurs) ou utiliser des types fusionnables |
| Croire que le réseau est fiable | Pannes en production | Concevoir pour la perte, la duplication, le retard, le réordonnancement |
🐉 Mini-boss (40 XP)
Journal causal de HashBox. Trois services (inscriptions, paiements, notifications) produisent des événements horodatés avec leurs horloges physiques (décalées de plusieurs secondes) et échangent des messages. Génère un scénario de 30 événements (graine fixée) avec des envois/réceptions.
- équipe chaque processus d'horloges de Lamport et vectorielles ;
- écris
ordre_causal(evenements)qui produit un ordre total compatible avec la causalité (tri topologique) ; - montre que le tri par heure physique viole au moins une relation de causalité, mais pas celui de ton algorithme ;
- écris
paires_concurrentes(evenements)et liste celles qui touchent la même ressource (conflits potentiels) ; - vérifie par un test aléatoire (100 graines) que ton ordre respecte
a → b ⟹ a avant bet que Lamport respecte la même propriété mais que la réciproque est fausse dans au moins un cas ; - écris 5 lignes sur ce que ton système ne peut pas savoir (ex. : l'ordre « réel » des événements concurrents).
✅ Pistes de correction
Un bon travail : classes Processus avec vecteur et Lamport, génération aléatoire d'actions (local, envoi, réception d'un message en attente), tri topologique (par exemple tri par somme du vecteur puis départage par nom — valide car a → b implique somme(Va) < somme(Vb)), détection des violations du tri physique, test aléatoire sur 100 graines, liste des conflits (paires concurrentes sur la même clé). Le point final : l'ordre entre événements concurrents est arbitraire et non observable — toute application doit être correcte quel que soit cet ordre.
⚡ Quiz éclair (15 XP si 4/5 ou plus)
1. Dans un système distribué asynchrone, un délai dépassé signifie :
- A. qu'on n'a pas reçu de réponse, sans savoir si l'autre est lent, mort ou injoignable
- B. que l'autre machine est tombée
- C. que le message est arrivé
2. a → b (a s'est produit avant b) signifie :
- A. que l'horloge physique de a est plus petite
- B. que a peut avoir influencé causalement b
- C. que a et b sont sur la même machine
3. Deux événements aux horloges vectorielles [2,0] et [0,1] sont :
- A. l'un avant l'autre
- B. identiques
- C. concurrents
4. 🔁 Révision HEF-130, mission 01 : D'après Amdahl, si 90 % d'un programme est parallélisable, l'accélération maximale est :
- A. environ ×10
- B. infinie
- C. ×90
5. 🔁 Révision HEF-130, mission 09 : Une file d'attente sans limite sous surcharge conduit à :
- A. une latence stable
- B. une latence qui explose et une mémoire saturée
- C. un gain de débit
✅ Réponses
- A.
- B.
- C.
- A.
- B.
🪞 Je réfléchis (10 XP)
- Quelle décision de ton système suppose aujourd'hui qu'une autre machine a « forcément » reçu ton message ?
- Où ton système trie-t-il des événements par une heure physique issue de plusieurs machines ?
🎒 À retenir
- Pannes partielles, asynchronie, pas d'horloge commune.
- Modèles de pannes : arrêt, reprise, omission, partition, byzantine.
- Deux généraux : l'accord certain est impossible, on arbitre sûreté et activité.
- Lamport : a → b ⟹ L(a) < L(b), pas la réciproque.
- Vecteurs : caractérisent la causalité et détectent la concurrence.
flowchart LR
T(["Modèles et contraintes distribuées"])
T --> R1["1. Pannes partielles, asynchronie, pas d'horloge commune."]
T --> R2["2. Modèles de pannes : arrêt, reprise, omission, partition, byzantine."]
T --> R3["3. Deux généraux : l'accord certain est impossible, on arbitre sûreté et…"]
T --> R4["4. Lamport : a → b ⟹ La Lb, pas la réciproque."]
T --> R5["5. Vecteurs : caractérisent la causalité et détectent la concurrence."]
Description du schéma : la mission au centre, reliée aux cinq idées à retenir.
🏅 Récompenses
Total possible : 100 XP · 🏅 Badge Explorateur du distribué
Mission 02 — RPC et communication →
HEF-140 — Systèmes distribués

