ModèlesEdit
Plusieurs tâches que nous aimerions automatiser en utilisant un ordinateur sont de type question-réponse : nous souhaitons poser une question et l’ordinateur doit produire une réponse. En informatique théorique, de telles tâches sont appelées des problèmes de calcul. Formellement, un problème de calcul se compose d’instances et d’une solution pour chaque instance. Les instances sont des questions que nous pouvons poser, et les solutions sont des réponses souhaitées à ces questions.
L’informatique théorique cherche à comprendre quels problèmes de calcul peuvent être résolus en utilisant un ordinateur (théorie de la calculabilité) et avec quelle efficacité (théorie de la complexité computationnelle). Traditionnellement, on dit qu’un problème peut être résolu à l’aide d’un ordinateur si nous pouvons concevoir un algorithme qui produit une solution correcte pour toute instance donnée. Un tel algorithme peut être mis en œuvre sous la forme d’un programme informatique fonctionnant sur un ordinateur polyvalent : le programme lit une instance de problème en entrée, effectue un calcul et produit la solution en sortie. Des formalismes tels que les machines à accès aléatoire ou les machines de Turing universelles peuvent être utilisés comme modèles abstraits d’un ordinateur polyvalent séquentiel exécutant un tel algorithme.
Le domaine du calcul concurrent et distribué étudie des questions similaires dans le cas soit de plusieurs ordinateurs, soit d’un ordinateur qui exécute un réseau de processus en interaction : quels problèmes de calcul peuvent être résolus dans un tel réseau et avec quelle efficacité ? Cependant, il n’est pas du tout évident de savoir ce que l’on entend par « résoudre un problème » dans le cas d’un système concurrent ou distribué : par exemple, quelle est la tâche du concepteur d’algorithmes, et quel est l’équivalent concurrent ou distribué d’un ordinateur général séquentiel ?
La discussion ci-dessous se concentre sur le cas de plusieurs ordinateurs, bien que de nombreuses questions soient les mêmes pour les processus concurrents s’exécutant sur un seul ordinateur.
Trois points de vue sont couramment utilisés :
Algorithmes parallèles dans le modèle à mémoire partagée
- Tous les processeurs ont accès à une mémoire partagée. Le concepteur de l’algorithme choisit le programme exécuté par chaque processeur.
- Un modèle théorique est celui des machines à accès aléatoire parallèles (PRAM) qui sont utilisées. Cependant, le modèle classique des PRAM suppose un accès synchrone à la mémoire partagée.
- Les programmes à mémoire partagée peuvent être étendus aux systèmes distribués si le système d’exploitation sous-jacent encapsule la communication entre les nœuds et unifie virtuellement la mémoire sur tous les systèmes individuels.
- Un modèle plus proche du comportement des machines multiprocesseurs du monde réel et qui prend en compte l’utilisation des instructions machine, telles que Compare-and-swap (CAS), est celui de la mémoire partagée asynchrone. Il existe un large corpus de travaux sur ce modèle, dont on peut trouver un résumé dans la littérature.
Algorithmes parallèles en modèle de passage de messages
- Le concepteur de l’algorithme choisit la structure du réseau, ainsi que le programme exécuté par chaque ordinateur.
- On utilise des modèles tels que les circuits booléens et les réseaux de tri. Un circuit booléen peut être vu comme un réseau informatique : chaque porte est un ordinateur qui exécute un programme informatique extrêmement simple. De même, un réseau de tri peut être vu comme un réseau informatique : chaque comparateur est un ordinateur.
Algorithmes distribués dans le modèle de passage de messages
- Le concepteur de l’algorithme ne choisit que le programme informatique. Tous les ordinateurs exécutent le même programme. Le système doit fonctionner correctement quelle que soit la structure du réseau.
- Un modèle couramment utilisé est un graphe avec une machine à états finis par nœud.
Dans le cas des algorithmes distribués, les problèmes de calcul sont généralement liés à des graphes. Souvent, le graphe qui décrit la structure du réseau informatique est l’instance du problème. Ceci est illustré dans l’exemple suivant.
Un exempleEdit
Considérons le problème de calcul consistant à trouver une coloration d’un graphe G donné. Différents domaines pourraient adopter les approches suivantes:
Algorithmes centralisés
- Le graphe G est codé comme une chaîne de caractères, et la chaîne est donnée en entrée à un ordinateur. Le programme informatique trouve une coloration du graphe, code la coloration comme une chaîne de caractères, et sort le résultat.
Algorithmes parallèles
- A nouveau, le graphe G est codé comme une chaîne de caractères. Cependant, plusieurs ordinateurs peuvent accéder à la même chaîne en parallèle. Chaque ordinateur pourrait se concentrer sur une partie du graphe et produire une coloration pour cette partie.
- L’objectif principal est le calcul haute performance qui exploite la puissance de traitement de plusieurs ordinateurs en parallèle.
Algorithmes distribués
- Le graphe G est la structure du réseau informatique. Il y a un ordinateur pour chaque nœud de G et un lien de communication pour chaque arête de G. Initialement, chaque ordinateur ne connaît que ses voisins immédiats dans le graphe G ; les ordinateurs doivent échanger des messages entre eux pour en découvrir davantage sur la structure de G. Chaque ordinateur doit produire sa propre couleur en sortie.
- L’objectif principal est de coordonner le fonctionnement d’un système distribué arbitraire.
Bien que le domaine des algorithmes parallèles ait un objectif différent de celui des algorithmes distribués, il y a beaucoup d’interaction entre les deux domaines. Par exemple, l’algorithme de Cole-Vishkin pour la coloration des graphes a été présenté à l’origine comme un algorithme parallèle, mais la même technique peut aussi être utilisée directement comme un algorithme distribué.
De plus, un algorithme parallèle peut être implémenté soit dans un système parallèle (en utilisant la mémoire partagée), soit dans un système distribué (en utilisant le passage de messages). La frontière traditionnelle entre les algorithmes parallèles et les algorithmes distribués (choisir un réseau approprié vs exécuter dans n’importe quel réseau donné) ne se situe pas au même endroit que la frontière entre les systèmes parallèles et les systèmes distribués (mémoire partagée vs passage de messages).
Mesures de complexitéModification
Dans les algorithmes parallèles, encore une autre ressource en plus du temps et de l’espace est le nombre d’ordinateurs. En effet, il existe souvent un compromis entre le temps d’exécution et le nombre d’ordinateurs : le problème peut être résolu plus rapidement s’il y a plus d’ordinateurs fonctionnant en parallèle (voir speedup). Si un problème de décision peut être résolu en temps polylogarithmique en utilisant un nombre polynomial de processeurs, alors le problème est dit être dans la classe NC. La classe NC peut être définie aussi bien en utilisant le formalisme PRAM ou les circuits booléens – les machines PRAM peuvent simuler efficacement les circuits booléens et vice versa.
Dans l’analyse des algorithmes distribués, on accorde généralement plus d’attention aux opérations de communication qu’aux étapes de calcul. Le modèle le plus simple de l’informatique distribuée est peut-être un système synchrone où tous les nœuds fonctionnent de manière lockstep. Ce modèle est communément appelé le modèle LOCAL. Pendant chaque cycle de communication, tous les nœuds en parallèle (1) reçoivent les derniers messages de leurs voisins, (2) effectuent un calcul local arbitraire et (3) envoient de nouveaux messages à leurs voisins. Dans de tels systèmes, une mesure de complexité centrale est le nombre de tours de communication synchrone nécessaires pour accomplir la tâche.
Cette mesure de complexité est étroitement liée au diamètre du réseau. Soit D le diamètre du réseau. D’une part, tout problème calculable peut être résolu de manière triviale dans un système distribué synchrone en approximativement 2D tours de communication : il suffit de rassembler toutes les informations à un endroit (D tours), de résoudre le problème et d’informer chaque nœud de la solution (D tours).
D’autre part, si le temps d’exécution de l’algorithme est beaucoup plus petit que D tours de communication, alors les nœuds du réseau doivent produire leur sortie sans avoir la possibilité d’obtenir des informations sur les parties distantes du réseau. En d’autres termes, les nœuds doivent prendre des décisions globalement cohérentes sur la base des informations disponibles dans leur D-voisinage local. On connaît de nombreux algorithmes distribués dont le temps d’exécution est bien inférieur à D tours, et comprendre quels problèmes peuvent être résolus par de tels algorithmes est l’une des principales questions de recherche dans ce domaine. Typiquement, un algorithme qui résout un problème en temps polylogarithmique de la taille du réseau est considéré comme efficace dans ce modèle.
Une autre mesure couramment utilisée est le nombre total de bits transmis dans le réseau (cf. complexité de communication). Les caractéristiques de ce concept sont typiquement capturées avec le modèle CONGEST(B), qui est défini de manière similaire au modèle LOCAL mais où les messages uniques ne peuvent contenir que B bits.
Autres problèmesEdit
Les problèmes de calcul traditionnels prennent la perspective que l’utilisateur pose une question, un ordinateur (ou un système distribué) traite la question, puis produit une réponse et s’arrête. Cependant, il existe également des problèmes où le système est tenu de ne pas s’arrêter, notamment le problème des philosophes à manger et d’autres problèmes d’exclusion mutuelle similaires. Dans ces problèmes, le système distribué est censé coordonner en permanence l’utilisation des ressources partagées afin qu’aucun conflit ou impasse ne se produise.
Il existe également des défis fondamentaux propres au calcul distribué, par exemple ceux liés à la tolérance aux pannes. Parmi les exemples de problèmes connexes, citons les problèmes de consensus, la tolérance aux pannes byzantine et l’auto-stabilisation.
De nombreuses recherches sont également axées sur la compréhension de la nature asynchrone des systèmes distribués :
- Des synchroniseurs peuvent être utilisés pour exécuter des algorithmes synchrones dans des systèmes asynchrones.
- Les horloges logiques fournissent un ordonnancement causal happened-before des événements.
- Les algorithmes de synchronisation des horloges fournissent des horodatages physiques globalement cohérents.
Édition de l’élection
L’élection du coordonnateur (ou élection du leader) est le processus de désignation d’un seul processus comme organisateur d’une certaine tâche distribuée entre plusieurs ordinateurs (nœuds). Avant le début de la tâche, tous les nœuds du réseau ignorent quel nœud servira de « coordinateur » (ou leader) de la tâche, ou sont incapables de communiquer avec le coordinateur actuel. Cependant, après l’exécution d’un algorithme d’élection du coordinateur, chaque nœud dans l’ensemble du réseau reconnaît un nœud particulier et unique comme le coordinateur de la tâche.
Les nœuds du réseau communiquent entre eux afin de décider lequel d’entre eux se mettra dans l’état de « coordinateur ». Pour cela, ils ont besoin d’une méthode afin de briser la symétrie entre eux. Par exemple, si chaque nœud a des identités uniques et comparables, alors les nœuds peuvent comparer leurs identités, et décider que le nœud avec l’identité la plus élevée est le coordinateur.
La définition de ce problème est souvent attribuée à LeLann, qui l’a formalisé comme une méthode pour créer un nouveau jeton dans un réseau en anneau à jetons dans lequel le jeton a été perdu.
Les algorithmes d’élection du coordinateur sont conçus pour être économiques en termes d’octets totaux transmis, et de temps. L’algorithme suggéré par Gallager, Humblet et Spira pour les graphes généraux non dirigés a eu un fort impact sur la conception des algorithmes distribués en général, et a remporté le prix Dijkstra pour un article influent en informatique distribuée.
De nombreux autres algorithmes ont été suggérés pour différents types de graphes de réseau, tels que les anneaux non dirigés, les anneaux unidirectionnels, les graphes complets, les grilles, les graphes d’Euler dirigés, et autres. Une méthode générale qui découple la question de la famille de graphes de la conception de l’algorithme d’élection du coordinateur a été suggérée par Korach, Kutten et Moran.
Afin d’effectuer la coordination, les systèmes distribués emploient le concept de coordinateurs. Le problème de l’élection du coordinateur consiste à choisir un processus parmi un groupe de processus sur différents processeurs dans un système distribué pour agir en tant que coordinateur central. Plusieurs algorithmes d’élection du coordinateur central existent.
Propriétés des systèmes distribuésModifier
Jusqu’à présent, l’accent a été mis sur la conception d’un système distribué qui résout un problème donné. Un problème de recherche complémentaire est l’étude des propriétés d’un système distribué donné.
Le problème de halte est un exemple analogue issu du domaine du calcul centralisé : on nous donne un programme informatique et la tâche est de décider s’il s’arrête ou s’exécute éternellement. Le problème de l’arrêt est indécidable dans le cas général, et naturellement, comprendre le comportement d’un réseau informatique est au moins aussi difficile que de comprendre le comportement d’un seul ordinateur.
Cependant, il existe de nombreux cas particuliers intéressants qui sont décidables. En particulier, il est possible de raisonner sur le comportement d’un réseau de machines à états finis. Un exemple est de dire si un réseau donné de machines à états finis en interaction (asynchrone et non déterministe) peut atteindre une impasse. Ce problème est PSPACE-complet, c’est-à-dire qu’il est décidable, mais il est peu probable qu’il existe un algorithme efficace (centralisé, parallèle ou distribué) qui résout le problème dans le cas de grands réseaux.