Relojes vectoriales y causalidad

Los relojes vectoriales marcan los eventos con una estampilla de tiempo de tal manera que la comparación de dos estampillas revela exactamente si una precede causalmente a la otra o si las dos son concurrentes.

Definition

Un reloj vectorial asigna a cada evento un vector de contadores, uno por proceso; un evento precede causalmente a otro si y solo si su vector es componente a componente menor o igual que el del otro y estrictamente menor en al menos un componente, y los eventos son concurrentes en caso contrario.

Scope

Este tema abarca el mecanismo del reloj vectorial —un contador por proceso, actualizado en eventos locales y fusionado al recibir mensajes—, el orden parcial que induce y su uso para detectar causalidad y concurrencia. También cubre los vectores de versión, la estructura estrechamente relacionada que se utiliza para detectar actualizaciones conflictivas entre réplicas, y el costo de espacio inherente al seguimiento preciso de la causalidad.

Core questions

• ¿Cómo pueden las estampillas de tiempo capturar la causalidad de forma precisa en lugar de solo consistente?
• ¿Cómo se distinguen los eventos concurrentes (causalmente no relacionados) de los ordenados?
• ¿Cómo detectan los vectores de versión las actualizaciones conflictivas entre réplicas?

Key theories

Caracterización de la causalidad mediante relojes vectoriales

Al mantener un vector de contadores por proceso que se maximiza punto por punto al recibir un mensaje, los relojes vectoriales hacen que el orden componente a componente de las estampillas de tiempo sea exactamente igual a la relación "sucedió antes", por lo que la concurrencia es detectable.

Vectores de versión para la detección de conflictos en réplicas

Los vectores de versión aplican la misma idea a los objetos replicados, permitiendo que las réplicas determinen si una versión domina a otra o si dos versiones entran en conflicto y deben ser reconciliadas.

Relación con los relojes lógicos

Los relojes vectoriales refinan estrictamente los relojes lógicos escalares de Lamport: las estampillas de tiempo escalares solo garantizan que el orden es consistente con la causalidad, mientras que las estampillas de tiempo vectoriales determinan la causalidad exactamente a costa de un espacio O(n) por estampilla de tiempo.

Clinical relevance

Los relojes vectoriales y de versión son el mecanismo estándar para la consistencia causal y la detección de conflictos en almacenes eventualmente consistentes, edición colaborativa y sistemas de clave-valor replicados, donde decidir si dos actualizaciones entran en conflicto es esencial para una reconciliación correcta.

History

Basándose en el tiempo lógico de Lamport, Fidge y Mattern introdujeron de forma independiente los relojes vectoriales en 1988-1989; los vectores de versión, estrechamente relacionados, ya habían aparecido en 1983 para detectar inconsistencias entre réplicas, y las estructuras siguen siendo fundamentales para los sistemas de datos replicados modernos.

Debates

El costo de espacio del seguimiento preciso de la causalidad

Los relojes vectoriales requieren una entrada por proceso, lo que no escala bien en sistemas con muchos participantes o con participantes cambiantes; esto ha impulsado la investigación en compresión, poda y alternativas aproximadas que sacrifican la precisión por la compacidad.

Key figures

• Colin Fidge
• Friedemann Mattern
• Leslie Lamport

Seminal works

• fidge1988
• mattern1989
• parker1983

Frequently asked questions

¿Cómo mejoran los relojes vectoriales a los relojes de Lamport?

Los relojes de Lamport solo garantizan que el orden de las estampillas de tiempo es consistente con la causalidad, por lo que no pueden determinar si dos eventos son concurrentes. Los relojes vectoriales hacen la comparación exacta: se puede leer directamente si un evento ocurrió antes que otro o si son concurrentes.