SDR

Estampilles

Olivier Lemer

Horloges Logiques

Le problème des horloges

Le problème des horloges

L'ordre des évènements n'apparait pas le même partout.

B

A

Envoi <A1>

Réception <B1>

Envoi <B1>

Réception <A1>

A1 → B1

B1 → A1

La synchronisation comme solution ?

Créer une horloge commune ?

Problème : Horloges à quartz dérivent différemment selon la machine.

Solutions : protocoles de mise à l'heure.

  • Network Time Protocol : longue distance, ms precision.
  • Precision Time Protocol : courte distance, µs precision.

Pas de solution permettant une horloge globale parfaite : toujours soumis aux délais et variabilités du réseau.

Nos besoins

Résolution par requirements

Quels sont les besoins ?

On veut connaitre

l'heure exacte de chaque évènement.

relative

l'ordre des évènements.

?

Qu'est-ce qu'un évènement ?

  • Une action sur une machine
  • Emission d'un message
  • Réception d'un message

(exécution d'une ou plusieurs instructions)

?

Qu'est-ce qu'un ordre d'évènements ?

Quand est-ce que E1 → E2 ?

  • Si E1 et E2 sont sur la même machine et E1 arrive avant E2.
  • Si E1 est l'émission d'un message et E2 sa réception.

E1

E2

E2

E1

Une relation d'ordre

Propriétés

Transitif

Anti-réflexif

Anti-symétrique

E1

E2

E2

E3

et

⇒

E1

E3

E1

E2

⇒

E1

E2

E1

Ordre Partiel ou Total ?

(Partiel s'il existe deux évènements E1 et E2 tels que ni E1 → E2, ni E2 → E1.)

Une relation d'ordre

Propriétés

Transitif

Anti-réflexif

Anti-symétrique

E1

E2

E2

E3

et

⇒

E1

E3

E1

E2

⇒

E1

E2

E1

Ordre Partiel

(i.e. il existe deux évènements E1 et E2 tels que ni E1 → E2, ni E2 → E1.)

E2 → F3 ?

F3 → E2 ?

F2

E1

F1

E2

F3

Les deux sont possibles.

Horloge logique

Une horloge logique

Représenter l'ordre partiel des évènements.

On veut :

une fonction H telle que :

0

1

2

3

4

5

6

0

1

2

3

4

5

6

E1

E2

H = 2

H = 3

E3

E4

H = 6

H = 5

Idée 1 : horloge logique = horloge locale ?

(i.e. H(E) = heure sur la machine sur laquelle l'évènement a eu lieu)

E1 → E2

H(E1) < H(E2)

⇒

E3 → E4

H(E3)    H(E4)

mais

>

L'horloge logique de Lamport

L'idée : les timestamps (ou estampilles)

A

B

t = 1

t = 1

t = 2

(t = 3)

t = 3

t = 4

t = 5

  • Chaque site maintient un numéro.

t = max(3,  )+1

= 5

4

t = max(5,  )+1

= 6

5

= 6

t = max(  ,5)+1

3

(t = 4)

(t = 5)

  • À chaque événement local,

le timestamp est incrémenté.

  • Le timestamp est envoyé

avec chaque nouveau message.

  • À la réception, le timestamp le plus

grand entre local et reçu est utilisé

et incrémenté.

(t = 2)

= 3

t = max(  ,1)+1

2

L'horloge logique de Lamport

Vérification des besoins

On voulait :

une fonction H telle que :

E1 → E2

H(E1) < H(E2)

⇒

  • Si E1 et E2 sont sur la même machine et E1 arrive avant E2.
  • Si E1 est l'émission d'un message et E2 sa réception.

On avait définit E1 → E2 :

H(E1) < H(E2)

⇒

?

H(E1) < H(E2)

⇒

?

L'horloge logique de Lamport

Vérification des besoins - un ordre total ?

On voulait :

une fonction H telle que :

E1 → E2

H(E1) < H(E2)

⇒

Remarque :

E1 → E2

H(E1) < H(E2)

⇒

On projette un ordre partiel sur un ordre total.

Autrement dit, si E1 et E2 n'ont pas de relation, H leur en donne une.

L'horloge logique de Lamport

Vérification des besoins - Un ordre total stricte ?

Remarque : On peut avoir H(E1) = H(E2).

Compliqué pour prendre des décisions, affecter des priorités, etc.

Ce n'est pas un ordre stricte.

Solution : le rendre stricte

1

2

t = 1

t = 1

F2

E1

t = 2

t = 2

H(E1) = H(F1), E1 est placé avant F1, car 1 < 2.

F1

E2

t = 3

t = 3

Si E1 arrive sur machine i,

E2 arrive sur machine j,

et H(E1) = H(E2),

Alors E1 est arrivé avant E2.

tels que i < j

, arbitrairement :

priorité à la machine à l'ID le plus petit.

L'horloge logique de Lamport

Ordre total rendu strict ; Exemple

1

2

t = 1

t = 1

F2

E1

t = 2

t = 2

F1

E2

t = 3

t = 3

Quel est l'ordre ?

E1,

F1,

E2,

F2.

Exercices

Quel est l'ordre des événements ?

1

t = 1

t = 1

F1

E2

2

3

t = 1

F2

E1

E3

F3

G1

G2

E4

G3

Exercice 1 - ordre total strict

E1, F1, E2, E3, G1, E4, G2, F2, G3, F3

1

t = 1

t = 1

t = 2

t = 2

F1

E2

t = 3

t = 6

2

3

t = 1

F2

E1

E3

t = 4

t = 7

F3

t = 4

G1

t = 5

G2

t = 5

E4

t = 6

G3

Quel est l'ordre des événements ?

Exercice 1 - ordre total strict

Solution

Exercice 2 - file d'attente distribuée

Plusieurs distributeurs de tickets, communiquant suivant le protocole de Lamport,

Chaque distributeur peut délivrer un ticket, affichant

  • la valeur actuelle du timestamp de Lamport
  • et le numéro du distributeur qui l'a délivré.

Chaque client doit d'abord obtenir un ticket au distributeur le plus proche.

Celui ayant le ticket (timestamp, numéro) le plus petit peut aller au guichet.

Questions :

  1. Tout personne est-elle sûre de passer un jour ?
  2. L'ordre d'arrivée des personnes est-il respecté ?
  3. Quels avantages par rapport à un système central délivrant des numéros aux distributeurs ?
  4. Que se passe-t-il si un distributeur tombe en panne et redémarre en repartant à son dernier timestamp ?

où une demande de ticket représente un événement.

Exercice 2 - file d'attente distribuée

  1. Tout personne est-elle sûre de passer un jour ?
    • Peut être prouvé par l'absurde : en notant que, si une personne ne passe pas, c'est qu'une autre a un ticket plus ancien et passe donc en premier, on voit que, si une personne ne passe jamais, c'est qu'il existe un nombre infini de personnes avec un ticket plus ancien, qui sont donc arrivées avant elles. Notre personne n'est donc jamais arrivée, une contradiction.
  2. L'ordre d'arrivée des personnes est-il respecté ?
    • Pas toujours. Si une machine tombe en panne et reboot, son premier ticket sera le plus ancien. Sinon, si deux personnes arrivent presque au même moment sur des machines ayant le même timestamp, l'ordre sera arbitraire en fonction de l'id de la machine.
  3. Quels avantages par rapport à un système central délivrant des numéros aux distributeurs ?
    • En cas de panne d'une machine, le reste fonctionne toujours, contrairement à un système centralisé qui est à l'arrêt si le processus central tombe en panne.
    • C'est aussi plus rapide s'il y a beaucoup de machines, car pas de bottleneck.
  4. Que se passe-t-il si un distributeur tombe en panne et redémarre en repartant à son dernier timestamp ?
    • Comme dit à la question 2 ; le ticket délivré sera le plus ancien et la personne sera privilégiée.

Solution