SDR
Sondes et échos
Olivier Lemer
Synchronisation
Algorithme "synchrone" ?
Définitions
Jusqu'ici, tous nos algorithmes étaient asynchrones.
"Chaque processus peut envoyer ou recevoir un message à tout moment."
Il existe aussi des algorithmes synchrones.
"Tous les processus avancent à l'unisson."
Attention : rien à voir avec un système sychrone
Requirements d'un algorithme synchrone
Dans chaque battement, un processus peut
- Faire des calculs en fonction des battements précédents.
- Envoyer jusqu'à un message par voisin, fonction des battements précédents.
- Recevoir jusqu'à un message par voisin, fonction des battements précédents.
Un signal est reçu pour déclencher un nouveau battement.
(pulse)
Un processus est prêt quand tous ses messages ont été reçus.
signal
battement
Requirements d'un algorithme synchrone
Remarques
C'est un ordre partiel : deux événements du même battement n'ont pas d'ordre.
Remarques, donc :
- Tout événement d'un battement k ne dépend que des battements < k.
- Il est possible de n'envoyer aucun message durant un battement.
- Il est impossible d'envoyer plusieurs messages au même voisin durant un même battement.
L'ordre des événements est évident :
E a eu lieu avant F
⇔
Le battement de E est plus ancien que celui de F.
Synchroniseur alpha
Comment synchroniser des processus ?
Deux approches de synchronisation
Décentralisée
Les processus doivent communiquer pour savoir quand ils peuvent déclencher un signal localement.
Centralisée
Un contrôleur est responsable d'envoyer les signaux à tous les processus au bon moment.
Synchronisation décentralisée
Demander un ACK pour chaque message envoyé.
Quand tous mes messages sont acquittés, je suis prêt.
Comment savoir quand je suis prêt ?
(i.e. tous mes messages de ce battement ont été reçus)
Problèmes à résoudre
Comment savoir quand je peux lancer le battement suivant ?
Informer mes voisins quand je suis prêt.
Quand tous mes voisins sont prêts, je peux lancer le battement suivant.
(i.e. le battement actuel est officiellement terminé)
(i.e. j'ai reçu tous les messages qui m'étaient destinés)
Synchronisation décentralisée
Autre problème ?
A
B
C
D
"prêt"
"prêt"
"prêt"
"prêt"
1
1
1
1
Prêt
Synchronisation décentralisée
Autre problème ?
A
B
C
D
"prêt"
"prêt"
1
1
1
1
Prêt
Synchronisation décentralisée
Autre problème ?
A
B
C
D
"Tous mes voisins sont prêts, je passe au suivant."
1
1
1
1
Synchronisation décentralisée
Autre problème ?
A
B
C
D
2
1
1
1
Que doit faire B ?
"uh oh"
Si je ne suis pas encore au battement suivant, je les buffer et les traiterai au moment venu.
msg
Message du battement 2.
msg
Message du battement 1.
Si un processus me dit prêt, tous ses messages suivants appartiendront au prochain battement.
Synchronisation décentralisée
Autre problème ?
A
B
C
D
2
1
1
1
Que doit faire B ?
"uh oh"
Si un processus me dit prêt, tous ses messages suivants appartiendront au prochain battement.
prêt
Battement 2 fini !
msg
Message du battement 1.
Si je ne suis pas encore au battement suivant, je les buffer et les traiterai au moment venu.
Synchroniseur alpha
Résumé et complexités
Début de battement
Je fais mes calculs
Réception d'un ACK
Je note la réception du message
Si j'ai un ACK pour tous mes envois
J'envoie prêt à tous mes voisins
Réception d'un message de i
Si j'ai noté que i est prêt
Je mets le message de coté
J'envoie mes messages
Réception d'un prêt de i
Je note que i est prêt
Je réinitialise tous les statuts "prêt"
Pour tout message mis de coté
Je traite sa réception
Je stocke le message
Sinon
Je réponds ACK
Si mes voisins et moi sommes prêts
Je lance un nouveau battement
Résumé
Si j'ai noté que i est prêt
Je mets le message de coté
Sinon
Besoin d'un numéro de battement sur les messages ?
Non ! Si j'ai reçu un prêt d'un voisin, je sais que ses prochains messages sont du battement suivant.
Communication par battement
Performances, en fonction de T
Séquence de 3 messages par battement, max.
Sur chaque lien, on a un ACK, et un prêt par battement, max.
Donc 2E.
Donc O(E).
Donc O(V^2).
Donc 3T.
Donc O(T).
(en ignorant les messages de l'algorithme synchronisé)
Avec V = nombre de processus ; E = nombre de liens ; T = durée de transit maximale
Complexité
Pas génial...
Synchroniseur beta
Une meilleure complexité...
On élit un leader, qui devient la racine de l'arbre.
On suppose un arbre intégré sur le réseau.
(a.k.a. un "spanning tree")
B
D
E
C
A
F
Changement de structure
B
D
E
C
A
F
On élit un leader, qui devient la racine de l'arbre.
Chaque noeud représente lui et ses enfants.
On suppose un arbre intégré sur le réseau.
(a.k.a. un "spanning tree")
Quand suis-je prêt ?
Tous mes messages et ceux de mes enfants
ont été reçus.
Quand lancer le prochain battement ?
Quand la racine est prête.
(elle représente l'arbre entier ; si elle est prête, tout l'arbre l'est)
Comment lancer le prochain battement ?
La racine envoie le signal à travers l'arbre.
Changement de structure
Synchroniseur beta
Exemple & Remarques
Synchroniseur Beta
Example
A
B
C
D
E
F
G
Début de battement
Message
ACK
prêt
signal
report
Synchroniseur Beta
Remarques
L'arbre ne sert qu'à la logique de l'algorithme. Il peut y avoir d'autres connections utilisées par l'algorithme synchrone lui-même.
Un processus qui n'a pas de messages à envoyer est prêt dès la fin de ses calculs locaux.
Le nouveau battement ne commence pas au même moment partout.
En quoi est-ce mieux qu'un système centralisé ?
C'est un système centralisé !
Mais le "centre" peut changer dynamiquement si besoin.
Il faut alors reconstruire le spanning tree, mais c'est possible.
Synchroniseur Beta
Un algorithme par sondes et échos ?
Réception d'une sonde
Je la propage à mes enfants
Si je n'ai pas d'enfants
Je réponds avec echo
Je fais des calculs (optionnel)
Réception d'un echo
Si j'ai tous les echos
Je fais des calculs (optionnel)
Je réponds echo à mon parent
J'ai fini
Si je suis la source
Lancement d'un battement
(et attente de fin de battement local si je n'ai pas d'enfants)
("signal")
Attente de fin de battement local
("prêt")
Ce synchroniseur utilise une approche par sondes et échos sur arbre !
Synchroniseur beta
Résumé & Complexités
Début de battement
Je fais mes calculs.
Réception d'un ACK
Je note la réception du message.
Si j'ai un ACK pour tous mes envois
Je me note prêt.
Réception d'un signal
Je réinitialise tous les status "prêt".
Réception d'un message de i
Je le mets de coté.
Sinon
J'envoie mes messages.
Tous mes enfants et moi sommes prêts
Si je suis la racine
Sinon
J'envoie prêt à mon parent.
Je fais semblant de recevoir un signal.
Réception d'un prêt de i
Je note que i est prêt.
J'envoie un signal à tous mes enfants.
Je déclenche un nouveau battement.
Résumé
Pour tout message mis de coté
Je traite sa réception.
S'il vient du prochain battement
Je réponds ACK.
Je stocke le message.
Impossible ; j'envois un signal entre tous 2 "prêt"
Pourquoi pas besoin de check si i est prêt ?
Complexité
Les messages et leur ACK, puis la chaine de prêt et du signal.
Sur chaque lien de l'arbre, un ACK, un prêt, et un signal par battement.
Donc 3 fois le nombre de liens dans l'arbre.
Donc 3 fois V-1
Donc O(V).
Donc environ
Donc O(TV), ou O(Tlog(V)) si l'arbre est équilibré.
Avec V = nombre de processus ; E = nombre de liens ; T = durée de transit maximale
2T + 2TV dans le pire des cas
2T + 2Tlog(V) si l'arbre est parfaitement équilibré.
Mieux !
Moins bien...
Communication par battement
Performances, en fonction de T
(en ignorant les messages de l'algorithme synchronisé)
Exercices
Synchroniseurs
Exercice
Sans rien mettre en place, des battements continueraient à l'infini.
Supposons que l'algorithme synchronisé utilisant ces synchroniseurs permette à certains processus de finir avant les autres.
Il se peut même que, après un certain temps, tous les processus aient fini.
Proposez une modification aux deux synchroniseurs permettant à tout processus de terminer avant les autres, et aux battements de s'arrêter une fois que tous ont terminé.
Synchroniseurs
Exercice
Alpha
Ici, on n'a pas le droit de finir tant que nos enfants n'ont pas fini non plus (car il faut garder le contact entre eux et nos parents). Quand on a fini (donc nous-même et nos enfants aussi), on en informe notre parent, qui nous enlève de sa liste d'enfants à gérer, il nous "oublie". Si la racine a fini, le synchroniseur a terminé.
Beta
Quand j'ai terminé, au lieu de dire "je suis prêt", dire "j'ai fini". Dans ce cas, les voisins m'enlèvent de leur liste de voisins à gérer, ils "m'oublient", et continuent sans moi.
Synchroniseur Gamma ?
Le meilleur des deux mondes
FYI
