Transmisión atómica

En la computación distribuida tolerante a fallos , una difusión atómica o difusión de orden total es una difusión en la que todos los procesos correctos en un sistema de múltiples procesos reciben el mismo conjunto de mensajes en el mismo orden; es decir, la misma secuencia de mensajes. ^{[ 1 ] [ 2 ]} La difusión se denomina " atómica " porque, o bien se completa correctamente en todos los participantes, o bien todos los participantes abortan sin efectos secundarios . Las difusiones atómicas son una primitiva importante de la computación distribuida.

Generalmente, se requieren las siguientes propiedades de un protocolo de difusión atómica:

1. Validez: si un participante correcto transmite un mensaje, todos los participantes correctos lo recibirán eventualmente.
2. Acuerdo uniforme: si un participante correcto recibe un mensaje, todos los participantes correctos eventualmente recibirán ese mensaje.
3. Integridad uniforme: cada participante recibe un mensaje como máximo una vez, y solo si se ha transmitido previamente.
4. Orden Total Uniforme: los mensajes están totalmente ordenados en el sentido matemático; es decir, si algún participante correcto recibe primero el mensaje 1 y segundo el mensaje 2, entonces todos los demás participantes correctos deben recibir el mensaje 1 antes que el mensaje 2.

Rodrigues y Raynal ^{[ 3 ]} y Schiper et al. ^{[ 4 ]} definen las propiedades de integridad y validez de la transmisión atómica de manera ligeramente diferente.

Cabe señalar que el orden total no es equivalente al orden FIFO , que exige que si un proceso envió el mensaje 1 antes que el mensaje 2, entonces todos los participantes deben recibir el mensaje 1 antes que el mensaje 2. Tampoco es equivalente al "orden causal", donde si el mensaje 2 "depende de" o "ocurre después" del mensaje 1, entonces todos los participantes deben recibir el mensaje 2 después de recibir el mensaje 1. Si bien es una condición fuerte y útil, el orden total solo exige que todos los participantes reciban los mensajes en el mismo orden, pero no impone otras restricciones a ese orden, como el orden en que se envían los mensajes. ^{[ 5 ]}

Diseñar un algoritmo para transmisiones atómicas es relativamente sencillo si se asume que las computadoras no fallarán. Por ejemplo, si no hay fallas, la transmisión atómica se puede lograr simplemente haciendo que todos los participantes se comuniquen con un "líder" que determine el orden de los mensajes, y los demás participantes sigan a dicho líder.

Sin embargo, las computadoras reales son defectuosas; fallan y se recuperan de fallas en momentos impredecibles, posiblemente inoportunos. Por ejemplo, en el algoritmo de seguimiento del líder, ¿qué sucede si el líder falla en el momento equivocado? En un entorno así, lograr transmisiones atómicas es difícil. ^{[ 1 ]} Se han propuesto varios protocolos para realizar transmisiones atómicas, bajo diversas suposiciones sobre la red, modelos de fallas, disponibilidad de soporte de hardware para multidifusión , etc. ^{[ 2 ]}

Para que se cumplan las condiciones de la difusión atómica, los participantes deben ponerse de acuerdo sobre el orden de recepción de los mensajes. Los participantes que se recuperan de un fallo, después de que los demás hayan acordado un orden y comenzado a recibir los mensajes, deben ser capaces de aprender y cumplir con dicho orden. Estas consideraciones indican que, en sistemas con fallos por caída del sistema, la difusión atómica y el consenso son problemas equivalentes. ^{[ 6 ]}

Un proceso puede proponer un valor para alcanzar el consenso mediante su difusión atómica, y un proceso puede decidir un valor seleccionando el valor del primer mensaje que recibe de forma atómica. Por lo tanto, el consenso se puede reducir a una difusión atómica.

Por el contrario, un grupo de participantes puede transmitir mensajes de forma atómica al alcanzar un consenso sobre el primer mensaje a recibir, seguido de un consenso sobre el siguiente, y así sucesivamente hasta que se hayan recibido todos los mensajes. De este modo, la transmisión atómica se reduce al consenso. Esto fue demostrado de forma más formal y con mayor detalle por Xavier Défago et al. ^{[ 2 ].}

Un resultado fundamental en computación distribuida es que lograr el consenso en sistemas asíncronos, en los que puede ocurrir incluso un solo fallo, es imposible en el caso más general. Esto fue demostrado en 1985 por Michael J. Fischer , Nancy Lynch y Mike Paterson , y a veces se le llama el resultado FLP . ^{[ 7 ]} Dado que el consenso y la difusión atómica son equivalentes, FLP también se aplica a la difusión atómica. ^{[ 5 ]} El resultado FLP no prohíbe la implementación de la difusión atómica en la práctica, pero sí requiere hacer suposiciones menos estrictas que FLP en algunos aspectos, como en lo que respecta a los tiempos del procesador y de la comunicación.

El algoritmo de Chandra-Toueg ^{[ 6 ] es una solución basada en consenso para la difusión atómica. Rodrigues y Raynal [ 3 ]} propusieron otra solución.

El protocolo Zookeeper Atomic Broadcast (ZAB) es el componente básico de Apache ZooKeeper , un servicio de coordinación distribuida tolerante a fallos que sustenta Hadoop y muchos otros sistemas distribuidos importantes. ^{[ 8 ] [ 9 ]}

Ken Birman propuso el modelo de ejecución de sincronización virtual para sistemas distribuidos, cuya idea es que todos los procesos observen los mismos eventos en el mismo orden. Un ordenamiento total de los mensajes recibidos, como en la difusión atómica, es un método (aunque no el único) para lograr la recepción virtualmente síncrona de mensajes.