Pourquoi n'avons-nous pas été en mesure de développer une théorie unifiée de la complexité de l'informatique distribuée?

Le domaine de l'informatique distribuée a été terriblement mis de côté pour développer une seule théorie mathématique décrivant les algorithmes distribués. Il existe plusieurs «modèles» et cadres de calcul distribué qui ne sont tout simplement pas compatibles les uns avec les autres. L’explosion des propriétés temporelles variables (asynchronisme, synchronie, synchronie partielle), diverses primitives de communication (transmission du message par rapport à la mémoire partagée, diffusion par rapport à la monodiffusion), plusieurs modèles de défaillance (échec, reprise après incident, omission par envoi, byzantin, etc.). on) nous a laissé un nombre incalculable de modèles de systèmes, de cadres et de méthodologies, ce qui fait que la comparaison des résultats de solvabilité relative et des limites inférieures entre ces modèles et ces cadres est devenue ardue, insoluble et parfois même impossible.

Ma question est très simple: pourquoi est-ce le cas? En quoi l'informatique distribuée est-elle si fondamentalement différente (de son homologue séquentiel) que nous n'avons pas été en mesure de regrouper les recherches dans une théorie unifiée de l'informatique distribuée? Avec l'informatique séquentielle, les machines de Turing, les fonctions récursives et le calcul lambda sont tous équivalents. S'agissait-il simplement d'un coup de chance ou avons-nous vraiment fait du bon travail en encapsulant l'informatique séquentielle d'une manière qui reste à accomplir avec l'informatique distribuée?

En d'autres termes, l'informatique distribuée est-elle inhérente à une théorie élégante (et si oui, comment et pourquoi?), Ou sommes-nous simplement pas assez intelligents pour découvrir une telle théorie?

La seule référence que je puisse trouver qui aborde ce problème est la suivante: " Évaluation de deux décennies de recherche sur la théorie de l'informatique répartie " par Fischer et Merritt DOI: 10.1007 / s00446-003-0096-6

Toute référence ou exposition serait vraiment utile.

Mon point de vue est que le modèle de calcul de Turing, à la motivation abstraite, était une bonne approximation de la technologie jusqu'à tout récemment, alors que les modèles de calcul distribué, depuis le début, sont motivés par le monde réel, qui est toujours plus compliqué que les abstractions.

De 1940 à 1995, par exemple, la taille des instances à problèmes, la relative "insignifiance" du parallélisme et de la concurrence, ainsi que la macro-échelle des dispositifs informatiques, ont tous "conspiré" pour que les machines de Turing restent une excellente approximation des ordinateurs du monde réel. Cependant, une fois que vous commencez à traiter avec des jeux de données volumineux, un besoin omniprésent de concurrence, la biologie à travers l’optique algorithmique, etc., il est beaucoup moins clair s’il existe un modèle de calcul "intuitif". Peut-être que les problèmes difficiles dans un modèle ne sont pas difficiles - strictement moins complexes en termes de calcul - dans un autre. Je pense donc que la complexité informatique traditionnelle rattrape enfin (!) Le calcul distribué, en commençant à envisager de multiples modèles de calcul et de structures de données, motivés par des considérations concrètes.

Je vais répondre à cela du point de vue des problèmes de graphes classiques (ou des problèmes d’entrée / sortie): nous avons un réseau, chaque nœud reçoit quelque chose en entrée et chaque nœud doit produire quelque chose en sortie. Je suppose que cela se rapproche le plus du monde de la complexité informatique traditionnelle.

Je suis certes partiale, mais je pense que dans ce contexte, il existe un modèle simple et assez répandu d’informatique répartie: les algorithmes distribués synchrones , avec la définition suivante: temps d'exécution = nombre de tours synchrones . Dans la terminologie de Peleg, il s'agit du modèle LOCAL .

Ce modèle est agréable car il comporte très peu de "pièces mobiles", pas de paramètres, etc. Néanmoins, il est très concret: il est logique de dire que le temps d'exécution d'un algorithme est exactement 15 dans ce modèle. Et vous pouvez prouver des limites inférieures inconditionnelles, basées sur la théorie de l'information: de ce point de vue, la complexité répartie de nombreux problèmes de graphes (par exemple, la coloration de graphes) est assez bien comprise.

Ce modèle fournit également une approche unifiée à de nombreux aspects de l'informatique distribuée:

• Transmission de messages par rapport à mémoire partagée, diffusion par rapport à diffusion individuelle: non pertinente dans ce modèle.
• $\alpha$
• Vous souhaitez disposer d'un algorithme pour les réseaux dynamiques ou souhaitez vous remettre en état après une panne? Eh bien, si votre algorithme synchrone est déterministe, vous pouvez l’utiliser pour construire un algorithme auto-stabilisant . Encore une fois, la complexité temporelle n’est essentiellement pas affectée.

Maintenant tout cela va bien tant que vous étudiez des problèmes "véritablement répartis" dans le sens où le temps d'exécution de votre algorithme est inférieur au diamètre du graphe , c'est-à-dire qu'aucun nœud n'a besoin d'avoir une information complète sur la structure de la structure. graphique. Cependant, il existe également de nombreux problèmes intrinsèquement globaux: l'algorithme le plus rapide de ce modèle a une durée d'exécution linéaire dans le diamètre du graphique. Dans l’étude de ces problèmes, le modèle ci-dessus n’a plus aucun sens et nous devons alors recourir à autre chose. En général, on commence à faire attention au nombre total de messages ou de bits communiqués sur le réseau. C'est une des raisons pour lesquelles nous avons plusieurs modèles différents.

Ensuite, nous avons bien sûr le problème suivant: la communauté informatique distribuée est en réalité deux communautés différentes, avec étonnamment peu de points communs . Si vous amalgamer tous les modèles de deux communautés, il va certainement chercher un peu déroutant ... Ma réponse ci - dessus est liée à une seule moitié de la communauté; J'espère que les autres répondront à propos de l'autre moitié.

Une idée romantique permettant de capturer différents modèles d’informatique distribuée a été la topologie algébrique. L'idée centrale est de construire des complexes simpliciaux en laissant les points être des états de processus, chacun étiqueté avec un identifiant de processus. Ceci est une introduction sur le sujet. La réponse la plus proche à votre question a probablement été évoquée par Eli Gafni dans son article intitulé «Informatique répartie»: une lueur de théorie. Dans son article, il montre des simulations montrant comment commencer par la mémoire partagée asynchrone pour deux à trois processeurs (pour les fonctions d'arrêt au rebut et byzantine). Il montre également comment appliquer cela au modèle de transmission de messages. La notion de visualisation topologique d’un calcul distribué est cruciale pour comprendre ses simulations.

Je pense que la situation semble très différente si on la regarde dans son contexte: à partir des premiers travaux et des résultats impossibles sur un accord byzantin ( PSL80 LSP82 FLP85), il est vite apparu que les problèmes fondamentaux de l’informatique distribuée ne peuvent être résolus qu’avec des hypothèses de synchronisme strictes et un degré élevé de redondance. Etant donné que ces limites minimales de ressources théoriques inconditionnelles étaient considérées comme infaisables pour des raisons pratiques, la recherche a été axée sur la mise au point de modèles plus raffinés permettant des compromis toujours plus détaillés entre des hypothèses défauts simultanés de quels types sur quels types de composants tolérés (par exemple, processeurs, liens) afin de donner aux concepteurs du système les outils nécessaires pour trouver le bon compromis pour le système en question.