Modelos de temporización y de fallos

Los modelos de temporización y de fallos especifican lo que un algoritmo distribuido puede asumir sobre los retrasos de los mensajes y las velocidades de los procesadores, y cómo se permite que fallen los componentes.

Definition

Un modelo de temporización fija las suposiciones sobre los límites superiores del tiempo de entrega de mensajes y la velocidad relativa del proceso, mientras que un modelo de fallos fija el conjunto de formas en que los procesos y canales pueden desviarse de su comportamiento especificado.

Scope

Este tema abarca los modelos de temporización síncronos, asíncronos y parcialmente síncronos; la taxonomía de fallos, desde fallos por caída (fail-stop) hasta omisiones y temporización, pasando por fallos arbitrarios (bizantinos); y la abstracción de los detectores de fallos que une los sistemas asíncronos y el razonamiento basado en tiempos de espera (timeout). Estos modelos son los axiomas a partir de los cuales se derivan tanto los resultados de posibilidad como los de imposibilidad.

Core questions

• ¿Qué límites de retardo y velocidad puede asumir un algoritmo, y cómo dependen de ellos los tiempos de espera?
• ¿Qué clases de fallos —por caída, omisión, temporización, bizantinos— debe enmascarar un protocolo?
• ¿Cómo se pueden aumentar los sistemas asíncronos con detectores de fallos para eludir los resultados de imposibilidad?

Key theories

Sincronía parcial

Los sistemas reales no son ni totalmente síncronos ni totalmente asíncronos; el modelo parcialmente síncrono asume límites de retardo y velocidad que se cumplen eventualmente o son desconocidos, lo cual es suficiente para resolver el consenso sin dejar de ser realista.

Jerarquía del modelo de fallos

Los fallos van desde caídas benignas (fail-stop), pasando por omisiones de envío/recepción y violaciones de temporización, hasta comportamientos bizantinos arbitrarios; la gravedad de los fallos que un protocolo debe tolerar determina el factor de replicación y la complejidad de los mensajes requeridos.

Detectores de fallos no fiables

Un detector de fallos abstracto proporciona pistas posiblemente incorrectas sobre qué procesos han fallado; la caracterización del detector más débil suficiente para resolver el consenso concilia el rigor asíncrono con las implementaciones prácticas basadas en tiempos de espera.

Clinical relevance

Los sistemas de producción eligen implícitamente un modelo de temporización y de fallos cada vez que establecen tiempos de espera, seleccionan un factor de replicación o deciden si defenderse de participantes maliciosos; una interpretación errónea de estas suposiciones es una causa común de incidentes de "split-brain" y pérdida de datos.

History

Después de que se demostrara que el modelo asíncrono era demasiado débil para el consenso tolerante a fallos, Dwork, Lynch y Stockmeyer introdujeron la sincronía parcial en 1988, y Chandra y Toueg formalizaron los detectores de fallos no fiables en 1996, proporcionando juntos las herramientas de modelado que hacen posible un acuerdo tolerante a fallos práctico.

Debates

¿Son los tiempos de espera una suposición de temporización o un detector de fallos?

Una perspectiva considera los tiempos de espera como la codificación de un límite de sincronía (eventual); otra los trata como una implementación de un detector de fallos abstracto. Los dos enfoques son en gran medida equivalentes, pero enfatizan diferentes límites de diseño entre el modelo de red y el algoritmo.

Key figures

• Cynthia Dwork
• Nancy Lynch
• Larry Stockmeyer
• Tushar Chandra
• Sam Toueg

Seminal works

• dwork1988
• chandra1996
• lynch1996

Frequently asked questions

¿Por qué no se puede implementar una detección de fallos fiable en un sistema puramente asíncrono?

Sin límites en el retardo de los mensajes, un proceso arbitrariamente lento pero activo es indistinguible de uno que ha fallado, por lo que cualquier detector debe, en ocasiones, ser incorrecto. Por esta razón, los sistemas asíncronos se aumentan con suposiciones de temporización o detectores no fiables.