Plusieurs machines, aucune mémoire commune, aucune horloge commune, juste des messages. Comment se mettre d'accord sur qui commande ? On reprend tout, calmement, avec des animations.
Des processus sans mémoire ni horloge communes s'échangent des messages. Élire un leader, c'est casser la symétrie pour désigner un unique chef, et c'est un calcul par approximation : chacun propose sa valeur et l'affine. Quatre algos selon la topologie : Chang & Roberts (anneau, O(n²) au pire), Franklin (anneau bi-directionnel, O(log n) rounds), Probe-Echo (graphe quelconque), Bully (avec pannes). Ce qui coûte, ce sont les messages ; ce qui compte, c'est l'ordre de réception, pas l'heure.
01 — Le décor
Imagine plusieurs ordinateurs (on les appelle des processus, notés P0, P1, … Pn). Chacun est dans son coin avec sa propre mémoire. Ils ne peuvent faire qu'une chose pour coopérer : s'envoyer des messages.
Le prof commence par un puzzle : LONGER + LARGER = MIDDLE où chaque lettre = un chiffre. Chaque processus gère quelques lettres et propose une valeur. Il ne voit pas le tableau entier : il devine une valeur, l'envoie aux autres, reçoit leurs contraintes, et affine peu à peu. Personne n'a la solution complète, elle émerge des échanges. C'est ça, un calcul distribué par approximation. Garde cette image : élire un leader, ce sera pareil.
Tout le cours repose sur ces suppositions. Si tu les connais, la moitié du travail est faite.
P0…Pn, chacun avec sa mémoire locale et son propre programme. Principe MIMD : chacun exécute son code sur ses données.
Aucune variable globale, aucun tableau commun. La seule façon de partager une info, c'est de l'envoyer par message.
Impossible de dire « il est 14h32 partout ». Chaque processus a son temps à lui. On ne peut donc pas ordonner les événements par l'heure.
Un processus parle à ses voisins (ceux dont il a la référence). Envoi le plus souvent asynchrone : on envoie et on continue, la réception arrive « plus tard ».
First In First Out : sur un même canal, les messages arrivent dans l'ordre où ils ont été envoyés. On ne les double pas.
Par défaut personne ne tombe en panne. On lèvera cette hypothèse à la fin (algo Bully), où le leader peut mourir.
02 — La langue du cours
Tous les algorithmes du cours sont écrits pareil. Si tu sais lire cette notation, tu peux lire n'importe quel algo. C'est une liste de règles de la forme : { si cette condition } → alors fais ça.
Action interne Iₚ : déclenchée par une condition sur les variables locales seulement. Elle peut envoyer des messages.
Action de réception Mₚ : déclenchée par l'arrivée d'un message. La garde peut tester le contenu / le type du message.
Si plusieurs gardes sont vraies en même temps, l'algo en choisit une au hasard. On ne contrôle pas l'ordre. Un algo correct doit marcher quel que soit cet ordre.
// Action INTERNE sur le processus p Iₚ : { garde : condition sur variables locales } x := ... ; // calcul local envoie ⟨M⟩ à voisin ; ... // Action de RÉCEPTION d'un message Mₚ : { un message ⟨j⟩ est arrivé } reçois le message ; si M < j alors ...
Une action est atomique : une fois la garde vraie, tout le corps s'exécute d'un coup, sans être coupé. Et on ne reçoit un message que dans une action de type M, jamais au milieu d'un calcul interne.
03 — Temps & complexité
Comme il n'y a pas d'horloge, deux exécutions qui reçoivent les messages dans le même ordre sont considérées identiques, même si les durées réelles diffèrent. Seul l'ordre de réception compte.
On raisonne en meilleur cas, pire cas, ou cas moyen selon l'algo.
Chaque flèche = un message. Ce qui définit l'exécution, c'est le graphe de ces flèches, pas leur durée.
04 — Le problème central
Au départ tous les processus sont identiques et jouent le même rôle (« démocratie » pair-à-pair). Problème : parfois il faut qu'un seul prenne une décision (le coordinateur, le serveur). Il faut donc désigner un unique chef. C'est casser la symétrie.
Certaines actions ne doivent être faites que par un seul processus : choisir la valeur finale d'une lettre dans le puzzle, jouer le rôle du serveur unique, orchestrer l'application.
À la fin : un et un seul leader, et tous les processus non en panne connaissent son identité. Pas besoin que tous soient candidats, mais tous doivent participer et finir par savoir.
Une élection est un calcul par approximation. Chaque candidat propose sa valeur (son identité) comme approximation du résultat final. À tout instant, un processus ne connaît qu'approximativement qui gagne. Le cœur de chaque algorithme, c'est affiner cette approximation : (0) je propose ma valeur, (1) j'attends une valeur d'un autre, (2) je la combine avec la mienne pour trouver une meilleure approximation et si elle est meilleure je la diffuse, (3) je recommence. La topologie change juste la vitesse de convergence.
Ce sont des identifiants uniques et totalement ordonnés (souvent : l'id du processus, ex. son IP). Convention habituelle : le leader = la plus grande valeur. Mais attention…
On se fiche de qui est élu ! La seule chose qui compte : qu'il y en ait exactement un et que tous soient d'accord. On peut donc élire le plus petit, le premier arrivé, n'importe qui, c'est exactement ce que demande l'exo du serveur.
Les messages tournent dans un seul sens. Le plus grand id fait le tour complet et revient chez lui → il est leader. Exercice 1
À chaque tour on élimine au moins la moitié des candidats. Beaucoup plus rapide : O(log n) tours.
On inonde le graphe puis on renvoie des accusés (echos). Sert aussi à collecter la topologie. Self-training
Le leader peut mourir. Les processus détectent la panne par timeout et se « bagarrent » pour le remplacer.
05 — Algorithme 1 · Exercice 1
Les processus forment un anneau : chacun ne peut envoyer qu'à un seul voisin (le suivant, dans un seul sens). Idée : chaque candidat lance son identité ; une identité n'avance que si elle est plus grande que le processus qu'elle rencontre. Le maximum est le seul à faire le tour complet et à se revoir → il se déclare leader.
// M = max vu jusqu'ici ; mon_numero = mon id Iᵢ : { M = 0 } M := mon_numero ; envoie ⟨M⟩ au suivant Mᵢ : { message ⟨j⟩ arrivé } si M < j alors M := j ; envoie ⟨M⟩ au suivant si j = i alors « je suis le leader »
Quand le leader revoit sa propre valeur (echo), il est sûr que tous l'ont vue. Il envoie un message ⟨End⟩ qui fait le tour : la proclamation est gratuite.
06 — Algorithme 2
Ici chaque processus voit ses deux voisins. À chaque round, un processus encore candidat (« blanc ») compare sa valeur à celle de ses deux voisins. S'il n'est pas le plus grand des trois, il abandonne (« noir »). Au moins la moitié des candidats disparaît à chaque tour → O(log n) rounds.
si blanc : envoie ma valeur à mes 2 voisins ; compare avec les 2 valeurs reçues : si ma valeur < une des deux → noir si ma valeur > les deux → « leader » sinon → round suivant si noir : je relaie seulement les messages (je transmets aux autres voisins)
« Sur un anneau unidirectionnel, quels sont les meilleur et pire cas ? » et « sur un graphe complet, spécialise l'algo (D=1) » → chaque processus attend un message de chacun, calcule le max localement : N·(N-1) messages.
07 — Algorithme 3 · Self-training Exo 1
Sur un graphe quelconque (pas juste un anneau), un initiateur inonde la topologie avec des messages « probe » (sonde). Le premier probe reçu désigne le père (on construit un arbre couvrant). Quand un processus a eu des nouvelles de tous ses voisins, il renvoie un « echo » (accusé) à son père. L'echo peut transporter des données collectées en chemin.
// engage=faux, PRED=père, NI=nb voisins ok Iᵢ : { initiateur } engage := vrai ; NI := 0 ; envoie ⟨info⟩ à tous les voisins Xᵢ : { un message (info ou echo) arrivé de P } si ¬engage alors // 1er probe engage := vrai ; NI := 0 ; PRED := P ; envoie ⟨info⟩ aux {voisins − PRED} NI := NI + 1 ; si NI = |voisins| alors // tous ok si initiateur alors ⟨terminé⟩ sinon envoie ⟨echo⟩ à PRED
Sert à : construire un arbre couvrant, synchroniser (maître/esclaves), faire de la détection de terminaison, et, comme dans l'exo, collecter la topologie. Il généralise Chang&Roberts à n'importe quel graphe.
Chaque candidat lance un probe-echo. Une seule vague se termine : celle du max. Les valeurs plus petites « meurent » car pas propagées. Le survivant est le leader.
08 — Algorithme 4 · avec pannes
On lève enfin l'hypothèse « pas de panne » : les processus peuvent tomber (y compris le leader). On suppose une topologie totalement connectée et que chacun connaît l'identité de tous. Grâce à un timeout, on détecte qu'un processus ne répond plus. « Bully » = la brute : le plus grand id vivant s'impose.
Si un processus crashé redémarre avec le même id le plus grand, il relance l'algo et s'auto-proclame leader, même si une élection était en cours. On peut alors se retrouver 2 leaders temporairement et une vision incohérente. C'est l'objet de l'exo p1..p4 avec p4 en panne puis p3 qui tombe.
09 — Aide guidée
Ouvre chaque exercice pour la correction pas à pas. fait = déjà rendu (self-training, corrigé A+). Les autres sont la « List of annexed exercises ».
Comparer la version du cours et celle de Krakowiak, expliquer la différence de résultat.
L'énoncé donne deux écritures du même algo d'élection sur anneau unidirectionnel. La question : quelle différence quand tous se réveillent spontanément vs quand seuls certains se réveillent ?
Les deux élisent bien le processus de plus grand id. La différence tient au cas où un nœud reçoit une valeur plus petite que la sienne alors qu'il ne s'est pas encore réveillé :
Quand tous se réveillent spontanément, les deux versions élisent le même : le max global. Quand seuls certains se réveillent, la Version 2 (parce qu'un message réveille un dormeur et l'oblige à propager sa propre valeur) garantit toujours le max parmi les participants effectifs et gère proprement les réveils tardifs ; la Version 1 telle qu'écrite suppose un réveil général et n'a pas ce mécanisme de « relance par le bas ».
Va voir l'animation Chang & Roberts pour visualiser l'absorption des petites valeurs et le tour complet du max.
Décrire une exécution possible sur le graphe P0–P4 (messages, traitements, valeurs successives).
On calcule de façon distribuée les plus courts chemins (tables de routage de plus faible coût). C'est l'application directe du « calcul par approximation » : chaque nœud a une estimation de sa distance à une destination, et l'affine en recevant les estimations de ses voisins (il garde le min). C'est du Bellman-Ford distribué (distance-vector).
« Quels messages, quels traitements, quelles valeurs successives ». → Chaque nœud envoie son estimation à ses voisins ; à la réception il fait min(actuel, coût_arête + estimation_reçue) ; s'il s'améliore, il rediffuse. Les valeurs de P4 illustrent bien l'affinage progressif (5 puis 4). Pas besoin de gérer la détection de terminaison (dit l'énoncé).
Self-training. A initie, veut récupérer tous les triplets (source, dest, perf) sans doublon.
Réseau 6 nœuds A–F, liens bidirectionnels, chaque nœud connaît ses voisins + la perf du lien. But : A collecte tous les triplets. L'echo doit transporter les données agrégées.
À la fin, A détient l'ensemble agrégé, sans doublon, de tous les triplets :
(A,B,1)(A,C,2) (B,A,2)(B,C,2)(B,D,4) (C,A,3)(C,B,3)(C,D,3) (D,B,1)(D,C,1)(D,E,3)(D,F,2) (E,D,1) (F,D,2)
On reprend l'algo Echo, mais l'echo transporte un champ set_triples. Chaque nœud, quand il renvoie son echo, y met ses triplets locaux ∪ tout ce qu'il a reçu des echos de ses fils (union → pas de doublon).
// mes_triplets = triplets locaux connus au départ // accu = ensemble accumulé (init = mes_triplets) Cᵢ : { initiateur = vrai } engage:=vrai; NI:=0; accu:=mes_triplets; envoie ⟨probe⟩ à tous les voisins REᵢ : { ⟨probe⟩ arrivé de P } si ¬engage alors engage:=vrai; PRED:=P; accu:=mes_triplets; NI:=0; envoie ⟨probe⟩ aux {voisins − P} NI:=NI+1; si NI=|voisins| alors fin() REᵢ : { ⟨echo, set_triples⟩ arrivé } accu := accu ∪ set_triples ; // union = sans doublon NI := NI + 1 ; si NI=|voisins| alors fin() fin() : si initiateur alors RÉSULTAT := accu sinon envoie ⟨echo, accu⟩ à PRED
Regarde l'animation Probe-Echo : elle joue exactement ce graphe. Résumé :
Non. Seules les arêtes de l'arbre couvrant portent 1 probe (aller) + 1 echo (retour). Les arêtes hors arbre (ex. B–C, C–D) sont traversées par des probes dans les deux sens mais aucun echo : quand un nœud déjà engage reçoit un probe, il ne le prend pas comme père, il compte juste le voisin. Donc : arêtes d'arbre = 1 probe + 1 echo ; arêtes hors-arbre = 2 probes, 0 echo.
Self-training, corrigé A+. Un serveur infaillible héberge le service d'élection.
Topologie étoile : un serveur central (qui ne tombe jamais) au milieu, des clients autour. Le serveur ne sait pas combien de clients existent. On veut élire un leader parmi les clients candidats (pas forcément le plus grand id) et que tous soient d'accord. Un oracle détecte la panne du leader.
L'oracle pingue régulièrement le leader. Pas de réponse → il envoie ⟨start_election⟩ au serveur et aux clients. Tout le monde remet leader_id := null ; les clients redemandent alors au serveur (candidat, ou juste savoir qui est le nouveau leader).
// SERVEUR (ne tombe jamais) I : { reçoit ⟨start_election⟩ de l'oracle } leader_id := null RBC : { reçoit ⟨be_candidate⟩ de p } si leader_id = null alors leader_id := p // 1er arrivé élu envoie ⟨set_leader, leader_id⟩ à p RSL : { ⟨search_leader⟩ de p, leader_id≠null } envoie ⟨set_leader, leader_id⟩ à p
// CLIENT (leader_id = null au départ) I : { leader = null } si veut_être_candidat alors envoie ⟨be_candidate⟩ au serveur sinon envoie ⟨search_leader⟩ au serveur RSE : { reçoit ⟨start_election⟩ de l'oracle } leader_id := null si veut_être_candidat alors ⟨be_candidate⟩→serveur sinon ⟨search_leader⟩→serveur RSL : { reçoit ⟨set_leader, id⟩ du serveur } leader_id := id
Astuce clé : c'est premier arrivé, premier élu (first-come-first-elected). Le serveur répond toujours set_leader, donc même une requête arrivant pendant la proclamation est traitée correctement (on renvoie le leader déjà fixé).
Étoile + serveur central infaillible → pas vraiment de meilleur/pire cas, un seul cas. Temps parallèle = O(1) (un aller-retour client↔serveur). Messages : avec N clients tous candidats → N ⟨be_candidate⟩ + N ⟨set_leader⟩ = 2N = O(N).
Très simple (toute la logique côté serveur), très rapide (1 round), coût faible, accord garanti car le serveur est la source unique de vérité.
Le serveur est un point de défaillance unique et un goulot d'étranglement (peut être submergé) → passe mal à l'échelle. Et on dépend d'un oracle externe pour détecter les pannes → moins autonome.
Ce corrigé correspond à ta copie notée A+. Sers-t'en comme modèle de rédaction : énoncé des hypothèses, algos en actions gardées, complexité chiffrée, discussion honnête des limites.
10 — Entraînement
Teste-toi avant le QCM de la semaine. Pool de questions tirées au hasard, correction et explication immédiates. Ton meilleur score est gardé dans ton navigateur.
Pool de 36 questions. Tire un échantillon au hasard, correction immédiate et explication à chaque réponse.
Lis la question, réponds dans ta tête, puis retourne la carte.