Algorithmique répartie

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un algorithme réparti (ou distribué) est généralement un algorithme parallèle (mais pas toujours, exemple, une communication téléphonique) réparti sur plusieurs sites. Chaque site calcule (i.e. produit de nouveaux résultats) et communique (i.e. échange des données avec d'autres sites). Un algorithme réparti décrit le fonctionnement d'un système informatique composé de plusieurs unités de calcul reliées par un réseau de communication, tels que par exemple les routeurs dans Internet.

L'algorithme d'un site isolé est appelé algorithme local. Il correspond le plus souvent à un algorithme séquentiel classique exprimé à la manière de la programmation événementielle : le site réagit à des actions externes (eg. début de l'algorithme), des conditions internes (eg. le site a atteint un état particulier) ou à l'arrivée d'un message. L'ensemble des algorithmes locaux constitue un algorithme réparti, aussi appelé protocole. Lorsque tous les algorithmes locaux sont identiques, l'algorithme est dit uniforme.

Structures de données réparties[modifier | modifier le code]

Dans l'Algorithme de Naimi-Trehel, par exemple, on trouve une arborescence répartie et une file d'attente répartie. Pour l'arborescence, ça signifie que chaque site ne connaît que son père dans l'arborescence, sauf, bien sûr, la racine. Pour la file, chaque site ne connaît que son suivant, sauf, bien sûr, la queue.

Autostabilisation[modifier | modifier le code]

Article détaillé : Autostabilisation.

Un algorithme réparti est autostabilisant si, après une défaillance transitoire qui modifie arbitrairement l'état du système, il revient de lui-même à un fonctionnement correct.

Bibliographie[modifier | modifier le code]

Notes et références[modifier | modifier le code]