Reloj vectorial

El algoritmo de relojes vectoriales permite establecer un orden parcial a los distintos sucesos o eventos que ocurren en los procesos de un Sistema Distribuido. En este algoritmo, al igual que en el algoritmo de los tiempos lógicos de Lamport, los mensajes entre procesos contienen el estado del reloj lógico del proceso que realiza el envío.

Colin Fidge y Friedemann Mattern, autores del algoritmo de relojes vectoriales.

Un reloj vectorial es un vector de N valores V en un sistema de N procesos. Dichos valores V son los estados de los relojes lógicos de los demás procesos dentro de un Sistema Distribuido. Gracias a que cada proceso cuenta con un reloj vectorial, es posible que cada proceso pueda conocer el estado de los relojes lógicos de los demás procesos. Estos relojes vectoriales se actualizan con cada suceso o evento que ocurre dentro de cada proceso.​

El algoritmo de relojes vectoriales fue desarrollado independientemente por Colin Fidge y Friedemann Mattern en el año 1988.​

Consideraciones

• Cada proceso P_i tiene su propio vector V_i en el que guarda tanto el estado de su reloj lógico como el de los demás procesos.
• Vi[i] es el estado del reloj lógico de P_i
• Vi[j] es la última actualización del estado del reloj lógico de P_j del que tiene constancia P_i
• V=V' si V[i]=V'[i] para i=1, 2, ..., N
• V≤V' si V[i]≤V'[i] para i=1, 2, ..., N
• V<V' si V≤V' y V≠V'​

Importancia para los sistemas distribuidos

Para la existencia y funcionamiento de los sistemas distribuidos es fundamental contar con una manera de garantizar la sincronización de los procesos que los conforman. Para ello se tienen relojes físicos y lógicos; Entre los lógicos se tiene a los relojes vectoriales,​ que son muy importantes para diseñar sistemas distribuidos, ya que permiten identificar más efectivamente la relación de causalidad, que indica qué suceso en un proceso desencadena otro suceso. Otros de los usos de relojes vectoriales son consistencia de archivos, depuración distribuida, exclusión mutua distribuida, recuperación distribuida, implementación de memoria compartida distribuida causal y el seguimiento de ejecución para probar software distribuido.​ Los relojes vectoriales facilitan el manejo de la sincronización de los sistemas distribuidos, ya que permiten tener un registro de la cantidad de eventos o sucesos que han ocurrido en cada proceso. Este registro se puede utilizar para crear algoritmos que condicionen y ordenen la ejecución de los procesos, con el fin de evitar un flujo o ejecución incorrecta de un sistema distribuido. Además este método se puede utilizar en otras áreas que utilicen procesadores, programas o cualquier grupo de entidades que se comuniquen entre sí para llevar a cabo una tarea en común y que necesiten mantener la cantidad de mensajes enviados o recibidos por cada una de ellas, incluyendo su causalidad y concurrencia.

El algoritmo

El algoritmo consta de las siguientes reglas:

1. Inicialmente Vi[j]=0 para j=1, 2, ..., N
2. Antes de que ocurra un suceso en P_i: Vi[i]=Vi[i]+1
3. P_i incluye el estado de su reloj lógico t=V_i en cada mensaje que envía.
4. Cuando P_i tiene un evento de recepción calcula el máximo entre t y la última actualización del estado del reloj lógico del proceso del que recibe dicho mensaje. Es decir, Vi[j]=max(V_i [j],t[j]) para j=1, 2, ..., N. Además, hay que tener en cuenta que Vi[i] se actualiza antes debido a la regla 2.​

Ejemplo

Imagen 1.

En la imagen 1 podemos ver un ejemplo en el que nos encontramos con un sistema con 3 procesos, los cuales son p1, p2 y p3.

Como podemos apreciar en el suceso 'a', el reloj vectorial de p1 tiene 3 valores. El primer valor se corresponde con el estado del reloj lógico del propio proceso, es decir, p1. El segundo valor se corresponde con el de p2, y el tercero con el de p3. El primer valor es un 1, ya que se considera un suceso o evento y se suma 1 al valor inicial que era 0. El segundo y el tercer valor son 0 porque p1 aun no tiene información de los relojes lógicos de los otros procesos, quedando dicho reloj vectorial así (1, 0, 0).

En el suceso 'b' lo que está ocurriendo es el envío del mensaje m1 de p1 a p2, pero antes, el valor correspondiente a p1 en dicho vector se incrementa en 1. En el suceso 'c' , p2 recibe el mensaje m1 de p1, en el cual recibe que el valor del reloj lógico de p1 es 2. Además, incrementa en 1 el valor correspondiente a p2 en dicho vector, quedando este así (2, 1, 0).

Debido a que el reloj vectorial de p1 en el suceso 'a' es menor que el de p2 en el suceso 'd', o sea V_a< V_d, podemos decir que 'a' ocurre antes que 'd', es decir, a->d. Lo mismo ocurre con a->b, a->c y a->f, pero no con la 'e', puesto que ni V_a< V_e ni V_e< V_a, ya que para que un vector sea menor que otro todas sus componentes tienen que ser menores o iguales que las componentes del otro vector, siendo al menos una de estas menor, y por supuesto, teniendo ambos el mismo número de componentes. Al no ser ningún vector menor que otro no podemos asegurar qué suceso ocurre antes, por tanto, cuando esto ocurre se dice que ambos sucesos son concurrentes.

