UNIVERSITE A.

MIRA-BEJAIA
FACULTE DES SCIENCES EXACTES
DEPARTEMENT INFORMATIQUE

SUPPORT DE COURS
SYSTEMES DISTRIBUES
SYNCHRONISATION D’HORLOGE

I- INTRODUCTION
Les applications distribuées ont les propriétés suivantes:

• les informations importantes sont disséminées sur plusieurs sites

• les processus prennent des décisions sur la base des informations locales

• le système (application répartie) ne doit pas avoir de ”talon d’Achille”

• il n’existe pas d’horloge commune

1. Algorithmes distribués
Un algorithme distribué est un ensemble de processus qui réalisent un but commun par communi-
cations de messages.

Caractéristiques:

• Degré de répartition: on parle de niveau de symétrie, exemple:

– non-symétrie: chaque processus exécute un code différent

– symétrie forte: les processus exécutent le même code et peuvent avoir des comportements
identiques ou différents
– symétrie totale: les processus exécutent le même code et génèrent le même comporte-
ment.

• Résistances aux pannes: pouvoir continuer et se reconfigurer

• Indépendant de la couche réseau (∀ protocole de transfert)

• Trafic engendré: moins de messages ⇒ temps d’attente des processus réduit

• Etat global ou local: connaissance des variables locales et avoir une copie des variables glob-
ales.

Techniques d’algorithmique distribuée:

• Le calcul diffusant: le principe est un processus racine qui émet des messages vers ses suc-
cesseurs, chaque processus qui reçoit un message le transmet à ses successeurs et attend des
réponses qu’il transmet au père. Un processus feuille retourne immédiatement une réponse
et le processus racine ayant reçu toutes les réponses termine le calcul. C’est un algorithme
utilisé pour contrôler la terminaison d’un traitement ou des situations d’interblocage.

1
 • Le jeton circulant: faire circuler un privilège dans un anneau (logique) de processus. L’algorithme
est utilisé en exclusion mutuelle et terminaison.

• Estampillage: pour avoir un ordre total, chaque processus Pi gère une horloge logique hi et
estampille ses messages <m, hi, i>. A la réception de ce message par Pj celui-ci met à jour son
horloge: hj=max(hi, hj)+1 (à chaque événement un processus met à jour son horloge local
h=h+1). On peut établir un ordre de précédence entre les processus grâce à ces estampilles
(si hi=hj alors l’ordre est donné par i<j)

2. Horloge physique
Utile pour les systèmes temps réel, bancaires, spatiale, etc.
Pour mesurer le temps:

1- la seconde solaire=1/86400 jour solaire

- jour solaire = intervalle entre deux transits solaires (soleil au plus haut)

- en général on mesure le jour solaire dans plusieurs endroits de la terre et on calcule la moyenne.

- le problème est que le jour solaire s’allonge et le nombre de jours dans l’année se réduit.
(Temps absolu de rotation de la terre est fixe)

2- la seconde atomique= intervalle de temps que prend l’atome de Césium 133 pour faire ex-
actement 9192631770 transitions.

- plusieurs horloges atomiques a travers le monde communiquent le temps au bureau inter-

national de l’heure à paris qui en calcule la moyenne et qui correspond au temps atomique
international (TAI)

- problème: le TAI retarde sur le temps solaire

- solution: a chaque retard de 800ms, on ajoute une seconde (sautée) au TAI⇒ temps universel
coordonné (TUC)

3- des radios spécialisés WWV donnent l’heure (TUC) avec une précision de 1ms.

- des satellites (comme GEOS) donnent le TUC avec une précision de 0.5ms

- un système informatique doit pouvoir à chaque instant synchroniser son horloge sur le TUC
(avec un récepteur WWV ou une liaison par satellite)

3. Horloge logique
Chaque ordinateur dispose d’un temporisateur: c’est un circuit composé d’un cristal de quartz
oscillant plus un registre de sauvegarde initialisé à une valeur fixe et un compteur. Le compteur
décompte de la valeur initiale et une interruption est générée à chaque valeur zéro du compteur.
Cette interruption est l’impulsion de l’horloge (clock tick). Dans le cas distribué il est impossible de
garantir que le quartz des différentes machines vibre à la même fréquence ⇒ une dérive de l’horloge.
Lamport (1978) a proposé un algorithme de synchronisation d’horloge basé sur l’ordre des
événements:

i) les processus indépendants n’ont pas besoin de se synchroniser

ii) les autres peuvent s’accorder sur l’ordre des événements.

