Existe-t-il une liste de problèmes canoniques dans les systèmes distribués?

La semaine dernière, je lisais à nouveau le transcript de Leslie's Lamport en 1982 d'une conférence qu'il a donnée sur les problèmes résolus, les problèmes non résolus et les non-problèmes dans la concurrence . Le document est facilement lisible, mais l'une des choses qui m'a fait réfléchir est l'affirmation suivante:

Un problème peut-il être considéré comme un problème d'exclusion mutuelle ou un problème producteur-consommateur, ou une combinaison des deux?

Je voudrais savoir si cette question a été répondue pour le cas des systèmes distribués.

Existe-t-il un ensemble de problèmes de systèmes distribués canoniques à partir desquels tous les problèmes de systèmes distribués possibles peuvent être réduits? Quelle est cette liste canonique?

S'il n'y a pas de liste canonique, quelle est la liste actuelle des problèmes et quelles réductions existent?

Par exemple, je dirais très naïvement que les problèmes d'élection des dirigeants et d'exclusion mutuelle peuvent être réduits au problème du consensus. Je dirais également qu'un instantané distribué peut être réduit à une horloge distribuée. C'est vrai ou tout simplement faux?

Si possible, je préférerais que les réponses fassent référence à un document / livre publié étayant ses affirmations :)

Existe-t-il un ensemble de problèmes de systèmes distribués canoniques à partir desquels tous les problèmes de systèmes distribués possibles peuvent être réduits?

Je ne suis pas au courant d'une telle liste publiée de problèmes.

Gardez à l'esprit qu'il existe de nombreux modèles différents (et quelque peu incomparables) dans l'informatique distribuée, allant du modèle synchrone "bénin" (sans défaut) où les nœuds s'exécutent en étapes de verrouillage et tous les messages sont délivrés de manière fiable à chaque ronde, à le modèle asynchrone où il n'y a pas de limites sur les vitesses de traitement et les retards de message et les nœuds eux-mêmes peuvent planter ou envoyer des messages corrompus. Pour ajouter à cette variété, il existe d'autres exigences et hypothèses orthogonales à la synchronisation et aux défauts: la connaissance initiale des nœuds (taille du réseau, diamètre du réseau, degré maximal du nœud, etc.), la possibilité d'interroger un détecteur de défaillance , si les nœuds ont des identifiants uniques, l'atomicité des étapes d'envoi et de réception, la taille maximale d'un seul message, et bien d'autres.

$2$

En revanche, lorsque l'on examine les échecs, les questions sont davantage liées à des problèmes de solvabilité tels que "Le consensus est-il résoluble dans ce modèle?" ou "Pouvons-nous implémenter ce détecteur de défaillance sophistiqué sous ces hypothèses?"

S'il n'y a pas de liste canonique, quelle est la liste actuelle des problèmes et quelles réductions existent?

Il existe de nombreux exemples de telles réductions dans certains modèles informatiques distribués, je limiterai ma réponse aux 2 suivants:

Calcul local dans le modèle synchrone (sans défaut)

$\Omega(\sqrt{\log n} + \log\Delta)$$n$$\Delta$$2$$A$$A$

Modèle asynchrone avec échecs de plantage

Ici, le problème le plus étudié est le consensus tolérant aux pannes et ses nombreuses variantes, car la mise en œuvre de primitives de base comme la diffusion atomique et / ou un synchroniseur eux-mêmes nécessitent un consensus.

$S$ $P$$T$$P$$S$

$P$$Q$$P$$Q$$k$

Par exemple, je dirais très naïvement que les problèmes d'élection des dirigeants et d'exclusion mutuelle peuvent être réduits au problème du consensus.

Bien sûr, si vous pouvez résoudre le consensus, vous disposez immédiatement d'un algorithme pour l'élection du leader: utilisez simplement l'ID de chaque nœud comme entrée pour l'algorithme de consensus. L'inverse ne vaut que pour les modèles où il est garanti que le leader sera finalement connu de tous.

[1] Pierre Fraigniaud: Complexité informatique distribuée: êtes-vous dépendant du volvo ou obsédé par le nascar? PODC 2010. http://doi.acm.org/10.1145/1835698.1835700

[2] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: Calcul local: limites inférieure et supérieure. CoRR abs / 1011.5470 (2010) http://arxiv.org/abs/1011.5470

[3] Tushar Deepak Chandra, Sam Toueg: Détecteurs de défaillance non fiables pour des systèmes distribués fiables. J. ACM 43 (2): 225-267 (1996). http://doi.acm.org/10.1145/226643.226647

[4] Prasad Jayanti, Sam Toueg: Chaque problème a un détecteur de défaillance le plus faible. PODC 2008: 75-84. http://doi.acm.org/10.1145/1400751.1400763

[5] Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg: le détecteur de défaillance le plus faible pour résoudre le consensus. J. ACM 43 (4): 685-722 (1996) http://doi.acm.org/10.1145/234533.234549

[6] Michel Raynal: Détecteurs de défaillance pour résoudre l'accord k-set asynchrone: un aperçu des résultats récents. Bulletin de l'EATCS 103: 74-95 (2011) http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/61