Cours de Systèmes Répartis: Partie 1: Algorithmique Répartie

Promotion BADS AU 2019/20

Plan

 Introduction  Bases de l’algorithmique répartie

1. Etat dans un système réparti, ordre, temps, 2. Observation cohérente 3. Algorithmique répartie

Définition d’un système réparti

Ensemble composé d’éléments reliés par les un système de communication éléments ont des fonctions de traitement (processeurs), de stockage (mémoire), de relation avec le monde extérieur (capteurs, actionneurs)

;

Propriétés des systèmes répartis

 Fonctionner (au moins de façon dégradée) même en cas de

défaillance de certains de ses éléments

 Résister à des perturbations du système de communication (perte de messages, déconnexion temporaire, performances dégradées)

 Résister à des attaques contre sa sécurité (tentatives de violation de la confidentialité et de l’intégrité, usage indu de ressources, déni de service)

 S’adapter pour faire face aux changements de conditions

d’utilisation et d’environnement

 Rester performant lorsque sa taille augmente (nombre

d’éléments, nombre d’utilisateurs, étendue géographique)

Difficultés dans les systèmes répartis

 Propriété d’asynchronisme du système de communication (pas de borne

supérieure stricte pour le temps de transmission d’un message) ◦ Conséquence : difficulté pour détecter les défaillances

 Dynamisme (la composition du système change en permanence)

◦ Conséquences : difficulté pour définir un état global ◦ Difficulté pour administrer le système

 Taille complexe et développée (nombre de composants, d’utilisateurs,

dispersion géographique) ◦ Conséquence : la capacité de croissance est une propriété importante,

mais difficile à réaliser

 En dépit de ces difficultés, des systèmes répartis existent tels

que: ◦ le DNS (Domain Name System) ◦ le World Wide Web ◦ divers services sur l’Internet

(service de base) (infrastructure) (applications)

Problèmes fondamentaux

 Comment déterminer des propriétés globales à partir

d’observations locales ?

 Comment coordonner des opérations en

l’absence

d’horloge commune ?

 Comment définir, et maintenir, la cohérence d’informations

réparties ?

 Comment garder un système en fonctionnement malgré

des défaillances partielles

Solutions fondamentales

Il faut définir des modèles

 Un modèle est une représentation du monde réel

 Un modèle représente des éléments réels par des éléments abstraits

 Un même système réel peut être représenté par des modèles

différents

 Tout modèle a des limites

Il faut utiliser les modèles

 Pour observer et comprendre le comportement du système réel

 Pour prédire le comportement du système réel dans certaines

circonstances

 Pour aider à commander le système réel (lui imposer un

comportement particulier)

Bases de l’algorithmique répartie

1. Ordre, temps, état dans un système

réparti

2. Observation cohérente 3. Algorithmes répartis de base

Ordre, temps, état dans un système réparti

On veut être capable de raisonner sur un système ou une

application ◦ Définir des prédicats, ce qui implique d’accéder à un état ◦ Coordonner des activités, ce qui implique de définir un ordre

Univers réparti est différent:

◦ Pas de mémoire commune (support habituel de l’état) ◦ Pas d’horloge commune (qui définit le séquencement des

événements)

◦ Asynchronisme des communications

 Pas de borne supérieure sur le temps de transit d’un message

◦ Asynchronisme des traitements

 Pas de bornes sur le rapport relatif des vitesses d’exécution sur deux

sites

 Conséquence de la variabilité de la charge et de l’absence (en général)

de garanties sur l’allocation des ressources

Sûreté et vivacité

 On est souvent amené à spécifier et à vérifier

des propriétés d’un système dynamique (évoluant dans le temps)

 Ces propriétés ont deux valeurs:

◦ Sûreté (safety) : un événement indésirable

n’arrivera jamais  Exemples : violation de l’exclusion mutuelle incohérence

dans les données

◦ Vivacité (liveness) : un événement désirable

