Promotion BADS AU 2019/20

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

un système de communication ; les éléments ont des fonctions de traitement (processeurs), de stockage (mémoire), de relation avec le monde extérieur (capteurs, actionneurs)

(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)

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) (service de base)
le World Wide Web (infrastructure)
divers services sur l’Internet (applications)

 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

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)

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

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

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

 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

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

 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

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)

Un message arrive intact (non modifié) ; on suppose que

des mécanismes de détection / correction d’erreur sont utilisés

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

FIFO entre deux processus

message de sa délivrance à son destinataire

historique (ou trace) du processus

- pour p1 : e, e, e, …, e, …

11 12 13 1k

 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)

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

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é)

 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)

 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

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é)

 Canal non FIFO. L’observation viole la causalité : les événements sont observés dans l’ordre inverse de leur occurrence

 La causalité est encore violée :

e 1  e 1 2
- e 1  e 2, mais ces événements sont observés dans 1 2

l’ordre inverse.  Ce phénomène est indépendant de la propriété

FIFO

 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))

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

 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é

 à 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

 É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

 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

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

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

délivrer ?

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é.

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)

 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)

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)

message Principe

 Horloge vectorielle / Site

 Taille

 - Nombre de sites

But

 - Dater les événements

 - Identique aux horloges logiques

 Evénement local à Pi

Vi = Vi +1  Emission d’un message m estampillé par Vm
Vi = Vi +1
Vm = Vi de l’émetteur  Réception d’un message (m, Vm) par Pi
- Vi = Vi +1
- Vi = max(Vi , Vm ) pour j = 1..n, j  i

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 )

 Horloge matricielle

Matrice d’horloges  Ce que Pi connaît de ce que Pj connaît de Pk (Hi )

 Evénement ei de Pi

Daté par la valeur courante de HMi  Envoi de message
Estampillé par Hmi

Sémantique

 Interprétation de HMi

Nombre de messages de Pj vers Pk dont Pi a connaissance

Envoi de message vers Pj

HMi = HMi + 1 HMi = HMi + 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 = HMi + 1

 Pour tout k  i,j: Em = HMi (messages des autres sites)

 Délivrance et MAJ horloges

 HMi = HMi + 1

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

Em )

de processus.

e représente le jème événement observable sur le ij

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.

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

e11 ?

Donner des exemples d’événements causalement

indépendants.

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

 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é

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

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

 Partie2: Tolérance aux pannes et aux fautes

Validation atomique
Groupes, diffusion, cohérence
Consensus, prise de décision

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

 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

 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

 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

 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

 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

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

 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

 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

 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

 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 )

 Parcourt nbreq pour trouver un j tel que :

 - nbreq [ j ] > jeton

 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

 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

 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 }

- 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

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

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é = )

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 ) )

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

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
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
Ensemble de processus communiquant par messages ; état actif ou passif
Programme (cyclique) de chaque processus : loop

attendre un message (passage temporaire à l’état passif)
exécuter un calcul local en réponse à ce message
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
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)
Méthodes spécifiques : applicables à un

schéma particulier de communication

Sur un anneau
Sur un arbre ou un graphe orienté (avec arbre couvrant)

complet Difficulté :

site trouvé passif

 é é

 é

 è