# SYD - TD - Lamport Clocks
###### tags: `SYD` `TD`

## Partial Ordering

> **Q1** - What is a partial order ?

[Wikipédia](https://fr.wikipedia.org/wiki/Ensemble_partiellement_ordonn%C3%A9)

Un ordre (ou ordre partiel) est une relation binaire sur un ensemble P qui est réflexive, antisymétrique et transitive. Elle se note ≤.

Les trois axiomes précédents se récrivent:

- $a ≤ a$ (réflexivité).
- Si $a ≤ b$ et $b ≤ a$, alors $a = b$ (anti-symétrie).
- Si $a ≤ b$ et $b ≤ c$, alors $a ≤ c$ (transitivité).

Ce n'est donc pas nécessairement un ordre total.

> **Q2** - Define and explain the relation $\to$

$a \to b$ : C'est possible que $a$ affecte $b$ causalement. On peut aussi dire que $a$ se passe avant $b$. Ces deux éléments ne sont pas concurrents.

> **Q3** - Why is the relation $\to$ an irreflexive partial order ?

## Logical Clocks

> **Q4** - Define a clock $C_i$ for a proces $P_i$

Une horloge $C_i$ attribue à chaque événement un numéro tel que si $a \to b$ alors $C(a) < C(b)$

> **Q5** - Given the clock condition stating yhat for any event $a$, $b$ if $a \to b$ then $C(a) < C(b)$, what are the two necessary conditions for the clock condition to hold, in a multi-process context ?

*Condition 1* : Si $a$ et $b$ sont des événements du même process $P_i$ alors $C_i(a) < C_i(b)$
*Condition 2* : Si $a \in P_i$ envoie un message à $b \in P_j$ alors $C_i(a) < C_j(b)$

En termes visuels, sur un diagramme comme celui de la figure 3, chaque ligne représente un tick de l'horloge. La condition 1 implique que tous les événements d'un même process doivent être séparés d'au moins une ligne. La condition 2 implique que chaque message doit couper au moins une ligne.

> **Q6** - Provide and explain the two clock implementation rules ($\mathbb{R}1$ et $\mathbb{R}2 \{a,b \}$) of the paper. Run such a clock on the example of Figure 3.

$\mathbb{R}1$ : Chaque process $P_i$ incrémente $C_i$ entre deux événements successifs.

$\mathbb{R}2 \{a,b \}$ :
**(a)** Si un événement $a \in P_i$ envoie un message $m$, ce message contient un timestamp $T_m = C_i(a)$
**(b)** A la réception d'un mesage $m$, $P_j$ incrémente $C_j$ de maniére à ce que $C_j$ soit plus grand ou égal à sa valeur actuelle et que $C_j > T_m$

## Ordering the Events Totally

> **Q7** - What is a total order ?

[Wikipédia](https://fr.wikipedia.org/wiki/Ordre_total)

C'est un ensemble partiellement ordonné dans lequel on peut comparer tous les éléments entre eux.
On a alors $x \leqslant y$ ou $y \leqslant x$ pour tout éléments $x$ et $y$ appartenant à cette espace.

> **Q8** - Define the relation $\Rightarrow$ of the paper