SDR

Sondes et Échos

Olivier Lemer

L'idée

Programmation par Sondes et Echos

Permettre à un processus donné d'échanger avec tous les autres processus.

Une phase de diffusion propage l'information.

L'idée

Programmation par Sondes et Echos

Permettre à un processus donné d'échanger avec tous les autres processus.

Une phase de diffusion propage l'information.

L'idée

Programmation par Sondes et Echos

Permettre à un processus donné d'échanger avec tous les autres processus.

Une phase de diffusion propage l'information.

L'idée

Programmation par Sondes et Echos

Permettre à un processus donné d'échanger avec tous les autres processus.

Une phase de diffusion propage l'information.

Puis une phase de contraction

renvoie une information à la source.

Puis une phase de contraction

renvoie une information à la source.

L'idée

Programmation par Sondes et Echos

Permettre à un processus donné d'échanger avec tous les autres processus.

Une phase de diffusion propage l'information.

Puis une phase de contraction

renvoie une information à la source.

L'idée

Programmation par Sondes et Echos

Permettre à un processus donné d'échanger avec tous les autres processus.

Une phase de diffusion propage l'information.

Puis une phase de contraction

renvoie une information à la source.

L'idée

Programmation par Sondes et Echos

Permettre à un processus donné d'échanger avec tous les autres processus.

Une phase de diffusion propage l'information.

Puis une phase de contraction

renvoie une information à la source.

L'idée

Définition formelle

et exemples

Sondes et Échos

Un processus source déclenche une requête.

Phase de diffusion

Des sondes sont envoyées aux voisins.

Transmission de requête.

Phase de contraction

Des echos sont renvoyés dans l'autres sens.

Transmission de réponse.

Invariante

Pour chaque processus, au total :

Nombre de sondes envoyées = Nombre d'échos reçus

Exemples

Agrégation d'information

Sondes : "Agrégeons les données distribuées"

Échos : "Voici mes données et celles que j'ai récoltées"

Sychronisation de processus

Sondes : "Faites ce calcul"

Échos : "Voici le résultat"

Partage d'information

Sondes : "Voici de nouveaux identifiants"

Échos : "Bien reçu"

(source demande, noeuds répondent)

(source informe, noeuds acquiescent)

(source orchestre, noeuds calculent puis répondent)

Sémantique des messages

Sonde

"Faites cette chose"

Écho

"Mes enfants et moi avons

fait cette chose"

"Note cette info"

Par exemple

"Donne moi le résultat de cette fonction"

"Commence un nouveau round de calculs et dis-moi quand tu as fini"

"C'est fait"

Par exemple

"Voici le résultat"

"On a fini"

simple ACK

véritable réponse

Cas particulier - L'arbre

Solution sur l'arbre

Source envoie une sonde à ses enfants.

Réception d'une sonde

Solution sur l'arbre

Source envoie une sonde à ses enfants.

Réception d'une sonde

Je la propage à mes enfants

Solution sur l'arbre

Source envoie une sonde à ses enfants.

Réception d'une sonde

Je la propage à mes enfants

Si je n'ai pas d'enfants

Je réponds avec echo

Solution sur l'arbre

Source envoie une sonde à ses enfants.

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)

Solution sur l'arbre

Source envoie une sonde à ses enfants.

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

S'il me manque des echos

Je ne fais rien

Solution sur l'arbre

Source envoie une sonde à ses enfants.

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

S'il me manque des echos

Je ne fais rien

Solution sur l'arbre

Source envoie une sonde à ses enfants.

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

S'il me manque des echos

Je ne fais rien

Solution sur l'arbre

Source envoie une sonde à ses enfants.

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)

Solution sur l'arbre

Source envoie une sonde à ses enfants.

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

Solution sur l'arbre

Source envoie une sonde à ses enfants.

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

Solution sur l'arbre

Source envoie une sonde à ses enfants.

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

Solution sur l'arbre

Source envoie une sonde à ses enfants.

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

Solution sur l'arbre

Source envoie une sonde à ses enfants.

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

"yay"

Solution sur l'arbre

Remarque ?

Très similaire au synchroniseur beta...

