En la computación distribuida tolerante a fallas , una transmisión atómica o transmisión de orden total es una transmisió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 transmisión se denomina " atómica " porque eventualmente se completa correctamente en todos los participantes, o todos los participantes abortan sin efectos secundarios. Las transmisiones atómicas son una primitiva importante de la computación distribuida.
Propiedades
Las siguientes propiedades generalmente se requieren de un protocolo de transmisión atómica:
- Validez: si un participante correcto emite un mensaje, todos los participantes correctos eventualmente lo recibirán.
- Acuerdo uniforme: si un participante correcto recibe un mensaje, todos los participantes correctos eventualmente recibirán ese mensaje.
- Integridad uniforme: cada participante recibe un mensaje como máximo una vez, y solo si fue transmitido previamente.
- Orden Total Uniforme: los mensajes están totalmente ordenados en el sentido matemático; es decir, si cualquier participante correcto recibe el mensaje 1 primero y el mensaje 2 en segundo lugar, 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 difusión atómica de forma ligeramente diferente.
Tenga en cuenta que el pedido total no es equivalente al pedido FIFO , que requiere que si un proceso envió el mensaje 1 antes de enviar el mensaje 2, todos los participantes deben recibir el mensaje 1 antes de recibir 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 sólida y útil, el orden total solo requiere que todos los participantes reciban los mensajes en el mismo orden, pero no no imponga otras restricciones a ese orden. [5]
Tolerancia a fallos
Diseñar un algoritmo para transmisiones atómicas es relativamente fácil si se puede suponer 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 determina el orden de los mensajes, y los demás participantes siguen al líder.
Sin embargo, las computadoras reales tienen fallas; fallan y se recuperan de fallas en momentos impredecibles, posiblemente inoportunos. Por ejemplo, en el algoritmo de seguimiento del líder, ¿qué pasa si el líder falla en el momento equivocado? En un entorno así, lograr emisiones atómicas es difícil. [1] Se han propuesto varios protocolos para realizar difusión atómica, bajo varios supuestos sobre la red, modelos de falla, disponibilidad de soporte de hardware para multidifusión , etc. [2]
Equivalente al consenso
Para que se cumplan las condiciones para la transmisión atómica, los participantes deben "acordar" efectivamente el orden de recepción de los mensajes. Los participantes que se recuperen de la falla, después de que los otros participantes hayan "acordado" una orden y hayan comenzado a recibir los mensajes, deben poder aprender y cumplir con la orden acordada. Tales consideraciones indican que en sistemas con fallas por colisión, la transmisión atómica y el consenso son problemas equivalentes. [6]
Un proceso puede proponer un valor para el consenso mediante su difusión atómica, y un proceso puede decidir un valor seleccionando el valor del primer mensaje que recibe atómicamente. Por tanto, el consenso puede reducirse a la difusión atómica.
A la inversa, un grupo de participantes puede transmitir mensajes de forma atómica logrando un consenso con respecto al primer mensaje que se recibirá, seguido de un consenso sobre el siguiente mensaje, y así sucesivamente hasta que se hayan recibido todos los mensajes. Por tanto, la difusión atómica se reduce al consenso. Esto fue demostrado de manera más formal y detallada por Xavier Défago, et al. [2]
Un resultado fundamental en la computación distribuida es que lograr un consenso en sistemas asincrónicos en los que incluso puede ocurrir una falla 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 denomina resultado de FLP. [7] Dado que el consenso y la difusión atómica son equivalentes, FLP se aplica también a la difusión atómica. [5] El resultado de FLP no prohíbe la implementación de la transmisión atómica en la práctica, pero requiere hacer suposiciones menos estrictas que FLP en algún aspecto, como sobre los tiempos de procesamiento y comunicación.
Algoritmos
El algoritmo Chandra-Toueg [6] es una solución basada en consenso para la difusión atómica. Rodrigues y Raynal han propuesto otra solución. [3]
El protocolo Zookeeper Atomic Broadcast (ZAB) es el bloque de construcción básico para Apache ZooKeeper , un servicio de coordinación distribuida tolerante a fallas que sustenta Hadoop y muchos otros sistemas distribuidos importantes. [8] [9]
Ken Birman ha propuesto el modelo de ejecución de sincronía virtual para sistemas distribuidos, cuya idea es que todos los procesos observen los mismos eventos en el mismo orden. Un orden total de los mensajes que se reciben, como en la difusión atómica, es uno (aunque no el único) método para lograr una recepción de mensajes prácticamente sincrónica.
Referencias
- ^ a b Kshemkalyani, Ajay; Singhal, Mukesh (2008). Computación distribuida: principios, algoritmos y sistemas (Google eBook) . Prensa de la Universidad de Cambridge. pp. 583 -585. ISBN 9781139470315.
- ^ a b c Défago, Xavier; Schiper, André; Urbán, Péter (2004). "Algoritmos de difusión y multidifusión de orden total" (PDF) . Encuestas de computación ACM . 36 (4): 372–421. doi : 10.1145 / 1041680.1041682 .
- ^ a b Rodrigues L, Raynal M .: Transmisión atómica en sistemas distribuidos asincrónicos de recuperación de fallos [1] , ICDCS '00: Actas de la 20ª Conferencia internacional sobre sistemas informáticos distribuidos (ICDCS 2000)
- ^ Ekwall, R .; Schiper, A. (2006). "Resolución de difusión atómica con consenso indirecto". Conferencia internacional sobre redes y sistemas fiables (DSN'06) (PDF) . págs. 156-165. doi : 10.1109 / dsn.2006.65 . ISBN 0-7695-2607-1.
- ^ a b Dermot Kelly. "Comunicación grupal" .
- ^ a b Chandra, Tushar Deepak; Toueg, Sam (1996). "Detectores de fallos no fiables para sistemas distribuidos fiables". Revista de la ACM . 43 (2): 225–267. doi : 10.1145 / 226643.226647 .
- ^ Michael J. Fischer, Nancy A. Lynch y Michael S. Paterson (1985). "Imposibilidad de consenso distribuido con un proceso defectuoso" (PDF) . Revista de la ACM . 32 (2): 374–382. doi : 10.1145 / 3149.214121 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Flavio P. Junqueira, Benjamin C. Reed y Marco Serafini, Yahoo! Investigación (2011). "Zab: transmisión de alto rendimiento para sistemas de respaldo primario". 2011 41ª Conferencia Internacional IEEE / IFIP sobre redes y sistemas fiables (DSN) . págs. 245-256. doi : 10.1109 / DSN.2011.5958223 . ISBN 978-1-4244-9233-6. S2CID 206611670 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ André Medeiros (20 de marzo de 2012). "Protocolo de transmisión atómica de ZooKeeper: teoría y práctica" (PDF) . Universidad Tecnológica de Helsinki - Laboratorio de Informática Teórica .