Este algoritmo se utiliza para mantener el orden causal de los mensajes, es decir, el mensaje que se envía primero debe recibirse primero. Si enviar (M1) -> enviar (M2), entonces para todos los procesos que reciben los mensajes M1 y M2 deben recibir M1 antes que M2.
Características :
- Mensajería basada en difusión.
- El tamaño de los mensajes es pequeño.
- Más No. de mensajes son enviados.
- Información limitada del estado.
Puntos clave :
- Cada proceso aumenta su reloj vectorial en 1 al enviar mensajes.
- El mensaje se entrega a un proceso si el proceso ha recibido todos los mensajes que le preceden.
- De lo contrario, búfer el mensaje.
- Actualice el reloj vectorial para el proceso.
Referencia :
- Proceso: Pi
- Evento: e ij , donde i:proceso es número & j: jésimo evento en iésimo proceso.
- T m : marca de tiempo vectorial para el mensaje m.
- reloj vectorial C i asociado con el proceso P i ; j th elemento es C i [j] y contiene el valor más reciente de P i para el tiempo actual en el proceso P j
Protocolo :
P i enviando un mensaje a P j –
- P i incrementa C i [i] y establece la marca de tiempo t m = C i [i] para el mensaje m.
P j recibiendo un mensaje de P i –
- Cuando P j , j != i, recibe m con sello de tiempo t m , retrasa la entrega del mensaje hasta las dos de la siguiente manera.
Cj[i] = tm[i] - 1; and for all k <= n and k != i, Cj[k] <= tm[k].
- Cuando el mensaje se entrega a P j , actualice el reloj vectorial de P j .
- Verifique el búfer para ver si se puede entregar alguno.
Ejemplo –
- El estado inicial para todos los procesos es 000.
- M1 se transmite desde P3 a P1 y P2. e31 actualiza el reloj vectorial a (001) y envía P1 y P2.
- P2 acepta el M1 con la marca de tiempo (001) porque cuando lo compara con su marca de tiempo inicial, es decir, (000), encuentra que M1 es el primer mensaje que recibe.
- Ahora consideramos que antes de que M1 pudiera llegar a P1, P2 envía M2 a P1 y P3 con sello de tiempo (011).
- P1 no pudo aceptar M2 porque al comparar la marca de tiempo de M2 con su marca de tiempo inicial se encuentra una discrepancia porque P1 no tiene ningún mensaje con marca de tiempo (001) recibido antes, por lo que M2 se almacena en el búfer.
- Ahora M1 es recibido por P1 y aceptado.
- M2 se elimina del búfer y es aceptado por P1.
- M2 es aceptado por P3 ya que no hay discrepancia en la marca de tiempo.
