Introduction

• Si a → b, il y a un lien de causalité
• Si a → b et b → c alors a → c
• Dans un ordre chronométrique, il n'y a pas forcément de causalité entre deux évènements successifs

NTP

"Network Time Protocol" → synchronisation d'horloges des machines pour avoir une heure locale fiable. Temps chronométrique discret.

• Précision typique de NTP entre 2 machines connectées à internet : 100ms (c'est le pire cas, exemple : satelite)
• 100µs : réseau local et resynchro fréquente
• Présision kernel de l'ordre de la µs (voir fraction de µs)
• Une horloge peut ralentir, accélérer, mais restera croissante.

NTP garantie sur l'horloge système que :

1. elle est croissante
2. on peut avoir une base de temps locale fiable
3. la précision est obtenue par calcul statistique sur les données de plusieurs serveurs

MARTE

Le modèle de temps de MARTE s’appuie sur les instants.

CCSL : langage permettant d’exprimer les relations entre instants et plus généralement les contraintes d’horloges.

---

Algorithmes de synchronisation

Problèmes de synchronisation typiques :

• se mettre d'accord
• algorithme d'election (choisir un coordinateur)
• algorithme d'exclusion mutuelle (ne pas se mélanger)
• algorithme de gestion de groupe (comment diffuser une requete a tous les membres du groupes)

Classes d'algorithmes

• avec un coordinateur (pas tolérant aux pannes, ne passe pas à l'échelle)
• avec une topologie virtuelle type anneau, arbre, etc.. (moins de communication, plus efficace mais il faut gérer la topologie. Si on perd un processus, on perd la topologie. Il faut prévoir la tolérance aux pannes)
• à base de contention (envoie info celui qui a la meilleur bande passante de vient coordinateur / ou numéro de processus le plus grand / le plus fort gagne / tolérant aux pannes / echange beaucoup de message / totalement distribué)

Algorithme de E. Chang & R. Roberts

Fonctionne sur un système d'élections.
Classe topologique circurlaire.

Chaque processus connait son propre numéro.
Chaque noeud envoie son message à gauche.

message ← noeud ← message

« Si le numéro du message reçu est suppérieur à mon numéro propre, alors je transmet le message à gauche. Sinon j'envoie mon numéro à gauche »

Complexité de temps : 0(n log n)

Algorithme de G. Ricart & A. Agrawala

Fonctionne sur base d'exclusion mutuelle.
Par exemple, si 3 processus veulent une ressource partagée :

étape a :
Ils font une requetes et previennent les autres. Ils numérotes les requetes.
3 envois.

étape b :
2 fait une demande.

étape c :
3 et 1 recoivent la demande de 2. Ils envoie leur accord.
2 recoit l'étape de 3 mais 2 est inferieur à 3. Il ignore donc.

étape d :
1 veut la ressource aussi. Il numérote sa requête 2 car il à déjà recu la requête de 2.

étape e :
échange.

étape f :
2 a finit sa partie. Il relache la ressource.

étape g :
1 recoit l'accusé de reception de 2.
Ils n'ont pas reçu l'accusé de reception de 3.

étape h:
échange.

étape i:
X peut demander son accord à 1.

étape j:
1 recoit les accords et peut entrer en section critique.

Le problème des généraux byzantins

Problème de concensus bien connu : wikipedia

Il s'agir d'un problème de tolérance aux fautes byzantines

Basé sur la métaphore des deux généraux

Les généraux "fiables" arrivent à résoudre le problème et se mettre d'accord malgré la présence de traitres si 2/3 des généraux sont fiables.

Plus précisément 3n+1 pour être tolérant à n pannes.

Algorithme de J. Fischer, A. Lynch et S. Paterson (FLS)

Il s'agit d'un algorithme d'impossibilité.

Un consensus dans un systeme asynchrone ne peut pas être fiable, meme s'il y a seulement un processus.
La présence d'une seule panne est intolérable, qu'importe la nature panne.

Hypothèse qui change par rapport aux systemes synchrones :

• on ne fait aucune hypothese sur la vitesse des processus / messages
• pas d'accès à des horloges synchrones (on ne peut pas utiliser de systèmes basés sur timeout)
• on est incapables de distinguer un processus en panne d'un réseau lent.
• on ne peut pas "se mettre d'accord".

Impossible à distribuer, même s'il y a uniquement un fautif.
En réalité, dans un système asynchrone, on ne peut pas être tolérant, même à une seule panne.

Paxos Made Simple

Réécriture par le biais d'une métaphore simplifiée, car la première version était considérée "trop compliquée à comprendre" par la communauté informatique.

Problèmes de concensus :

• on propose des valeurs,
• seule une valeur doit être choisie,
• si aucune valeur n'est choisie alors rien n'est choisi
• un processus ne sait qu'il y a un choix qu'une fois qu'il est effectif

On ne se force pas à mettre des délais de réponse, il ne garanti pas d'arriver à une solution. Le but est de converger vers une réponse.

Il y a 3 rôles : ceux qui proposent, ceux qui acceptent et ceux qui apprenent (un processus peu jouer les 3 rôles).

Les agents opèrent à une vitesse arbitraire, chaque agent peut tomber en panne et redémarrer (même après le choix de la valeur).

Les messages peuvent être longs à être délivrés, être dupliqués, être perdus mais pas être corrompus (parceque chiffrement).

Cas de la blockchaine :

• se mettre d'accord sur ce qu'on écrit
• beaucoup de copies
• résister à la censure