Sauf avis contraire, les algorithmes présentés dans ce cours s'exécuteront dans un environnement asynchrone; les différents sites coopérant pour l'exécution des algorithmes communiquent uniquement par messages véhiculés par des lignes de communication bidirectionnelles. Ces messages sont délivrés en un temps fini, sans altération ni suppression ni génération spontanée de messages (Toutefois, il existe aussi des algorithmes résistant aux pannes, ce sujet sera évoqué dans le troisième cours).
Les sites connaissent au moins les lignes de communications qui les lient à leurs voisins immédiats. Dans certains cas, on pourra être amené à supposer que les différents sites du réseau ont des identités deux à deux distinctes, et que chaque site connaît les identités de ses voisins immédiats. Le plus souvent, travailler avec des numéros de lignes ou des identités de voisins reviendra au même. Pour certains algorithmes, il pourra être nécessaire de supposer que chaque site a quelques connaissances sur l'ensemble du réseau (par exemple nombre de sites du réseau).
Les différents sites du réseau exécutent chacun un algorithme séquentiel. On écrira donc les algorithmes sous la forme d'ensemble de transitions supposées atomiques du point de vue de l'exécution. Ces transitions comporteront une condition de déclanchement (réception d'un message ou événement interne au site), des actions sur les variables locales au site, et éventuellement des envois de messages vers des voisins. Tout ceci peut être formalisé au moyen de structures d'événements, voir le deuxième cours.
Ces transitions se présenteront donc généralement sous la forme suivante :
Sur réception d'un message m(paramètres) reçus par la ligne de communication n° i (ou venant du voisin d'identité i)
traiter le message m (avec analyse des paramètres éventuels), mettre à jour les variables locales en conséquence
envoyer des messages via certaines lignes de communications reliées au site (ou vers des voisins immédiats dont les identités sont connues)
Le cas échéant, on pourra présenter l'algorithme de chaque site sous forme d'automate à états finis. Il faudra alors, pour chaque transition, préciser l'état de départ et l'état d'arrivée. Ceci peut être pratique pour mettre en évidence les états fondamentaux par lesquels peut passer un site, plutôt que de mémoriser ces informations dans des variables "standard". Exemple : etat "connecté" ou "déconnecté" pour deux sites susceptibles d'échanger de l'information.
Certains algorithmes répartis seront symétriques dans le sens où chaque site participant possède le même algorithme. Dans d'autres cas, un ou plusieurs des sites pourront jouer un ou des rôles particuliers (cf. exemple fondamental ci-dessous). Bien entendu, même dans le premier cas, cela ne signifie pas que tous les sites font exactement la même chose, mais seulement que les transitions possibles sont au départ les mêmes.
Les réseaux sont supposés finis (les nombres de sites et de canaux de communication sont finis) et connexes (toute paire de site peut être reliée par un chemin formé de canaux de communications)
Un des sites du réseau, appelé initiateur, désire envoyer un message à tous les autres. L'objectif fondamental est donc que tous les sites du réseau aient reçu ce message au bout d'un temps fini. Il sera bien entendu préférable que l'algorithme lui-même se termine en un temps fini. Enfin, on pourra en profiter pour obtenir des "sous-produits" de l'algorithme, tel qu'un arbre couvrant le réseau, qui pourra être ultérieurement utilisé pour une autre diffusion de message par exemple.
Il peut s'écrire de la manière suivante :
Initiateur
Envoie le message via chaque ligne de communication à laquelle il est rattaché
Tout site, sur réception du message
mémorise l'information reçue
envoie une copie du message via chaque ligne de communication à laquelle il est rattaché
Il est assez facile de prouver que cet algorithme atteint l'objectif (tout site reçoit le message en un temps fini). Il suffit pour cela de raisonner par récurrence sur la distance d'un site à l'initiateur (longueur en nombre de canaux de communications d'un plus court chemin entre l'initiateur et le site):
L'inconvénient majeur de l'algorithme écrit ci-dessus est qu'il ne s'arrête jamais, et même qu'il génère de plus en plus de messages qui vont saturer le réseau. Il est donc essentiel pour une version opérationnelle de contrôler la diffusion du message afin d'éviter la plupart des messages inutiles et d'assurer la terminaison de l'algorithme. Pour cela, on supposera que chaque site est capable, lorsqu'il reçoit le message, de savoir s'il l'a dèjà reçu ou pas, et de plus on évitera d'envoyer une copie du message au site qui vient de nous l'envoyer :
Initiateur
Envoie le message via chaque ligne de communication à laquelle il est rattaché
Tout site, sur réception du message
S'il n'a pas déjà reçu le message
mémorise l'information reçue
envoie une copie du message via chaque ligne de communication à laquelle il est rattaché, sauf celle par laquelle il vient de le recevoir.
On peut alors prouver que l'algorithme se termine. Considérons en effet le vecteur (n,m), où n est le nombre de sites du réseau n'ayant pas encore reçu le message, et m le nombre de messages envoyés dans le réseau et non encore traités. Au départ (après le lancement de l'algo par l'initiateur), n vaut N-1, où N est le nombre de sites du réseau, et m est égal au nombre de voisins de l'initiateur.
À chaque traitement de message, de deux choses l'une :
Si on considère pour les vecteurs à deux composantes l'ordre lexicographique, on voit que le vecteur (n,m) diminue strictement lors du traitement de chaque événement. Comme la valeur initiale est finie, et que la borne inférieure est (0,0), le processus doit nécessairement être fini, donc l'algorithme s'arrêtera au bout d'un temps fini.
On peut prouver que l'ensemble des sites du réseau, associé aux lignes de communication ayant véhiculé les messages pris en compte par les récepteurs, est un arbre couvrant le réseau. Il peut être intéressant de mémoriser de manière répartie cette structure d'arbre, pour un usage ultérieur. Il est très facile pour chaque site de mémoriser son père (la ligne par laquelle il a reçu le message la première fois), mais il convient d'ajouter des acquittements si on veut mémoriser les fils :
Initiateur
Envoie le message via chaque ligne de communication à laquelle il est rattaché
FIls = {}
Tout site,
sur réception du message via la ligne l
S'il n'a pas déjà reçu le message
mémorise l'information reçue
Père = l; Fils = {}
envoie un acquittement via la ligne l
envoie une copie du message via chaque ligne de communication à laquelle il est rattaché, sauf celle par laquelle il vient de le recevoir.
sur réception d'un acquittement via la ligne l
ajoute à Fils la ligne l
De nombreuses variantes de cet algorithme peuvent être écrites (voir TD : version pdf).
On peut également envisager des versions séquentielles, assimilables à des parcours "en profondeur" du réseau. Le texte ci-dessous présente une version "minimale" de ce parcours.
Tout site,
sur réception du message Explorer via la ligne i
S'il n'a pas déjà reçu le message
mémorise l'information reçue
Père = i: Fils = {} Avisiter = Voisins - {i}
Si Avisiter est non videchoisit x dans Avisiter
retire x de Avisiter
envoie Explorer à xSinon envoie rebrousser(oui) viaPère
Sinon envoie rebrousser(non) via i
sur réception de rebrousser(retour) via la ligne j
Si retour = oui alors ajoute j à Fils
Si Avisiter est non videchoisit x dans Avisiter
retire x de Avisiter
e nvoie Explorer à xSinon envoie rebrousser(oui) viaPère
L'initiateur doit bien entendu lancer l'algorithme en choisissant un voisin pour lui envoyer le premier message. Il sait que l'algorithme est terminé lorsque, à la réception d'un rebrousser, sa variable Avisiter devient vide.
On est ici obligé de mémoriser au moins la variable Père pour pouvoir rebrousser chemin. Si on gère également la variable Fils, comme ci-dessus, alors on mémorise l'arborescence couvrante. De plus on ajoute un paramètre à rebrousser afin de signaler au père qu'on a bien pris son message en compte, ou qu'au contraire on l'avait déjà reçu. On verra en TD une variante évitant les explorations inutiles, au prix d'un paramètre supplémentaire dans les messages.
Par ailleurs, une autre utilité de ces parcours peut être de faire remonter de l'information vers l'initiateur (dans les acquittements, qui sont alors indispensables, et dont la gestion devra être adaptée par rapport à la version ci-dessus)
La complexité d'un algorithme réparti se mesure essentiellement en nombre et taille des messages envoyés. Bien sûr, on peut envisager des algorithmes répartis pour lesquels la complexité de fonctions évaluées sur un ou plusieurs des sites soit importante, par exemple algorithme des plus courts chemins, une fois qu'un site au moins a acquis de la connaissance sur l'ensemble de graphe du réseau, mais en général, les tailles de ces graphes sont assez faibles (on ne fait pas de tels calculs sur l'ensemble de l'Internet !) et les temps d'exécution sont faibles, voire négligeables par rapport au transport des messages.
Par contre, évaluer le nombre de massages nécessaires est souvent difficile, sauf si on se limite à des structures particulières de réseau (par exemple anneau). On pourra dans certains cas évaluer ce nombre au pire ou en moyenne.
La taille des messages sera elle souvent plus facile à évaluer, elle dépend de la nature des paramètres des messages.
Retour au sommaire algorithmique répartie