Systèmes distribués · L3 · Section 1/12
Modèles de synchronie et pannes
Progression
#Modèles de synchronie et pannes
Concevoir un système distribué nécessite d'expliciter les hypothèses sur le temps (synchronie) et les types de pannes tolérés. Ces hypothèses déterminent quels algorithmes sont possibles.
#Spectre de synchronie
#Synchrone
Les délais de communication et les vitesses de traitement ont des bornes connues. On peut détecter les pannes par timeout: si un nœud ne répond pas dans le délai, il est considéré en panne.
Avantage: algorithmes simples et déterministes.
Inconvénient: irréaliste en pratique (réseau Internet, GC pauses, congestion).
#Asynchrone
Aucune hypothèse sur les délais. Un message peut prendre un temps arbitrairement long. Résultat célèbre: le consensus est impossible dans un système asynchrone avec même une seule panne crash (FLP impossibility, 1985).
#Partiellement synchrone
Compromis réaliste: le système finit par se stabiliser (GST - Global Stabilization Time) et les bounds deviennent valides. La plupart des algorithmes pratiques (Paxos, Raft, PBFT) supposent ce modèle.
#Types de pannes
#Pannes crash
Le nœud s'arrête et ne revient pas (ou s'il revient, c'est considéré comme un nouveau nœud). C'est le modèle le plus simple et le plus courant.
#Pannes byzantines
Le nœud peut mentir, envoyer des messages contradictoires, ou agir de manière arbitraire (malveillante ou bugguée). Tolérer f pannes byzantines nécessite au moins 3f+1 nœuds.
#Détecteurs de pannes
Un détecteur de pannes est une abstraction qui indique quels nœuds sont suspectés d'être en panne.
#Propriétés des détecteurs
Complétude (completeness): tout nœud réellement crashé finit par être suspecté.
Exactitude (accuracy): les nœuds corrects ne sont pas (ou rarement) suspectés.
En asynchrone pur, on ne peut pas avoir les deux parfaitement. Des détecteurs "eventually perfect" (◇P) suffisent pour le consensus en modèle partiellement synchrone.
#Timeouts et réessais
En pratique, on implémente la détection par timeouts et heartbeats. Les pièges sont nombreux:
Timeout trop court: faux positifs (nœuds corrects marqués comme pannes) → instabilité.
Timeout trop long: détection lente → disponibilité réduite.
Pas de jitter: tous les timeouts expirent en même temps → tempête de messages.
#Retries et idempotence
Face à l'incertitude (le message a-t-il été reçu?), on réessaie. Mais cela nécessite que les opérations soient idempotentes: les appliquer plusieurs fois donne le même résultat qu'une seule fois.
1# Mauvais: non idempotent2def transfer(from_account, to_account, amount):3 from_account.balance -= amount4 to_account.balance += amount5 6# Bon: idempotent avec un identifiant de transaction7def transfer(tx_id, from_account, to_account, amount):8 if tx_id in processed_transactions:9 return # Déjà traité10 from_account.balance -= amount11 to_account.balance += amount12 processed_transactions.add(tx_id)