Algorithme distribué - Distributed algorithm

Un algorithme distribué est un algorithme conçu pour fonctionner sur du matériel informatique construit à partir de processeurs interconnectés . Les algorithmes distribués sont utilisés dans différents domaines d'application de l' informatique distribuée , tels que les télécommunications , l'informatique scientifique , le traitement de l'information distribuée et le contrôle de processus en temps réel . Les problèmes standard résolus par les algorithmes distribués incluent l' élection du leader , le consensus , la recherche distribuée , la génération d' arbre couvrant , l'exclusion mutuelle et l'allocation des ressources .

Les algorithmes distribués sont un sous-type d' algorithme parallèle , généralement exécuté simultanément , avec des parties distinctes de l'algorithme exécutées simultanément sur des processeurs indépendants et disposant d'informations limitées sur ce que font les autres parties de l'algorithme. L'un des défis majeurs dans le développement et la mise en œuvre d'algorithmes distribués est de coordonner avec succès le comportement des parties indépendantes de l'algorithme face aux pannes de processeur et aux liaisons de communication peu fiables. Le choix d'un algorithme distribué approprié pour résoudre un problème donné dépend à la fois des caractéristiques du problème et des caractéristiques du système sur lequel l'algorithme s'exécutera, telles que le type et la probabilité de défaillance du processeur ou de la liaison, le type de communication inter-processus. qui peut être effectuée, et le niveau de synchronisation temporelle entre des processus séparés.

Problèmes standards

Validation atomique
Une validation atomique est une opération dans laquelle un ensemble de modifications distinctes est appliqué en une seule opération. Si le commit atomique réussit, cela signifie que toutes les modifications ont été appliquées. S'il y a un échec avant que la validation atomique ne puisse être terminée, la "validation" est annulée et aucune modification ne sera appliquée.
Les algorithmes de résolution du protocole de validation atomique incluent le protocole de validation en deux phases et le protocole de validation en trois phases .
Consensus
Les algorithmes de consensus tentent de résoudre le problème d'un certain nombre de processus s'accordant sur une décision commune.
Plus précisément, un protocole de consensus doit satisfaire les quatre propriétés formelles ci-dessous.
  • Résiliation : chaque processus correct décide d'une valeur.
  • Validité : si tous les processus proposent la même valeur , alors chaque processus correct décide .
  • Intégrité : chaque processus correct décide au plus une valeur, et s'il décide d'une valeur , alors doit avoir été proposé par un processus.
  • Accord : si un processus correct décide , alors chaque processus correct décide .
Les algorithmes courants pour résoudre le consensus sont l' algorithme Paxos et l' algorithme Raft .
Recherche distribuée
Élection du chef
L'élection du leader est le processus de désignation d'un seul processus comme organisateur d'une tâche répartie entre plusieurs ordinateurs (nœuds). Avant que la tâche ne commence, tous les nœuds du réseau ne savent pas quel nœud servira de « leader » ou de coordinateur de la tâche. Cependant, après l'exécution d'un algorithme d'élection de leader, chaque nœud du réseau reconnaît un nœud particulier et unique en tant que leader de la tâche.
Exclusion mutuelle
Structures de données non bloquantes
Diffusion fiable
La diffusion fiable est une primitive de communication dans les systèmes distribués. Une diffusion fiable est définie par les propriétés suivantes :
  • Validité - si un processus correct envoie un message, un processus correct finira par livrer ce message.
  • Accord - si un processus correct délivre un message, alors tous les processus corrects délivrent finalement ce message.
  • Intégrité - chaque processus correct délivre le même message au plus une fois et seulement si ce message a été envoyé par un processus.
Une diffusion fiable peut avoir un ordre séquentiel, causal ou total.
Réplication
Allocation des ressources
Génération d' arbre couvrant
brisure de symétrie, par exemple coloration du sommet

Les références

Lectures complémentaires

Liens externes