"Network Time Protocol" → synchronisation d'horloges des machines pour avoir une heure locale fiable. Temps chronométrique discret.
NTP garantie sur l'horloge système que :
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.
Problèmes de synchronisation typiques :
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)
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.
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.
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 :
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.
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 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 :