2
 Remarque

Horloge logique: la cohérence entre les horloges existe mais pas par rapport au temps réel.

Horloge physique: il doit y avoir une cohérence avec l’heure et la date réelle.

II. ETAT PARTIEL / ETAT GLOBAL

1. Ordre des événements
Un système centralisé dispose d’une seule mémoire et une seule horloge donc l’ordre de précédence
entre deux événements est connu: ordre global. Un système répartie ne dispose pas d’horloge
commune donc l’ordre entre tous les événements du système n’est pas connu: ordre partiel (il est
connu au niveau de chaque machine). Un bon algorithme réparti doit étendre la relation d’ordre
partiel à une relation d’ordre globale ou une relation d’ordre total cohérente.
Les dépendances causales définissent des ordres partiels pour des ensembles d’événements

2. La relation de précédence
(notée: →) A précède B s’écrit A→B. Les événements d’un seul processus sont totalement ordonnés.
Un message n’est reçu qu’aprés avoir été envoyé (loi de causalité). La relation de précédence est
définie par:

i) si (A,B) ∈ même processus et A s’exécute avant B alors: A→B

ii) si A est l’événement (envoyer message m) et B l’événement (recevoir message m) alors: A→B

iii) si A→B et B→C alors A→C (transitivité)

La relation de précédence est non réflexive, non commutative et transitive. C’est une relation
d’ordre partiel. Si (A, B) ne sont pas liés par la relation de précédence alors A et B sont dits
concurrents.

3. Ordre partiel
Soit l’exemple suivant:

Site1 Site2
A1
B1
A2
B2 temps
A3
B3
A4
B4
A5

• Ordre local des événements:

site1: A1→A2...→A5.
site2: B1→B2...→B4.

3
 • Loi de causalité:
A2 → B2
B3 → A4

• Par transitivité:
A1→A2→B2→B3→B4.
B1→B2→B3→A4→A5.
A1→A2→B2→B3→A4→A5.

• Evénements concurrents: B1 et A1, A2, A3 ou A3 et B2, B3, B4 etc.

Exemple1: Causalité non respectée Exemple2: Causalité respectée

4. Ordre global
L’ordre partiel des evenements induit des incoherences sur un système distribué.
Exemple : soit un parking et trois gardiens éloignés. Etat initial: 100 places vides. Les trois
gardiens (G1, G2, G3) diffusent les messages suivants: M1 <20 places libérés>, M2 <10 places
occupés>, M3 <10% des places réservés pour le nettoyage>. Résultat on peut avoir plusieurs
situations:
Ordre Initialement Sequence Total
G1 100 M1, M3, M2 98
G2 100 M2, M1, M3 99
G3 100 M3, M1, M2 100

Pour un problème d’allocation de ressources: dans un cas centralisé les requêtes et avis de
libération sont ordonnés. Dans un cas réparti soit les messages arrivent un à la fois et l’ordre est
strict, soit plusieurs messages (requêtes ou libérations) arrivent en même temps et la machine les
range dans une file d’attente pour les traiter en exclusion mutuelle. On doit les ranger dans l’ordre
de leur émission donc le système doit pouvoir ordonner globalement l’émission des messages.
Solution: il faut un algorithme qui permet d’ordonner globalement les événements.

5. Etat global et Coupures

Un calcul distribué est un ensemble d’événements E.
Une coupure est une photographie (snapshot) instantanée de l’etat d’un système : ensemble
d’événements (virtuels), un par processus, qui permet de définir un passé et un futur (par rapport
à la coupure). Relation d’ordre (partiel) sur les coupures est obtenu par inclusion des passés .
Etat associé à une coupure C est l’ensemble d’états locaux Si (un par processus) tel que l’effet
local de tout événement de C soit pris en compte dans Si.
Exemple: Sur la figure 1: L’etat de C={e11, e25, e32}

4
 Figure 1: Exemple coupure

• Cohérence est le respect de la causalité (un message ne peut pas venir du futur)

• Coupure cohérente est une coupure férmee par la relation de dependance causale:
(a ∈ C) et (b → a) alors (b ∈ C)

• Etat global cohérent est l’etat associé à une coupure cohérente

• Les coupures cohérentes permettent de définir un ordre de précédence entre états globaux
cohérents, et permettent aussi la reprise après une panne.

Exemple: C={e11, e25, e32} C est cohérente

C’={e11, e25, e34} C’ n’est pas cohérente car: (e34∈ C’) et(e13 → e34) mais (e13 6 in C’)

Figure 2: Coherence

