Reloj vectorial - Vector clock

Un reloj vectorial es una estructura de datos que se utiliza para determinar el orden parcial de eventos en un sistema distribuido y detectar violaciones de causalidad . Al igual que en las marcas de tiempo de Lamport , los mensajes entre procesos contienen el estado del reloj lógico del proceso de envío . Un reloj vectorial de un sistema de N procesos es una matriz / vector de N relojes lógicos, un reloj por proceso; En cada proceso se guarda una copia local de los "valores posibles más grandes" de la matriz de reloj global.

Denote como el reloj vectorial mantenido por el proceso i, las actualizaciones del reloj proceden de la siguiente manera: ${\ Displaystyle VC_ {i}}$

Ejemplo de un sistema de relojes vectoriales. Los eventos en la región azul son las causas que conducen al evento B4, mientras que los de la región roja son los efectos del evento B4.

• Inicialmente, todos los relojes son cero.
• Cada vez que un proceso experimenta un evento interno, incrementa su propio reloj lógico en el vector en uno. Por ejemplo, ante un evento en el proceso i, se actualiza .${\ Displaystyle VC_ {i} [i] \ leftarrow VC_ {i} [i] +1}$
• Cada vez que un proceso envía un mensaje, incrementa su propio reloj lógico en el vector en uno (como en la viñeta anterior, pero no dos veces para el mismo evento) y luego el mensaje lleva una copia de su propio vector.
• Cada vez que un proceso recibe un mensaje, incrementa su propio reloj lógico en el vector en uno y actualiza cada elemento en su vector tomando el máximo del valor en su propio reloj vectorial y el valor en el vector en el mensaje recibido (por cada elemento). Por ejemplo, si el proceso Pj recibe un mensaje m de Pi, se actualiza estableciendo .${\ Displaystyle VC_ {j} \ leftarrow max (VC_ {j} [k] + 1, VC_ {i} [k]), \ forall k}$

Historia

Sin usar el nombre específico "reloj vectorial", el concepto de reloj vectorial fue mencionado por primera vez en un artículo de 1986 por Rivka Ladin y Barbara Liskov donde usan el término "marca de tiempo de varias partes". Para citar de la página 31 del artículo de Liskov / Ladin:

Resolvemos este problema mediante el uso de marcas de tiempo de varias partes , donde hay una parte para cada réplica. Por lo tanto, si hay n réplicas, una marca de tiempo t es

t = <t1, …, tn>

donde cada parte es un número entero positivo. Dado que normalmente habrá una pequeña cantidad de réplicas (p. Ej., De 3 a 7), es práctico utilizar dicha marca de tiempo.

El término "reloj vectorial" fue utilizado por primera vez de forma independiente por Colin Fidge y Friedemann Mattern en 1988.

Propiedad de pedido parcial

Los relojes vectoriales permiten el ordenamiento causal parcial de los eventos. Definiendo lo siguiente:

• ${\ Displaystyle VC (x)}$denota el reloj vectorial del evento y denota el componente de ese reloj para el proceso .${\ Displaystyle x}$${\ Displaystyle VC (x) _ {z}}$${\ Displaystyle z}$
• ${\ Displaystyle VC (x) <VC (y) \ iff \ forall z [VC (x) _ {z} \ leq VC (y) _ {z}] \ tierra \ existe z '[VC (x) _ { z '} <VC (y) _ {z'}]}$
  • En inglés: es menor que , si y solo si es menor o igual que para todos los índices de proceso , y al menos una de esas relaciones es estrictamente menor (es decir, ).${\ Displaystyle VC (x)}$${\ Displaystyle VC (y)}$${\ Displaystyle VC (x) _ {z}}$${\ Displaystyle VC (y) _ {z}}$${\ Displaystyle z}$${\ Displaystyle VC (x) _ {z '} <VC (y) _ {z'}}$
• ${\ Displaystyle x \ to y \;}$denota que el evento ocurrió antes del evento . Se define como: si , entonces${\ Displaystyle x}$${\ Displaystyle y}$${\ Displaystyle x \ to y \;}$${\ Displaystyle VC (x) <VC (y)}$

Propiedades:

• Antisimetría : si , entonces ¬${\ Displaystyle VC (a) <VC (b)}$${\ Displaystyle (VC (b) <VC (a))}$
• Transitividad : si y , entonces ; o, si y , entonces${\ Displaystyle VC (a) <VC (b)}$${\ Displaystyle VC (b) <VC (c)}$${\ Displaystyle VC (a) <VC (c)}$${\ Displaystyle a \ to b \;}$${\ Displaystyle b \ to c \;}$${\ Displaystyle a \ a c \;}$

Relación con otros pedidos:

• Sea el tiempo real cuando ocurre el evento . Si entonces${\ Displaystyle RT (x)}$${\ Displaystyle x}$${\ Displaystyle VC (a) <VC (b)}$${\ Displaystyle RT (a) <RT (b)}$
• Sea la marca de tiempo de Lamport del evento . Si entonces${\ Displaystyle C (x)}$${\ Displaystyle x}$${\ Displaystyle VC (a) <VC (b)}$${\ Displaystyle C (a) <C (b)}$

Otros mecanismos

• En 1999, Torres-Rojas y Ahamad desarrollaron los relojes plausibles , un mecanismo que ocupa menos espacio que los relojes vectoriales pero que, en algunos casos, ordenará totalmente los eventos que son causalmente concurrentes.

• En 2005, Agargwal y Garg crearon Chain Clocks , un sistema que rastrea las dependencias usando vectores con un tamaño menor que el número de procesos y que se adapta automáticamente a sistemas con un número dinámico de procesos.
• En 2008, Almeida et al. introdujo Interval Tree Clocks . Este mecanismo generaliza los relojes vectoriales y permite operar en entornos dinámicos cuando las identidades y el número de procesos en el cálculo no se conocen de antemano.

• En 2019, Lum Ramabaja desarrolló Bloom Clocks , una estructura de datos probabilística cuya complejidad espacial no depende de la cantidad de nodos en un sistema. Si dos relojes no son comparables, el reloj de floración siempre puede deducirlo, es decir, no son posibles falsos negativos. Si dos relojes son comparables, el reloj de floración puede calcular la confianza de esa declaración, es decir, puede calcular la tasa de falsos positivos entre pares de relojes comparables.

Ver también

• Marcas de tiempo de Lamport
• Relojes de matriz
• Vector de versión

Referencias

enlaces externos

• Por qué los relojes lógicos son fáciles (compara historias causales, relojes vectoriales y vectores de versión)
• Explicación de los relojes vectoriales
• Implementación de reloj vectorial basado en marcas de tiempo en Erlang
• Implementación de reloj vectorial en Objective-C
• Implementación de reloj vectorial en Erlang
• Por qué los relojes vectoriales son difíciles
• Por qué Cassandra no necesita relojes vectoriales