Oui, il utilise ce paradigme.

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 si je n'ai pas d'enfants)

Attente de fin de battement

Comportement d'un noeud

Comportement de la source

Demande d'envoi de sonde s

s

s

e

e

Agrégation des échos

Sondage terminé avec écho agrégé.

e

e

Comportement d'un intermédiaire

s

Sonde s reçue

s

s

écho agrégé

e

e

Agrégation des échos

e

e

Comportement d'une "feuille"

s

Agrégation des échos

Sonde s reçue

écho agrégé

(un seul voisin)

(ensemble vide)

Interface

Sondes et échos

Demande de sondage

Bloque jusqu'à retourner l'agrégation des échos reçus

Notification de réception de sonde

Peut retourner une nouvelle sonde à propager

Notification de réception de tous les échos

Retourne un écho agrégeant ceux reçus

Cas particulier - L'arbre

Pseudocode

Pseudocode

Variables

voisins

liste d'entiers

ids de mes processus voisins

parent

entier, init nil

id du processus parent

echos_reçus

liste d'échos

échos reçus

receptionSonde

callback

à appeler à la réception d'une sonde

agrégerEchos

callback

à appeler une fois tous les échos reçus

Pseudocode

Écouter infiniment les événements suivants :

Réception d'une sonde de la part de i

Note : les traitements de ces événements sont faits de manière séquentielle.

Initialisation

Réception d'un écho de la part de i

Demande d'envoi d'une sonde

Note : on suppose aussi pour l'instant aucune sonde concurrente.

Pseudocode

parent = nil

Envoyer s à tous les voisins

echos_reçus = []

Si voisins est vide :

    echo := agrégerEchos(echos_reçus)

    Terminer le sondage avec echo

Demande d'envoi d'une sonde s

parent = i

Envoyer s à tous les voisins sauf i

Exécuter receptionSonde()

echos_reçus = []

Si voisins a une taille de 1 :

    echo := agrégerEchos(echos_reçus)

    Envoyer echo à parent

Réception d'une sonde s de i

Pseudocode

Ajouter e à echos_reçus

Si parent est nil et echos_reçus a la taille de voisins

    echo := agrégerEchos(echos_reçus)

    Terminer le sondage avec echo

Si echos_reçus a la taille de voisins - 1

    echo := agrégerEchos(echos_reçus)

    Envoyer echo à parent

Réception d'un écho e de i

Pseudocode

Cas général - Graphe

Stratégie sur graphe arbitraire

Solution 1

Intégrer un arbre de recouvrement et utiliser l'algorithme précédent.

(a.k.a. spanning tree)

Solution 2

Un algorithme spécialisé.

Problème

Sur une boucle, deux sondes vont inévitablement se croiser.

Que faire ?

Les ignorer...

Problème : on compte les échos reçus.

Ne plus attendre d'écho de ce voisin.

"Si je reçois de ta part une sonde que j'ai déjà,

c'est que tu as reçu une sonde avant la mienne.

Tu es donc déjà l'enfant de quelqu'un, je n'attends plus ton écho."

Problème

Les sondes traitées forment un arbre de recouvrement.

=> Retour à l'algorithme initial.

Remarque :

Source envoie une sonde à ses enfants.

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 attendus

Je fais des calculs (optionnel)

Je réponds echo à mon parent

J'ai fini

Si je suis la source

Si je connais déjà cette sonde

J'arrête d'attendre l'écho de ce voisin.

Sinon

Seuls changements

Solution

Pseudocode

Cas général - Graphe

Variables

voisins

liste d'entiers

ids de mes processus voisins

parent

entier, init nil

id du processus parent

echos_reçus

liste d'échos

échos reçus

echos_attendus

entier

nombre d'échos attendus

Pseudocode

sonde_reçue

bool, init false

si j'ai déjà reçu une sonde

receptionSonde

callback

à appeler à la réception d'une sonde

agrégerEchos

callback

à appeler une fois tous les échos reçus

Pseudocode

parent = nil

Envoyer s à tous les voisins

echos_reçus = []

echos_attendus = taille de voisins

Vérifier nombre d'échos reçus

Demande d'envoi d'une sonde s

Nouveau