III. CONSTRUCTION D’UN ETAT GLOBAL

1. Ordonnancement par estampilles:
A chaque événement on associe une estampille qui est une valeur numérique instantané d’une
horloge logique locale au site. Pour un événement A on associe son estampille E(A) et si A→B
alors E(A)<E(B). Cet algorithme assure un ordre global pour des processus sur un même site mais
pas entre plusieurs sites. Exemple: soit deux processus P1 et P2 sur deux sites i et j et deux
événements A et B

A: P1 envoie un message m à P2 E(A)=200

B: P2 reçoit le message m E(B)=195 (horloge de P2 retarde)

5
Donc A→B mais E(A)>E(B)
Solution: quand un processus reçoit un message avec une estampille supérieur à son horloge
alors il avance son horloge à la valeur de l’estampille plus 1.

2. Horloge de Lamport:
• chaque site est muni d’un compteur à valeur entière Hs appelé horloge logique

• Hs est incrémenté entre chaque deux événements successifs

• un site émetteur marque d’une estampille E son message (E=valeur courante He)

• le site récepteur reçoit le message et met à jour son horloge logique: si Hr<E alors Hr=E+1
(l’événement réception est daté par Hr), et on obtient une relation d’ordre totale:
A→B⇔Hi(A)<Hj(B).

Pour avoir un ordre total stricte on associe le numéro d’un site à l’estampille: A→B ⇔
(Hi(A)<Hj(B))ou(Hi(A)=Hj(B) et i<j)

Figure 3: Exemple Horloge de Lamport

Inconvenients des horloges scalaires

- Les estampilles ne conservent pas la trace des chemins de causalité
- Non constantes = pas de lien avec la précédence
- Nécessité de conserver l’état de chaque estampille pour déterminer localement la précédence
entre deux événements

3. Horloges vectorielles
Horloge de Mattern et Fidge (vectorielles) assure la réciproque de la dépendance causale (H(e)
< H(e’) ⇒ e→ e’), permet également de savoir si 2 événements sont parallèles (non dépendants
causalement), mais ne définit pas un ordre total global!.
Utilisation d’estampilles sur les messages: Vecteur V de taille égale au nombre de processus.
Localement, chaque processus Pi a un vecteur Vi telque chaque case Vi[j] du vecteur contiendra
des valeurs de l’horloge du processus Pj.

Fonctionnement

• On associe un vecteur Vi à chaque processus Pi (ou site Si), i=1, ... , n

6
 • Initialement, Vi = (0, ... , 0)

• A chaque événement local à Pi, Vi[i] := Vi[i] + 1;

• Chaque message m porte une estampille Vm (Vm = Vi de lémetteur)

• A la réception de (m, Vm) par un processus Pi :

- Vi[j] := max(Vi[j], Vm[j]) pour j = 1, ... , n, j 6= i
- mémorise le nombre d’événements sur Pj qui sont sur Pj dépendants causalement par rapport
à l’émission du message. La réception du message est donc aussi dépendante causalement de
ces événements sur Pj
- Vi[i] := Vi[i] + 1

Figure 4: Exemple Horloge vectorielle

Caracteristiques:

• Relation d’ordre partiel sur les dates

- V ≤ V’ défini par ∀ i : V[i] ≤ V’[i]
- V < V’ défini par V ≤ V’ et ∃ j tel que V[j] < V’[j]
- V || V’ défini par ¬(V < V’) ∧ ¬(V’ < V)

• Dependance et independance causales: Horloge de Mattern assure les proprietes suivantes,

