Lien de la note Hackmd
Problem statement
- No global clock
- No shared memory
- Unpredictable message delay
On est dans un data center, EDF coupe l’electricite $\Rightarrow$ on est mort.
Comment est-ce qu’on backup ?
Etienne nous dit de backup, il y en a un qui est un peu lent. Il y a un crash et on a loupe le backup
On definit un etat stable
Qu’est-ce qu’on fait de l’info entre nous (les messages) ?
Si on definit un etat stable ou rien ne transite, sinon c’est pas un systeme distrib
On doit definir un backup pendant que des messages passent, des apps tournent, etc.
Global state and cuts
Cuts
Definition A cut in a time diagram is a line joining an arbitrary point on each process line that slices the space-time diagram into a PAST and a FUTURE.
Global state
Definition The global state of a distributed system is a collection of the local states of the processes and the channels.
Consistent cut
Qu’est-ce qu’on pense de cette cut ?
Le probleme est qu’il ne faut pas qu’on soit dans des moment ou il y a un envoie et un evenement qui risque de ne pas etre retrouve Elle est mauvaise parce que la coupe se fait avant l’envoie $e_2$ mais aussi après la réception de $g_4$
Consistent Global state
On a des regles:
- Tout envoi a une reception
- Une reception implique que l’envoi est dans l’etat global
Voila une coupure coherente: 
Snapshot for FIFO channels
On veut envoyer un message puis un deuxieme, comment on fait pour que le premier message arrive avant le premier ?
Envoyer un message a tout le monde $\to$ broadcast Arreter ce que font les machines n’est pas une bonne idee On flush les canaux grace a la propriete FIFO avec le broadcast $\to$ plus aucun message en transit
Probleme: le leader envoie un message a tout le monde “fait la snapshot”. Une machine rapide relaie le message a une machine lente qui n’a pas recu le message original, elle va recevoir 2 fois le meme message. Comment on fait ?
On essaie de numeroter de maniere unique les snapshots
Dans un snapshot, on s’en fiche des messages applicatifs.
Prenons l’exemple de $f_3$-$e_4$, a ce moment un message est en transit. Comment on enregistre le message ?
Dans ce cas, seul $F$ peut enregistrer On va stocker dans les messages envoyes depuis notre derniere snapshot
Chandy-Lamport Algorithm : Informal
Correctness
- When a process $j$ receives a message $m_{i,j}$
Complexity
Message complexity $O(e)$ for the record of a single instance of the algorithm, with $e$ the number of edges in the graph
Time Complexity $O(d)$ time with $d$ the diameter of the graph
Remarks
- The recorded global state may not correspond to any of the gloal states that occured during the computation
- The recorded global state may not corresponds to any of the global states that occurred during the computation
- The recorded global state is a valid state in a equivalent execution
Snapshot for non-FIFO channels
On envoie $A$ puis $B$, on suppose qu’on peut recevoir $B$ avant $A$
Lai Yang Algorithm
On est tous initialement d’une couleur (ex: blanc). On se met en rouge si on fait une snapshot et on envoie des messages.
Qu’est-ce qui se passe si on recoit un message rouge ?
Quelqu’un a fait un snapshot et c’est en cours A partir de maintenant j’envoie que des messages rouges
Comment on sait quels etaient les messages en transit ?
Tous les messages blancs Le recepteur va sauvegarder les messages comme etant en transit
On n’est pas capable de:
- Borner les delais d’un message
- Avoir une file de message
Au moment de redemarrer le systeme, on ne renvoit pas de message blanc et on peut les integrer au snapshot directement au lieu de simuler leur reception.
Pour ne pas faire $\color{white}{\text{blanc}}$ $\color{red}{\text{rouge}}$ $\color{white}{\text{blanc}}$, on fait plutot $\color{white}{\text{blanc}}$ $\color{red}{\text{rouge}}$ $\color{purple}{\text{violet}}$ $\color{green}{\text{vert}}$ etc.
Si on recoit des messages blanch en snapshot violet, il y a un probleme dans le systeme. Ce n’est pas grave du moment que la couleur de la derniere snapshot est de la meme couleur pour toutes les machines.
Mattern’s Algorithm
Horloge de Mattern
Comment on fait si on veut manger chez Glados jeudi soir ? 
On envoit un message “A 19h je mange chez Glados” On va faire pareil pour cete algo
On se dit “RDV a un million” pour un snapshot (au plus tard). Avant la reception du message a 1 million, les machines doivent faire leurs snapshots