finira par arriver  Exemples : un message sera délivré à son destinataire  une ressource demandée sera rendue disponible  un algorithme se termine

Le modèle asynchrone (fiable)

 Le but est de modéliser certains

aspects du monde réel ◦ Asynchronisme des communications et des

traitements

 C’est le modèle le plus “faible”

◦ Les contraintes sont les plus fortes  les

résultats sont les plus généraux  Bornes sur les coûts  Résultats d’impossibilité

◦ " Le modèle peut être renforcé (en levant

certaines contraintes  Exemple : borne supérieure sur le traitement

et/ou la durée de transmission

Le modèle asynchrone

 Les processus (sur différents sites) ne communiquent que par messages

 Trois types d’événements

◦ Local (changement de l’état d’un processus) ◦ Lié à la communication  Émission d’un message  Réception d’un message

Pas de bornes sur : •la durée de transmission d’un message •le rapport des vitesses d’exécution des processus

Réception / Délivrance

 On suppose disponible un système de communication permettant d’envoyer des messages entre processus

 Propriétés :

1. Un message finit par arriver à destination, mais son temps de transmission n’est pas borné!; on modélise ainsi une panne (détectée) suivie d’une ou plusieurs réémission(s) 2. Un message arrive intact (non modifié) ; on suppose que des mécanismes de détection / correction d’erreur sont utilisés

3. Selon le cas, on fera ou non l’hypothèse que le canal est

FIFO entre deux processus

Réception / Délivrance

 Bien distinguer la réception d’un message de sa délivrance à son destinataire

Événements, historique, synchronisation

 L’exécution d’un processus est une suite

d’événements (local, émission, réception) appelée historique (ou trace) du processus ◦ pour p1 : e11, e12, e13, …, e1k, …

 Cette suite est ordonnée par l’horloge locale du

processus p1

Que veut dire “synchroniser deux processus ?”  Imposer un ordre entre des événements

appartenant à ces deux processus ◦ Exemple : l’exclusion mutuelle ◦ fin(C2) précède deb(C1) ou fin(C1) précède deb(C2)

Relation de précédence

 Le problème :

◦ 1) Définir une relation globale de précédence (donner un

sens à l’opérateur « précède »)

◦ 2) Définir un ordre entre deux événements sur la seule

base d’informations locales

 Solution : utiliser le principe de causalité : la cause

précède l’effet. Une relation de précédence est dite causale si elle est compatible avec ce principe. Application ici : ◦ Sur un processus : un événement local ne peut agir localement que sur les événements postérieurs

◦ Entre deux processus : l’envoi d’un message précède sa

réception

◦ Composition : la relation de causalité est transitive

La causalité

 Définition [Lamport 78] :

◦ e précède causalement e' ( e  e') si :

La causalité est potentielle

 La relation de précédence causale ! définit en fait une causalité potentielle (par négation)  Si e e', on peut simplement dire qu’on ne

viole pas le principe de causalité en disant que e est la cause de e'. On peut donc dire que e est une cause potentielle de e', mais pas que e est effectivement une cause de e' (il faudrait pour cela analyser la sémantique de l’application)  Certitude que e' ne peut pas être la cause de e

(le futur n’agit pas sur le passé)

Dépendance et indépendance causale

 Définition : passé (ou historique) d’un événement e

◦ hist(e) = l’ensemble des e' tels que e'  e  {e}

 Seul le passé strict de e peut influencer e

◦ si e'  e, alors e' peut influencer e ◦ si ¬ (e‘  e), alors il est certain que e' ne peut pas

influencer e

 Si ¬ (e  e') et ¬ (e'  e), on note e || e' et on dit que e et e' sont causalement indépendants (aucun des deux n’appartient au passé de l’autre, aucun des deux ne peut influencer l’autre)

Problème de datation

 Problème : construire un système de datation des événements compatible avec la causalité

 Approche : introduire un processus

“observateur” p0 qui est informé, par message, de tout événement du système

 La suite des événements enregistrée par p0 est une observation globale du système

