|
Reloj vectorialEl 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.  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.[1] El algoritmo de relojes vectoriales fue desarrollado independientemente por Colin Fidge y Friedemann Mattern en el año 1988.[2] Consideraciones
Importancia para los sistemas distribuidosPara 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,[2] 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.[3] 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 algoritmoEl algoritmo consta de las siguientes reglas:
Ejemplo 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).
Del mismo modo 'b', 'c' y 'd' también son concurrentes con respecto a 'e'.[1]
AplicacionesLos 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.[4] 
El primero de ellos es inconsistente ya que e02 se encuentra dentro del corte, pero e11 , que es quien le está enviando el mensaje m1 y por tanto sucede antes que él, está fuera del corte. En cuanto a e01 , no tiene ningún suceso más antes que él, pero como e11 está fuera del corte y precede a e02 dicho corte ya es inconsistente. El segundo corte es consistente ya que e22 está dentro del corte, y el suceso que le precede es el e12 , que también está dentro del corte. En cuantoa e21 , está dentro del corte, y el suceso que le precede es e11 y también está dentro del corte.
 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 Pi , su reloj lógico en ese momento es mayor o igual que todos los registros del valor del reloj Pi 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 X2=100, es decir, el reloj lógico de P1 en P2, es 2, y el último suceso de P1 que está dentro del corte es el X1=1 , cuyo reloj vectorial tiene como reloj lógico de P1 el valor 1. Y por tanto, el reloj lógico de P1 en P1 no es mayor o igual que el reloj lógico de P1 en P2 , 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 P1 en P1 [primer elemento del vector del suceso X1=105 (3, 0) ] sea mayor o igual que el reloj lógico de P1 en P2 [primer elemento del vector del suceso X2=90 (2, 3)] como que el reloj lógico de P2 en P2 [segundo elemento del vector del suceso X2=90 (2, 3) ] sea mayor o igual que el reloj lógico de P2 en P1 [segundo elemento del vector del suceso X1=105 (3, 0) ].[4] 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, Ci(a) < Cj(b), esto no implica que a->b. Por tanto, aunque Ci(a) < Cj(b), 'a' y 'b' pueden ser concurrentes.[5]
 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 Va< Vb entonces a->b.
|