Si sonde_reçue

    echos_attendus -= 1

Sinon

    sonde_reçue = true

    parent = i

    echos_reçus = []

    echos_attendus = taille de voisins - 1

    Envoyer s à tous les voisins sauf i

    Executer receptionSonde()

Vérifier nombre d'échos reçus

Réception d'une sonde s de i

Pseudocode

Nouveau

Nouveau

Nouveau

Réception d'un écho e de i

Ajouter e à echos_reçus

Vérifier nombre d'échos reçus

Si echos_reçus a une taille de echos_attendus

    sonde_reçue = false

    echo := agrégerEchos(echos_reçus)

    Si parent est nil

        Terminer le sondage avec echo

    Sinon

        Envoyer echo à parent

Vérification du nombre d'échos reçus

Pseudocode

Avec plusieurs sources

Sur graphe arbitraire

Cas général avec plusieurs sources

Problème

???

Réception de deux sondes différentes.

Que faire ?

Marquer la sonde d'un id globalement unique.

Les traiter indépendamment.

Avec plusieurs sources

Pseudocode

Parenthèse - id globalement unique

Comment générer localement un id globalement unique ?

Générer un id localement unique (e.g. un compteur)

Y préfixer un id globalement unique du processus.

count

"proc_id est la dizaine

 count est l'unité"

proc_id,

Pseudocode

Variables

voisins

liste d'entiers

ids de mes processus voisins

parent

dict d'entiers

id du parent pour chaque id de sonde.

echos_reçus

dict de listes d'échos

échos reçus par id de sonde

echos_attendus

dict d'entiers

nombre d'échos attendus par id de sonde

receptionSonde

callback

à appeler à la réception d'une sonde

agrégerEchos

callback

à appeler une fois tous les échos reçus

sonde_reçue est remplacé par la présence d'une clé dans echos_attendus

Pseudocode

Générer un nouveau s_id

parent[s_id] = nil

Envoyer s à tous les voisins

echos_reçus[s_id] = []

echos_attendus[s_id] = taille de voisins

Vérifier nombre d'échos reçus pour s_id

Demande d'envoi d'une sonde s

Pseudocode

Si s_id est dans echos_attendus

    echos_attendus[s_id] -= 1

Sinon

    echos_attendus[s_id] = taille de voisins - 1

    echos_reçus[s_id] = []

    parent[s_id] = i

    Envoyer s et s_id à tous les voisins sauf i

    Executer receptionSonde(s, s_id)

Vérifier nombre d'échos reçus pour s_id

Réception d'une sonde s avec id s_id de i

Pseudocode

Réception d'un écho e avec id s_id de i

Ajouter e à echos_reçus[s_id]

Vérifier nombre d'échos reçus pour s_id

Si echos_reçus[s_id] a une taille de echos_attendus[s_id]

    Enlever s_id de echos_attendus

    echo := agrégerEchos(echos_reçus[s_id])

    Si parent[s_id] est nil

        Terminer le sondage s_id avec echo

    Sinon

        Envoyer echo avec s_id à parent

Vérification du nombre d'échos reçus pour s_id

Exercices

Exercices

1

Écrire un algorithme qui détermine la topologie d'un réseau garanti comme étant un arbre.

 

Un processus démarre l'algorithme et obtient à la fin un dictionnaire contenant pour chaque processus la liste de ses enfants, si la source était la racine.

 

2

Écrire un algorithme qui détermine un arbre de recouvrement d'un réseau quelconque (donc avec potentiellement des cycles).

 

Un processus démarre l'algorithme, et à la fin de son exécution, chaque processus contient uniquement la liste de ses enfants dans cet arbre de recouvrement. Aucun processus ne connait l'arbre complet.

Corrigés

1

Rien à faire au moment de propager une sonde. En revanche, au moment de retourner un echo, on fait l'union des dictionnaires reçus de la part de tous nos enfants, et on s'y ajoute soi-même (donc une clé avec soi et ses voisins directs) avant de l'envoyer à notre parent.

 

2

Rien à faire au moment de propager une sonde. En revanche, au moment où tous les échos ont été reçus, on stocke comme ses enfants tous les noeuds desquels on a reçu un echo.