Algorithmique répartie

Un algorithme réparti (ou distribué) est une suite d'instructions et il 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 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 (e.g. début de l'algorithme), des conditions internes (e.g. 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

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

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.