Del mismo modo 'b', 'c' y 'd' también son concurrentes con respecto a 'e'.​

Aplicaciones

Los relojes vectoriales además de permitir establecer un orden parcial a los distintos sucesos o eventos que ocurren en los procesos de un Sistema Distribuido, también son de suma utilidad a la hora de evaluar cortes consistentes en el estado global de un sistema. Hay tareas para las que se necesita conocer el estado global de un sistema, como por ejemplo la detección de objetos distribuidos que ya no se utilizan, un interbloqueo distribuido que ocurre cuando dos procesos esperan un mensaje el uno del otro, o detectar la terminación de un algoritmo distribuido. Para todas estas tareas es vital tener en cuenta el estado de todos los procesos y del canal de comunicación. El estado global de un sistema será consistente si se corresponde con un corte consistente. Un corte es consistente si, para cada suceso que contiene, también contiene todos los sucesos que "sucedieron antes que él", y de no ser así, se denomina corte inconsistente.​

Imagen 2.

En la imagen 2 podemos ver los dos tipos de corte, el corte consistente y el corte inconsistente.

El primero de ellos es inconsistente ya que e⁰₂ se encuentra dentro del corte, pero e¹₁ , que es quien le está enviando el mensaje m1 y por tanto sucede antes que él, está fuera del corte. En cuanto a e⁰₁ , no tiene ningún suceso más antes que él, pero como e¹₁ está fuera del corte y precede a e⁰₂ dicho corte ya es inconsistente.

El segundo corte es consistente ya que e²₂ está dentro del corte, y el suceso que le precede es el e¹₂ , que también está dentro del corte. En cuantoa e²₁ , está dentro del corte, y el suceso que le precede es e¹₁ y también está dentro del corte.

Imagen 3.

Una vez que sabemos lo que son los cortes consistentes, podemos ver la aplicación de los relojes vectoriales en los cortes consistentes. Los relojes vectoriales ayudan a la hora de saber si un corte es consistente o inconsistente, ya que un corte es consistente si, para cada proceso P_i , su reloj lógico en ese momento es mayor o igual que todos los registros del valor del reloj P_i mantenidos por otros procesos.

En la imagen 3 podemos observar el mismo ejemplo anterior, pero ahora usando relojes vectoriales.

El primer corte es inconsistente, ya que el primer elemento del reloj vectorial del suceso X₂=100, es decir, el reloj lógico de P₁ en P₂, es 2, y el último suceso de P₁ que está dentro del corte es el X₁=1 , cuyo reloj vectorial tiene como reloj lógico de P₁ el valor 1. Y por tanto, el reloj lógico de P₁ en P₁ no es mayor o igual que el reloj lógico de P₁ en P₂ , no cumpliéndose así la condición mencionada anteriormente que define si un corte es o no consistente utilizando relojes vectoriales.

El segundo corte del ejemplo es consistente, ya que se cumple tanto que el reloj lógico de P₁ en P₁ [primer elemento del vector del suceso X₁=105 (3, 0) ] sea mayor o igual que el reloj lógico de P₁ en P₂ [primer elemento del vector del suceso X₂=90 (2, 3)] como que el reloj lógico de P₂ en P₂ [segundo elemento del vector del suceso X₂=90 (2, 3) ] sea mayor o igual que el reloj lógico de P₂ en P₁ [segundo elemento del vector del suceso X₁=105 (3, 0) ].​

Comparación con el algoritmo de los tiempos lógicos de Lamport.

El algoritmo de los tiempos lógicos de Lamport es el predecesor de este algoritmo. Leslie Lamport se dio cuenta de que no podemos sincronizar perfectamente 2 relojes físicos y que, por tanto, no podemos usar el tiempo físico para obtener el orden de cualquier par arbitrario de sucesos, y para intentar solventar esto creó el algoritmo de los tiempos lógicos de Lamport, mediante el cual podemos capturar todas las relaciones "sucede antes que". Pero este algoritmo tiene una desventaja, y es que cuando el tiempo del reloj lógico asociado a un suceso 'a' es menor que el tiempo del reloj lógico asociado a un suceso 'b' , es decir, C_i(a) < Cj(b), esto no implica que a->b. Por tanto, aunque C_i(a) < Cj(b), 'a' y 'b' pueden ser concurrentes.​

Imagen 4.

Como podemos apreciar claramente en la imagen 4, aplicando el algoritmo de los tiempos lógicos de Lamport, vemos como el suceso 'e' tiene un valor 1 en su reloj lógico, mientras que el suceso 'b' tiene un valor 2 en su reloj lógico, y a pesar de que el valor del reloj lógico de 'e' es menor, dicho suceso no ocurre antes que 'b'.

El algoritmo de relojes vectoriales solventa esto, pues al contar con un vector en cada suceso, no se compara simplemente un número sino un vector entero el cual se va actualizando con cada mensaje entre procesos, lo cual hace imposible que un suceso 'a' que tenga un vector mayor que otro vector de otro suceso 'b' ocurra antes que 'b'. Por tanto, si tenemos que V_a< V_b entonces a->b.

• Datos: Q65162621