Tiempo y estado global
El tiempo y el estado global se refieren a cómo un sistema distribuido ordena los eventos y razona sobre su condición colectiva cuando no hay un reloj compartido ni una vista global instantánea.
Definition
En un sistema distribuido, los eventos ocurren en procesos separados sin un reloj compartido; el estudio del tiempo y el estado global proporciona las relaciones y algoritmos (relojes lógicos y vectoriales, instantáneas y entrega ordenada) que permiten al sistema ordenar los eventos causalmente y capturar estados globales consistentes.
Scope
Esta área abarca los relojes lógicos y la relación de "sucedió antes" (happened-before), la sincronización de relojes físicos, los relojes vectoriales y la detección de causalidad y concurrencia, la determinación de instantáneas globales consistentes y las garantías de ordenación (FIFO, causal, total) necesarias para la multidifusión fiable. Juntas, estas herramientas permiten que los sistemas distribuidos hagan afirmaciones significativas sobre "cuándo" y "qué estado" a pesar de la ausencia de un reloj global.
Sub-topics
Core questions
- ¿Cómo se pueden ordenar los eventos en diferentes procesos sin un reloj físico compartido?
- ¿Cómo puede un proceso determinar si dos eventos están relacionados causalmente o son concurrentes?
- ¿Cómo se puede registrar una instantánea global consistente mientras la computación continúa?
- ¿Qué garantías de ordenación en la entrega de mensajes se necesitan para preservar la causalidad?
Key theories
- Happened-before y relojes lógicos
- La relación "sucedió antes" (happened-before) de Lamport define un orden causal parcial en los eventos, y los relojes lógicos (escalares) asignan marcas de tiempo consistentes con ella, proporcionando una noción de orden sin reloj suficiente para construir un orden total para muchos protocolos.
- Relojes vectoriales y causalidad
- Los relojes vectoriales extienden los relojes lógicos de modo que la comparación de dos marcas de tiempo captura exactamente si un evento precede causalmente a otro o si los dos son concurrentes, lo que permite un seguimiento preciso de la causalidad.
- Instantáneas globales consistentes
- El algoritmo de instantáneas de Chandy-Lamport registra un estado global consistente (estados de proceso más mensajes en tránsito) sin detener el sistema, propagando marcadores a lo largo de los canales.
Clinical relevance
Los relojes lógicos y vectoriales sustentan la consistencia causal, la detección de conflictos en almacenes replicados y la depuración de ejecuciones distribuidas; las instantáneas consistentes sustentan los puntos de control distribuidos, la detección de interbloqueos y terminaciones, y la recuperación de fallos en el procesamiento de flujos.
History
El artículo de Lamport de 1978 introdujo el tiempo lógico y la relación de "sucedió antes" (happened-before), uno de los resultados más citados en ciencias de la computación; Chandy y Lamport formalizaron las instantáneas globales consistentes en 1985; y Fidge y Mattern desarrollaron independientemente los relojes vectoriales a finales de la década de 1980, completando el conjunto de herramientas fundamentales para razonar sobre el tiempo y el estado.
Key figures
- Leslie Lamport
- K. Mani Chandy
- Colin Fidge
- Friedemann Mattern
Related topics
Seminal works
- lamport1978
- chandy1985
- fidge1988
Frequently asked questions
- ¿Por qué los sistemas distribuidos no pueden simplemente usar relojes físicos sincronizados?
- Los relojes físicos se desvían y no se pueden sincronizar perfectamente a través de una red con retardo variable, por lo que el orden en tiempo real de dos eventos puede ser ambiguo. Los relojes lógicos y vectoriales, en cambio, capturan el orden causal que realmente importa para la corrección.
- ¿Qué hace que una instantánea global sea 'consistente'?
- Una instantánea es consistente si, cada vez que incluye la recepción de un mensaje, también incluye el envío de ese mensaje. Tal estado podría haber ocurrido durante la ejecución, aunque nunca se observó un solo instante globalmente.