ALGOREP : Logical Time

Problem statement

Dans la classe, qui s'est reveille avant qui ?

$1^{ere}$ proposition: on demande l'heure du reveil de tout le monde
Probleme: il faut que tout le monde ait un horloge

On ne peut pas faire l'hypothese qu'on a une horloge pour tout le monde, sinon on est synchrone
Les horloges peuvent avoir des divergences

Quelqu'un peut dire qu'il est debout depuis 5h alors qu'en fait il etait 8h

$2^{eme}$ proposition: On envoie un message des qu'on se leve (ne le fait pas, c'est pas bon pour la sante)
On ne doit pas avoir de delais de transmission du message

Quel evenement a eu lieu avant quel evenement ?

Est-ce qu'on a vraiment besoin de cette info ?

$1^{ere}$ proposition: pour savoir quand est-ce qu'une faute est arrivee et on relance le systeme dans un etat precedent

$\Rightarrow$ c'est une snapshot

On n'a pas de garanti sur le delais des messages

Il faudrait prendre en compte la latence des messages et c'est trop complique

On va utiliser des horloges logiques

On va essayer de construire un systeme ou on date les evenements par rapports a des evenements logique

$\Rightarrow$ les envois de messages

"J'ai vu le message d'Etienne avant de manger ma tartine"

Consider 3 processes

$E$,

$F$ et

$G$

• With some local events:
  $e_1$,
  $f_1$,
  $f_3$,
  $g_2$,
  $g_3$
• With some send events:
  $g_1$,
  $f_2$,
  $e_2$
• With some receive events:
  $e_3$,
  $f_4$,
  $g_4$

Ces 2 executions sont impossibles a distinguer

On va donner une notion de progres

Scalar Time: Lamport Clocks

Definitions

Rule R1
Before executing an event (send, receive, or internal), process pi executes the following

$$C_i:=C_i+d\text{with }d>0\text{, typically 1}$$

Rule R2
Each message piggybacks the clock value of its sender at sending time.

When a process

$p_i$ receives a message with timestamp

$C_{msg}$ , it executes the following actions :

• $C_i:=max(C_i,C_{msg})$
• Execute R1 and deliver message

Example

Remarques

• On peut utiliser l'horloge de Lamport pour l'ordre
  • Il suffit de dire
    $e_1<g_1$
• Si on incremente toujours de
  $1$,
  $h-1$ sera toujours le temps requis pour atteindre le process
  $e_h$
• No Strong Consistency

Problem

The main problem in totally ordering events is that two or more events at different processes may have identical timestamp !

Vector Time: Mattern Clocks

• On va toujours maintenir un compteur
• On va avoir une horloge local par processus
  • On gere comme une horloge de Lamport
• On maintient son horloge et celle de tout le monde

Comment est-ce qu'on peut connaitre l'etat d'un processus ?

En envoyant un message

On echange avec une

$3^e$ personne qui n'a jamais echange avec Etienne
On lui transmet l'avancement d'Etienne
Si cette 3e personne envoie un message a Etienne, elle connaitra son avancee

Pourquoi une personne tierce ?

Si on est que 2, on echange des messages qu'a 2 et on ne peut pas mettre en avant des horloges complexes

En pratique, comment est-ce qu'on fait passer notre compteur local ?

Quand on structure un programme distribue, on incremente l'horloge local a des points stables (barre de progression de chargement, etc.)

Example

On envoie un message a

$G$, on veut savoir s'il l'a recu mais il ghost
Indirectement, on apprend que

$G$ a avance de

$5$ elements donc il est vivant, mais est-ce qu'il a recu le message ?
On sait que

$F$ n'avait pas d'information de notre part au depart
Le

$2$ envoye par

$E$ a

$G$ a ete renvoyee par

$F$, sachant que

$E$ n'a pas envoye de message a

$F$ auparavant
On sait donc que

$F$ a recu le message de

$E$

Remarques

Efficient Implementation of Vector Clocks

Comment on implemente ca de maniere efficace ?

Implementation
On peut garder les

$n$ derniers messages avec nos voisins, on peut juste envoyer le differentiel de la derniere heure envoyer par quelqu'un et l'horloge courante

Problem

Qu'est-ce qu'il se passe si j'ai une inversion de messages ?

Est-ce qu'on est capable de gerer ce cas avec les horloges precedentes ?

Non.

On va utiliser les ragots

$\Rightarrow$ des matrices d'informations

On m'a dit que tu m'as dit que…

$$\left|\begin{array}{ccc}E& F_E& G_E\\ E_F& F& G_F\\ E_G& F_G& G\end{array}\right|$$

La machine qui a le plus de communication serait-elle celle qui a le plus de chance d'etre a jour sur la timeline des processus sur chaque machine ?

Oui.

Virtual Time System

Definition
Virtual time system is an (optimistic) paradigm for organizing and synchronizing distributed systems

• Relies on Time Warp mechanism, i.e. lookahead-rollback mechanism
• When a conflict is discovered, the offending processes are rolled back to the time just before the conflict
• Processes are then executed forward along the revised path

Conclusion

• Different kind of logical time
• Virtual time system (Jefferson) is a paradigm for organizing and synchronizing distributed systems