Relojes vectoriales

Sruthi Sree Kumar
Sruthi Sree Kumar

Seguir

17 de mayo de 2020 * 3 minutos de lectura

Al igual que el Reloj de Lamport, el reloj Vectorial también es un reloj lógico, que se utiliza para asignar marcas de tiempo para eventos en un sistema distribuido. Reloj vectorial también da un orden parcial de los eventos. Una de las deficiencias del reloj de Lamport es que no puede identificar eventos concurrentes que estén relacionados causalmente. Aquí, en lugar de usar valores enteros para la marca de tiempo, usamos un vector de valores enteros para representar la marca de tiempo. Si tenemos N procesos en el grupo, entonces cada proceso tendrá un vector con N elementos.

La regla para incrementar la marca de tiempo para el reloj vectorial también es similar al reloj de Lamport con una pequeña adición. Los eventos actualizan la marca de tiempo lógica de acuerdo con las siguientes reglas:

  1. Antes de ejecutar un evento, el proceso i incrementa el i-ésimo elemento de su reloj vectorial por 1
V = V + 1

2. Durante un evento de envío, el proceso i incrementa el i-ésimo elemento de su reloj vectorial en 1 y envía la hora (Vmsg) junto con el mensaje.

V = V + 1

3. Durante un evento de recepción, el proceso i incrementa el i-ésimo elemento de su reloj vectorial en 1. Para todos los demás procesos, toma el máximo del elemento correspondiente en el mensaje entrante y su propio vector local y lo establece como el elemento correspondiente en el reloj local.

V = V + 1V = max(Vmsg, V) for j ≠ i

Podemos usar las marcas de tiempo vectoriales para verificar si dos eventos están relacionados causalmente o concurrentes. Antes de eso, veremos cómo se comparan dos marcas de tiempo vectoriales.

Para dos marcas de tiempo determinadas V1 y V2,

V1 = V2 , iff V1 = V2, for all i = 1 to N (i.e, V1 and V2 are equal if and only if all the corresponding values in their vector matches)V1 ≤ V2 , iff V1 ≤ V2, for all i = 1 to N 

Dos eventos con marcas de tiempo vectoriales V1 y V2 están relacionados causalmente, si

V1 < V2 , iff V1 ≤ V2 & there exists a j such that 1 ≤ j ≤ N & V1 < V2

Dos eventos con marcas de tiempo vectoriales V1 y V2 son concurrentes, iff

NOT (V1 ≤ V2 ) AND NOT (V2 ≤ V1 )

Figura 1: Reloj vectorial

La figura muestra cómo se incrementan los valores de marca de tiempo vectorial para diferentes tipos de eventos. Veamos algunos ejemplos de eventos concurrentes y eventos relacionados causalmente.

Ejemplos de eventos relacionados causalmente:

a – > j as (1,0,0) < (2,2,0)

a – > b as (1,0,0) < (2,0,0)

m – > k as (0,0,2) < (6,3,2)

Ejemplos para eventos concurrentes:

Para los eventos b y l tenemos marcas de tiempo vectoriales (2,0,0) & (0,0,1) respectivamente. Aquí ni b ≤ l ni l ≤ b. Por lo tanto, son eventos simultáneos. De manera similar, d y j son eventos simultáneos.

El reloj vectorial también es un reloj lógico que obedece a la causalidad y asegura el orden parcial de los eventos. En comparación con el reloj de Lamport, puede identificar eventos concurrentes de manera eficiente, ya que el Reloj Vectorial se representa utilizando más espacio.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.