Problème de datation

Problème de datation: Validité des observations

 Une observation du système est un

ordonnancement particulier des événements du système.

 Une observation est dite valide si pour tout

couple d’événements (e, e') tels que

e  e', O(e) précède O(e'). Sinon, elle est dite invalide (elle

viole la causalité)

Problème de datation: Validité des observations

 Canal non FIFO. L’observation viole la

causalité : les événements sont observés dans l’ordre inverse de leur occurrence

Problème de datation: Validité des observations

 La causalité est encore violée :

◦ e1

1  e2

l’ordre inverse.

2 , mais ces événements sont observés dans

 Ce phénomène est indépendant de la propriété

FIFO

Observation valide

 Temporairement, lever l’hypothèse

d’asynchronisme

 temps de transmission borné = & et supposer qu’on dispose d’une horloge HR donnant le temps réel.

 Chaque événement transmis à l’observateur est

estampillé par HR

 une observation de e est le couple (e, HR(e))

Observation valide

 Au temps t, on délivre tous les messages

ayant des estampilles < t – & dans l’ordre des estampilles.

Caractérisation des observations valides

Condition de validité:  " Dans un système où les observations sont

ordonnées par des estampilles H, une condition suffisante de validité est :

 e e'  H(e) < H(e') : condition de validité faible

de l’horloge (implication dans un seul sens)

 Cette condition est trivialement satisfaite par HR

Etat Global?

 Pas de HR  Temps de propagation des messages n’est pas

borné

 Objectif: construire un système d’horloges

assurant une observation valide, en respectant la condition de validité faible

 L’absence de borne & aura une conséquence

sur la complétude, non sur la validité

Horloges logiques (Lamport)

Principe:

 à chaque site i, un compteur HLi à valeurs

entières

 Un événement e se produisant sur le site i est daté par la valeur courante de HLi , soit HLi(e)

 Un message m émis à partir du site i porte une estampille égale à sa date d’émission

Algorithme de Lamport

 Initialisation :

◦ HLi = 0

 Événement local et d’envoi :

◦ HLi = HLi + 1

 Envoi d’un message m :

◦ on envoie (m, Em), avec Em = HLi (après incrémentation)

 Réception d’un message (m, Em) :

◦ HLi = max (HLi, Em) + 1

Exemple

 HL satisfait la condition de validité faible :

◦ e e'  H(e) < H(e')

 Mais H(e) < H(e')  ¬ (e e'). ◦ Donc ou bien e'  e, ou bien e' || e

Ordre strict et total

 L’ordre n’est pas strict. Deux événements peuvent avoir la même estampille: ils sont alors causalement indépendants. Si on veut un ordre strict, il faut ajouter un critère (en général on prend le numéro du processus)

