Ordenación de Mensajes y Multidifusión
La comunicación en grupo entrega un mensaje a un conjunto de procesos con garantías especificadas de fiabilidad y ordenación, que van desde FIFO hasta el orden total, pasando por el causal.
Definition
La multidifusión entrega un único mensaje a cada miembro de un grupo de procesos; las garantías de ordenación restringen el orden de entrega relativo de los mensajes, con FIFO preservando el orden por remitente, causal preservando el orden de "sucedió antes" (happened-before), y el orden total entregando todos los mensajes en la misma secuencia en cada miembro.
Scope
Este tema cubre la multidifusión fiable y la jerarquía de órdenes de entrega —FIFO, causal y total (atómica)—, sus implementaciones utilizando números de secuencia, relojes lógicos y esquemas de secuenciador o token, y el modelo de sincronía virtual que integra la multidifusión ordenada con cambios consistentes en la membresía del grupo. Se demuestra que la difusión de orden total (atómica) es equivalente en potencia al consenso.
Core questions
- ¿Qué garantías de fiabilidad y ordenación requiere una aplicación de la comunicación en grupo?
- ¿Cómo se implementan eficientemente los órdenes de entrega causal y total?
- ¿Por qué la difusión de orden total es equivalente al consenso?
Key theories
- Jerarquía de ordenación
- Los órdenes de entrega forman una jerarquía —FIFO es más débil que el causal, que a su vez es más débil que el orden total—, cada uno de ellos aplicado mediante metadatos adicionales como números de secuencia por remitente, marcas de tiempo vectoriales o una secuencia acordada globalmente.
- Sincronía virtual
- La sincronía virtual presenta los cambios de membresía del grupo y los mensajes de multidifusión en un orden consistente para todos los miembros, de modo que los procesos ven la misma secuencia de eventos y cambios de vista, simplificando la construcción de servicios replicados.
- La difusión atómica equivale al consenso
- La difusión de orden total (atómica) y el consenso son reducibles entre sí, por lo que cualquier solución para uno produce una solución para el otro y ambos comparten los mismos límites de solubilidad bajo asincronía y fallos.
Clinical relevance
La multidifusión ordenada y fiable es el sustrato de la replicación de máquinas de estado, los sistemas de publicación-suscripción y las bases de datos replicadas, donde cada réplica debe aplicar las mismas actualizaciones en el mismo orden para mantener la coherencia.
History
Birman y Joseph introdujeron la sincronía virtual y la multidifusión ordenada en la década de 1980 a través del sistema ISIS; la relación entre la difusión atómica y el consenso se clarificó en la década de 1990, y la encuesta de Defago, Schiper y Urban de 2004 sistematizó los numerosos algoritmos de orden total.
Key figures
- Kenneth Birman
- Thomas Joseph
- Andre Schiper
- Leslie Lamport
Related topics
Seminal works
- birman1987
- defago2004
- lamport1978
Frequently asked questions
- ¿Cuál es la diferencia entre el orden causal y el orden total?
- El orden causal solo restringe los mensajes que están causalmente relacionados, dejando que los mensajes concurrentes se entreguen en diferentes órdenes en diferentes procesos. El orden total requiere que cada proceso entregue todos los mensajes en la secuencia idéntica, lo cual es estrictamente más fuerte y tan difícil como el consenso.