avec e et e’ deux événements et V(e) et V(e’) leurs datations
- V(e) < V(e’) ⇒ e→e’(Si deux dates sont ordonnées, on a forcément dépendance causale
entre les événements datés
- V(e) || V(e’)⇒ e || e’ (Si il n’y a aucun ordre entre les 2 dates, les 2 événements sont
indépendants causalement)

Horloge vectorielle et Coupures coherentes:

Horloge de Mattern permet de dater la coupure. Soit N processus, C la coupure, ei l’événement
le plus récent pour le processus Pi, V(ei) la datation de ei et V(C) la datation de la coupure.
V(C)=max{V(e1), ... , V(eN)}: ∀ i: V(C)[i]=max{ V(e1)[i], ... ,V(eN)[i]}

Horloge vectorielle permet egalement de determiner si la coupure est cohérente.

7
 C est cohérente si V(C)=(V(e1)[1], ... ,V(ei)[i], ... , V(eN)[N])
Pour un processus Pi, si l’événement ei est le plus récent c’est lui qui a la date la plus récente
pour C; sinon un événement ej d’un processus Pj (i6=j) s’est deroulé après un événement ei’ de Pi
avec ei’ plus recent que ei: ei→ ei’ et ei’→ ej avec ei ∈ C, ej ∈ C et ei’¬ ∈C

Figure 5: Coupure vectorielle

Pour l’exemple de la figure 5:

Coupure C1 : cohérente
Coupure C2 : non cohérente car e35 → e23 mais e35 ¬ ∈ C2 (La réception de m5 est dans la
coupure mais pas son émission, m5 vient du futur par rapport à la coupure).

Inconvénients de l’horloge de Mattern

- Ne permet pas de définir un ordre global total
- En cas de nombreux processus, la taille du vecteur peut-être importante et donc des données
à transmettre relativement importante.

4. Horloges matricielles
Dans un système de n sites, les horloges d’un site i et les estampilles des événements (et des
messages) sont des matrices carrées d’ordre n.
HMi désigne l’horloge matricielle du site Si,
EMm désigne l’estampille matricielle du message m,
Mémorisation dans une matrice :
element (i, i) : état du processus i
element (i, j) : nombre de messages que Pi a envoyé à Pj

Fonctionnement: Sur le site Si, la matrice HMi va :

• mémoriser le nombre de messages que le site Si a envoyé aux différents autres sites: cette
information est fournie par la ième ligne de la matrice.

• l’élément diagonal représente la connaissance qu’a Si du nombre d’événements locaux qui se

sont déjà produits sur les différents sites Sj: correspond à lestampille vectorielle.

• mémoriser, pour chacun des autres sites j, le nombre de messages émis par ce site dont le site
i a connaissance.

• ainsi sur le site i, la valeur EMi [j,k] donne le nombre de messages en provenance du site
Sj délivrables sur le site Sk dont le site Si a connaissance (i.e dont lenvoi est causalement
antérieur à tout ce qui arrivera dorénavant sur Si).

8
 • lorsqu’un evenement local se produit sur le site Si: HMi[i,i] est incrementé;

• lorsqu’un message est expedié à partir du site Si vers le site Sj: HMi[i,i] et HMi[i,j] sont
incrementés;

• lorsqu’un message m en provenance du site Sj est reçu sur le site Si , il faut s’assurer que tous
les messages envoyés antérieurement au site Si y sont effectivement arrivés. Cela suppose
donc que Si ait reçu : d’une part tous les messages precedents de Sj, et d’autre part tous ceux
envoyés plus tôt causalement depuis d’autres sites. Cela correspond aux conditions suivantes:
1. HMm [j,i] = HMi [j,i] + 1 (ordre FIFO sur le canal (j,i))
2. pour tout k 6=i et j, HMm[k,i] ≤ HMi[k,i] (tous les messages en provenance des sites
différents de Sj ont été reçus).

• si toutes ces conditions sont vérifiées, le message est délivrable et l’horloge du site Si est mise
à jour :
1. HMi[i,i] est incrémenté;
2. HMi[j,i] est incrémenté;
3. pour le reste de la matrice : HMi[k,l]=max(HMi[k,l], EMm[k,l])

• sinon, la délivrance du message est différée jusquà ce qu’elles le deviennent et l’horloge nest
pas mise à jour. La délivrance dun message pourra ainsi provoquer celle des messages arrivés
prématurément.

Exercice: On considère un système distribué constitué de deux sites utilisant des horloges
matricielles pour dater les événements de chaque
à processus.
!
0 0
L’tat initial du chaque processus est : .
0 0
Après
à quelques! instantsà d’exécution,
! les horloges des processus indiquent les dates suivantes:
3 0 0 0
HM1 = HM2 =
1 1 1 2
i) Combien de messages ont été échangés ?
ii) Combien d’événements ont eu lieu ?
iii) Réaliser le chronogramme de ce système.

5. Séquenceur:
les estampilles laissent des trous dans la numérotation des événements. Si c’est nécessaire, on définit
un mécanisme basé sur le principe du ticket afin de respecter l’ordre d’arrivée des demandeurs. Le
séquenceur est le mécanisme (processus ou serveur) qui exécute la fonction ticket() (un compteur)
et génère des numéros uniques consécutifs. La première valeur retournée est 0 et tous les numéros
retournés sont distincts.
Inconvénient: l’exécution en exclusion mutuelle de la fonction ticket()doit être garantie et limite
le parallélisme des sites participants.

Mme YAICI