¿Existe una lista de problemas canónicos en sistemas distribuidos?

La semana pasada, estaba leyendo de nuevo el trasncrito de Leslie en Lamport de 1982 de una conferencia que dio sobre Problemas resueltos, Problemas no resueltos y No problemas en concurrencia . El documento es fácilmente legible, pero una de las cosas que me hizo pensar es la siguiente afirmación:

¿Se puede considerar algún problema como un problema de exclusión mutua o un problema de productor-consumidor, o una combinación de ambos?

Me gustaría saber si esta pregunta ha sido respondida para el caso de sistemas distribuidos.

¿Existe un conjunto de problemas de sistemas distribuidos canónicos a partir de los cuales se pueden reducir todos los posibles problemas de sistemas distribuidos? ¿Qué es esta lista canónica?

Si no hay una lista canónica, ¿cuál es la lista actual de problemas y qué reducciones existen?

Por ejemplo, diría muy ingenuamente que los problemas de elección de líderes y exclusión mutua pueden reducirse al problema del consenso. También diría que una instantánea distribuida se puede reducir a un reloj distribuido. ¿Es verdad o está mal?

Si es posible, preferiría que las respuestas proporcionen una referencia a un documento / libro publicado que respalde sus afirmaciones :)

¿Existe un conjunto de problemas de sistemas distribuidos canónicos a partir de los cuales se pueden reducir todos los posibles problemas de sistemas distribuidos?

No estoy al tanto de una lista de problemas publicada.

Ten en cuenta que hay muchos modelos diferentes (y algo incomparables) en computación distribuida, que van desde el modelo síncrono "benigno" (sin fallas) donde los nodos se ejecutan en rondas de paso de bloqueo y todos los mensajes se entregan de manera confiable en cada ronda, hasta El modelo asíncrono donde no hay límites en las velocidades de procesamiento y los retrasos de mensajes y los propios nodos pueden bloquearse o enviar mensajes corruptos. Para agregar aún más a esta variedad, existen otros requisitos y supuestos que son ortogonales a la sincronía y las fallas: el conocimiento inicial de los nodos (tamaño de la red, diámetro de la red, grado máximo de nodo, etc.), la capacidad de consultar detectores de fallas , si los nodos tienen identificadores únicos, la atomicidad de los pasos de envío y recepción, el tamaño máximo de un solo mensaje y muchos más.

$2$

Cuando se observan fallas, por otro lado, las preguntas están más relacionadas con problemas de solvencia como "¿Se puede resolver el consenso en este modelo?" o "¿Podemos implementar este elegante detector de fallas bajo estos supuestos?"

Si no hay una lista canónica, ¿cuál es la lista actual de problemas y qué reducciones existen?

Hay muchos ejemplos de tales reducciones en ciertos modelos de computación distribuida, limitaré mi respuesta a los siguientes 2:

Cálculo local en el modelo síncrono (sin fallas)

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

Modelo asincrónico con fallas de choque

Aquí el problema más estudiado es el consenso tolerante a fallas y sus muchas variaciones, ya que la implementación de primitivas básicas como la transmisión atómica y / o un sincronizador requieren consenso.

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

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

Por ejemplo, diría muy ingenuamente que los problemas de elección de líderes y exclusión mutua pueden reducirse al problema del consenso.

Claro, si puede resolver el consenso, inmediatamente tiene un algoritmo para la elección del líder: simplemente use la ID de cada nodo como entrada para el algoritmo de consenso. La forma opuesta solo se aplica en modelos donde se garantiza que el líder sea finalmente conocido por todos.

[1] Pierre Fraigniaud: Complejidades computacionales distribuidas: ¿eres adicto al volvo o obsesionado con el nascar? PODC 2010. http://doi.acm.org/10.1145/1835698.1835700

[2] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: Computación local: límites inferior y superior. CoRR abs / 1011.5470 (2010) http://arxiv.org/abs/1011.5470

[3] Tushar Deepak Chandra, Sam Toueg: detectores de fallas no confiables para sistemas distribuidos confiables. J. ACM 43 (2): 225-267 (1996). http://doi.acm.org/10.1145/226643.226647

[4] Prasad Jayanti, Sam Toueg: Cada problema tiene un detector de fallas más débil. PODC 2008: 75-84. http://doi.acm.org/10.1145/1400751.1400763

[5] Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg: el detector de fallas más débil para resolver el consenso. J. ACM 43 (4): 685-722 (1996) http://doi.acm.org/10.1145/234533.234549

[6] Michel Raynal: Detectores de fallas para resolver el acuerdo asincrónico de k-set: un vistazo de resultados recientes. Boletín de EATCS 103: 74-95 (2011) http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/61