◦ Si e  pi, e‘ pj, alors ◦ (HL(e), i) < (HL(e'), j) ssi HL(e) < HL(e') ou (HL(e)

= HL(e') et i<j)

Non-détection des événements manquants

 p1 reçoit des messages des autres processus. On

souhaite qu’ils lui soient délivrés dans l’ordre de leurs estampilles.

 Délivrance de m2 (3) et réception de m4 (8). Peut-on le

délivrer ?

Non-détection des événements manquants

 Les trois situations sont indistinguables avec

les HL

 Plus généralement, si HL(e) < HL(e'), existe-t-il

e" tel que e  e"  e' ?

 Question insoluble. Il s’agit d’une propriété de vivacité (un événement va-t-il arriver ?) Risque d’un événement ne soit pas détecté.

Solution: les messages stables.

 un message reçu est stable si aucun message

portant une estampille inférieure ne parviendra au destinataire

délivrer un message que s’il est stable

 Attendre la réception d’un message de tous les émetteurs potentiels. Puis, les délivrer dans l’ordre des estampilles.

 Canaux FIFO (si non FIFO, c’est possible

mais plus complexe)

Solution: les messages stables.

 Connaître tous les émetteurs potentiels

 Traiter la non réception d’un processus : envoyer un message avec demande de réponse (ping)

 Pas de garantie pour la terminaison qu’elle soit en temps fini. (Dans la pratique, on utilise un délai de garde, avec le risque d’une arrivée tardive)

Horloges vectorielles

On cherche à caractériser la dépendance causale, en construisant un système de datation H qui ait la propriété de validité forte :

e  e‘ H(e) < H(e')

 Applications

◦ observation, mise au point (attribution d’une cause

à un effet)

◦ communication causale, diffusion causale ◦ contrôle et maintien de la cohérence d’informations

(Ex: la reprise après une panne)

Horloges vectorielles: Fidge, Mattern

Idée inclure le passé de l’événement “émission” dans l’estampille H du message Principe  Horloge vectorielle / Site  Taille

◦ Nombre de sites

But

◦ Dater les événements ◦ Identique aux horloges logiques

Horloges vectorielles: Fidge, Mattern (1988)

Fonctionnement  Associer un vecteur Vi à chaque site Pi  Init : Vi = (0, … , 0)  Evénement local à Pi

◦ Vi[i] = Vi[i]+1

 Emission d’un message m estampillé par Vm

◦ Vi[i] = Vi[i]+1 ◦ Vm = Vi de l’émetteur

 Réception d’un message (m, Vm) par Pi

◦ Vi[i] = Vi[i]+1 ◦ Vi[j] = max(Vi[i], Vm[j]) pour j = 1..n, j  i

Exemple

Horloge Vectorielle

Horloges vectorielles

Horloges matricielles

Synthèse  Horloge logique ou scalaire

◦ Réduite à un nombre

 Ce que Pi connaît du système (Hi)

 Horloge vectorielle

◦ Vecteur d’horloges scalaires  Ce que Pi connaît de Pj (Hi[j])

 Horloge matricielle ◦ Matrice d’horloges

 Ce que Pi connaît de ce que Pj connaît de Pk (Hi[j,k])

Horloges matricielles

Principe  Horloge matricielle/Site  nxn  Evénement ei de Pi

◦ Daté par la valeur courante de HMi

 Envoi de message ◦ Estampillé par Hmi

Sémantique  Interprétation de HMi[j,k]

◦ Nombre de messages de Pj vers Pk dont Pi a

connaissance

Horloges matricielles

 Evénement local à Pi ◦ HMi[i,i] = HMi[i,i] + 1

Envoi de message vers Pj HMi[i,i] = HMi[i,i] + 1 HMi[i,j] = HMi[i,j] + 1

 Réception de (m,Em) par Pj

 Délivré que si tous les messages qui sont causalement

antérieurs à lui ont été délivrés  Em[j,i] = HMi[j,i] + 1  Pour tout k  i,j: Em[k,i] = HMi[k,i] (messages des autres sites)

 Délivrance et MAJ horloges

 HMi[i,i] = HMi[i,i] + 1  HMi[j,i] = HMi[j,i] + 1  Pour tout k  i,j et pour tout l  i: HMi[k,l] = max(HMi[k,l],

Em[k,l])

Exemple

Exercice d’application

On considère l'exécution parallèle représentée par la figure

ci-dessous, dans laquelle :

les lignes horizontales représentent les échelles de temps de processus.

eij représente le jème événement observable sur le

processus Pi.

les flèches reliant les événements de processus distincts sont des échanges de messages

TAF: Appliquer l’algorithme de l’horloge matricielle sur les deux

systèmes répartis suivants.

Exercice d’application

1. Donner deux couples d'événements concurrents. 2. Quels sont les événements causalement dépendants de

e11 ?

3. Donner des exemples d’événements causalement

indépendants.

4. Proposer un modèle de datation relatif à cet exemple.

Horloges matricielles

Optimisations  les horloges matricielles sont coûteuses (

O(n2) )

 Diverses optimisations ont été proposées ◦ partitionner le système en sous-systèmes

(interaction faible entre sous-systèmes) - réduit n

◦ exploiter des caractéristiques spécifiques du

système (synchronisation)

◦ restreindre la “profondeur” du passé

Etat d’un Système Réparti Notion de Coupure

État d’un système réparti

Coupures

Coupures cohérentes

Propriétés des coupures cohérentes

Plan

 Introduction:

◦ Définition, organisation, propriétés, …

 Partie 1: Bases de l’algorithmique répartie 1. Etat dans un système réparti, ordre, temps, 2. Observation cohérente 3. Algorithmique répartie

 Partie2: Tolérance aux pannes et aux fautes

1. Validation atomique 2. Groupes, diffusion, cohérence 3. Consensus, prise de décision

Définition

Exclusion mutuelle  Contexte de plusieurs processus s'exécutant en parallèle  Accès à une ressource partagée par un seul processus à la

fois

Exclusion mutuelle en distribué  Accès à une ressource partagée distante par un seul

processus à la fois

Processus distribués  Requêtes et gestion d'accès via des messages échangés entre

les processus

 Nécessité de mettre en œuvre des algorithmes gérant ces échanges de messages pour assurer l'exclusion mutuelle

Rappel

 Un processus est dans 3 états possibles, par rapport

à l'accès à la ressource

 Demandeur : demande à utiliser la ressource, à

entrer dans la section

 Dedans : dans la section critique, utilise la ressource

partagée

 Dehors : en dehors de la section et non demandeur

d'y entrer

Changement d'état par un processus

 De dehors à demandeur pour demander à accéder à

la ressource

 De dedans à dehors pour préciser qu'il libère la

Ressource

 Le passage de l'état demandeur à l'état dedans est géré par le système et/ou l'algorithme de gestion d'accès à la ressource

Plusieurs grandes familles de méthodes  Contrôle par un serveur qui centralise les

demandes d'accès à la ressource partagée

 Contrôle par jeton ◦ Un jeton circule entre les processus et donne l'accès à la

ressource

◦ La gestion et l'affectation du jeton – et donc l'accès à la

ressource – est faite par les processus entre eux Deux approches : jeton circulant en permanence ou

affecté à la demande des processus

 Contrôle par permission ◦ Les processus s'autorisent mutuellement à accéder à la

ressource

Plusieurs grandes familles de méthodes

Contrôle par un serveur centraliseur Avantages  Très simple à mettre en œuvre  Simple pour gérer la concurrence d'accès à la

ressource Inconvénients  Nécessite un élément particulier pour gérer

l'accès

 Potentiel point faible, goulot d'étranglement

Plusieurs grandes familles de méthodes

 Contrôle par jeton ◦ Principe général

 Un jeton unique circule entre tous les processus  Le processus qui a le jeton est le seul qui peut

accéder à la section critique

◦ Versions de l’algorithme

 Anneau sur lequel circule le jeton en permanence  Jeton affecté à la demande des processus

Plusieurs grandes familles de méthodes

 Contrôle par jeton sur anneau ◦ un processus reçoit le jeton ◦ S'il est dans l'état demandeur : il passe dans l'état

dedans et accède à la ressource

◦ S'il est dans l'état dehors, il passe le jeton à son voisin ◦ Quand le processus quitte l'état dedans, il passe le

jeton à son voisin

Contrôle par jeton sur anneau

Avantages  Très simple à mettre en œuvre  Intéressant si nombreux processus demandeurs de la ressource  Équitable en terme de nombre d'accès et de temps d'attente  Aucun processus n'est privilégié

Inconvénients  Nécessite des échanges de messages (pour faire circuler le jeton)

même si aucun site ne veut accéder à la ressource

 Temps d'accès à la ressource peut être potentiellement long  Si le processus i+1 a le jeton et que le processus i veut accéder à la ressource et est le seul à vouloir y accéder, il faut que le jeton fasse tout le tour de l'anneau

Contrôle par jeton avec communication entre processus

 Soit N processus avec un canal bi-directionnel entre chaque processus

 Canaux fiables mais pas forcément FIFO

 Localement, un processus Pi possède un tableau nbreq, de taille N

 Pour Pi, nbreq [ j ] est le nombre de requêtes d'accès que le processus Pj a fait et que Pi connaît (par principe il les connaît toutes)  Le jeton est un tableau de taille N  jeton [ i ] est le nombre de fois où le processus Pi a accédé à la

ressource

 La case i de jeton n'est modifiée que par Pi quand celui-ci accède à la

ressource

Contrôle par jeton avec communication entre processus (suite)

 Initialisation

 Pour tous les sites Pi :  j  [ 1 .. N ] : nbreq [ j ] = 0

 Jeton  j  [ 1 .. N ] : jeton [ j ] = 0

 Un site donné possède le jeton au départ

Quand un site veut accéder à la ressource et n'a pas le jeton

 Envoie un message de requête à tous les processus

Contrôle par jeton avec communication entre processus (suite)

Quand processus Pj reçoit un message de requête venant de Pi

 Pj modifie son nbreq localement : nbreq [ i ] = nbreq [ i ] + 1

 Pj mémorise que Pi a demandé à avoir la ressource

 Si Pj possède le jeton et est dans l'état dehors

 Pj envoie le jeton à Pi

Quand processus récupère le jeton

 Il accède à la ressource (passe dans l'état dedans)

Contrôle par jeton avec communication entre processus (suite)

Quand Pi libère la ressource (passe dans l'état dehors)

 Met à jour le jeton : jeton [ i ] = jeton [ i ] + 1

 Parcourt nbreq pour trouver un j tel que :

◦ nbreq [ j ] > jeton[j]

 Une demande d'accès à la ressource de Pj n'a pas

encore été satisfaite : Pi envoie le jeton à Pj

 Si aucun processus n'attend le jeton : Pi le garde

Contrôle par Permission

Un processus demande l'autorisation à un sous-

ensemble donné de tous les processus

Deux modes:  Permission individuelle : un processus peut donner

sa permission à plusieurs autres à la fois

 Permission par arbitre : un processus ne donne sa

permission qu'à un seul processus à la fois

◦ Les sous-ensembles sont conçus alors tel qu'au moins un processus soit commun à 2 sous-ensembles : il joue le rôle d'arbitre

Permission individuelle

 un processus peut donner sa permission à

plusieurs autres à la fois

 Chaque processus demande l'autorisation à tous

les autres (sauf lui par principe)

◦ Liste des processus à interroger par le processus Pi pour

accéder à la ressource : Ri = { 1, ... , N } – { i }

Permission individuelle

 Se base sur une horloge logique (Lamport) pour garantir le bon fonctionnement de l'algorithme

◦ Ordonnancement des demandes d'accès à la ressource

◦ Si un processus ayant fait une demande d'accès reçoit une demande d'un autre processus avec une date antérieure à la sienne, il donnera son autorisation à l'autre processus

Algorithme de [Ricart & Agrawala]

 Chaque processus gère les variables locales suivantes:  Une horloge Hi  Une variable dernier qui contient la date de la dernière

demande d'accès la ressource

 L'ensemble Ri  Un ensemble d'identificateurs de processus dont on attend

une réponse : attendu

 Un ensemble d'identificateurs de processus dont on diffère le renvoi de permission si on est plus prioritaire qu'eux : différé

 Initialisation ◦ Hi = dernier = 0 ◦ différé = , attendu = Ri

Algorithme de [Ricart & Agrawala]

 Si un processus veut accéder à la ressource, il exécute

◦ Hi = Hi + 1 ◦ dernier = Hi ◦ attendu = Ri ◦ Envoie une demande de permission à tous les processus de Ri avec

estampille (Hi, i )

◦ Se met alors en attente de réception de permission de la part de tous les

processus dont l'identificateur est contenu dans attendu

◦ Quand l'ensemble attendu est vide, le processus a reçu la permission de tous

les autres processus

 Accède alors à la ressource partagée  Quand accès terminé

 Envoie une permission à tous les processus dont l'id est dans différé  différé est ensuite réinitialisé (différé = )

Algorithme de [Ricart & Agrawala]

 Quand un processus Pi reçoit une demande de permission de

la part du processus Pj contenant l'estampille (H, j) ◦ Met à jour Hi : Hi = max (Hi, H) +1

◦ Si Pi pas en attente d'accès à la ressource : envoie permission à Pj

◦ Sinon, si Pi est en attente d'accès à la ressource

 Si Pi est prioritaire : place j dans l'ensemble différé

 On lui enverra la permission quand on aura accédé à la ressource

 Si Pj est prioritaire : envoi permission à Pj,

 Pj doit passer avant moi, je lui envoie ma permission

 La priorité est définie selon la datation des demandes d'accès à la ressource

de chaque processus

 Le processus prioritaire est celui qui a fait sa demande en premier

 Ordre des dates : l'ordre << de l'horloge de Lamport :

( dernier, i ) << ( H, j ) si ( ( dernier < H ) ou ( dernier = H et i < j ) )

Élection

 Problème

◦ Parmi un ensemble de processus, en choisir un

et un seul (et le faire connaître à tous)  sécurité : un seul processus élu  vivacité : un processus doit être élu en temps fini

◦ L’élection peut être déclenchée par un

processus quelconque, éventuellement par plusieurs processus

◦ L’identité de l’élu est en général indifférente,

on peut donc (par exemple) choisir le processus qui a le plus grand numéro

◦ Difficulté : des processus peuvent tomber en

panne pendant l’élection

Élection

 Utilité et domaines d’application

◦ Regénération d’un jeton perdu : un jeton et un

seul doit être recréé

◦ Dans les algorithmes de type “maître-esclave” :

élire un nouveau maître

◦ en cas de défaillance du maître courant

Élection

Algorithme de base: Bully algorithm

◦ Algorithme de la brute ◦ Hypothèses

 Réseau fiable et synchrone  Identité des processus connue par tous

 Principe

◦ Basé sur la recherche d’un min ou max d’un

ensemble

◦ Demande d’élection par inondation ◦ Réponse à ceux qui ont un numéro inférieur ◦ le Processus est élu s’il ne reçoit aucune réponse

Élection: algorithme de la brute (bully)

Election sur un anneau (Chang et Roberts)

Terminaison (1)

 Modèle de calcul réparti (rappel)

◦ Ensemble de processus communiquant par messages ; état actif

ou passif

◦ Programme (cyclique) de chaque processus :

loop

1. attendre un message (passage temporaire à l’état passif) 2. exécuter un calcul local en réponse à ce message 3. le calcul peut comporter l’envoi de messages à d’autres processus ou la terminaison du processus (passage définitif à l’état passif)

end

 Problème de la terminaison ◦ Vérifier que le calcul est achevé ◦ Cela implique deux conditions sur l’état global du système

 Tous les processus sont au repos (passifs)  Aucun message n’est en transit

◦ En effet l’arrivée d’un message en transit peut relancer le calcul

réparti

Terminaison (2)

 Méthodes pour détecter la terminaison 1. Méthode générale : analyse de l’état global ◦ La terminaison est une propriété stable ◦ On peut donc la détecter par examen d’un état global enregistré (Partie 1 du cours)

2. Méthodes spécifiques : applicables à un schéma particulier de communication

◦ Sur un anneau ◦ Sur un arbre ou un graphe orienté (avec arbre

couvrant)

Terminaison sur un anneau

Principe :  visiter l’anneau dans le sens de la communication et vérifier que tous les sites sont passifs après un tour complet Difficulté :  un message émis après le passage du visiteur (et non visible par celui-ci) peut venir réactiver (derrière lui) un site trouvé passif

Terminaison sur un anneau (Misra)



é é

Terminaison sur un anneau (Misra)