|
|
Home |
Comme indiqué, dans cette brève introduction à la tolérance aux défaillances par le biais de primitives de communications de groupe, le problème du consensus (encore appelé problème de l'accord distribué) joue un rôle central dans toute la théorie des systèmes distribués asynchrones. En effet, il a été prouvé par Fischer, Lynch et Paterson, que ce problème ne possède pas de solutions déterministes dans un tel système. Le résultat est connu sous l'acronyme de ses auteurs, à savoir FLP. Il devenait dès lors extrêmement intéressant d'essayer d'affiner la frontière existant entre problèmes solubles et problèmes insolubles (à l'instar du consensus) dans les systèmes distribués asynchrones. Ce problème est resté ouvert jusqu'à la publication d'un article de Maurice Herlihy et Nir Shavit.
À la lecture de ce papier, il est facile de comprendre pourquoi les tentatives précédentes était vouée à ne pas réussir. En effet, les auteurs adopte dans cet article une modélisation de l'évolution d'un système distribué complètement différente du modèle standard. Celui-ci hérité de l'article FLP, repose sur l'utilisation de graphes où chaque sommet est un état global du système (c'est-à-dire une collection d'états locaux) et chaque transition représentant une transition d'un des processus particulier du système. De telle sorte que deux sommets adjacents, ne diffèrent que par l'état du processus ayant effectué la transition. Les auteurs adoptent ici un modèle complètement dual. Chaque état global est représenté par un polyèdre de dimension suffisamment grande (un sommet par processus dans système), de telle sorte que la transition entre deux états du graphe à la FLP, est ici représenté par deux polyèdres de même dimension, partageant tous leurs sommets en commun, sauf un, celui codant l'état local du processus qui a effectué la transition.