Dieser Algorithmus wird verwendet, um die kausale Reihenfolge der Nachrichten aufrechtzuerhalten, dh die Nachricht, die zuerst gesendet wird, sollte zuerst empfangen werden. Wenn send(M1)–>send(M2) dann für alle Prozesse, die die Nachrichten M1 und M2 empfangen, M1 vor M2 erhalten soll.

Merkmale :

  • Broadcast-basiertes Messaging.
  • Größe der Nachrichten sind klein.
  • Mehr nein. der Nachrichten gesendet werden.
  • Begrenzte staatliche Informationen.

Schlüsselpunkte:

  • Jeder Prozess erhöht seinen Vektortakt beim Senden von Nachrichten um 1.
  • Eine Nachricht wird einem Prozess zugestellt, wenn der Prozess alle ihm vorangegangenen Nachrichten empfangen hat.
  • Anderenfalls die Nachricht puffern.
  • Aktualisieren Sie die Vektoruhr für den Prozess.

Bezug :

  • Prozess: P i
  • Ereignis: e ij , wobei i:Prozess die Nummer & j: j. Ereignis im i-ten Prozess ist.
  • T m : Vektorzeitstempel für Nachricht m.
  • C i -Vektortakt, der dem Prozess P i zugeordnet ist ; Das j -te Element ist C i [j] und enthält den letzten Wert von P i für die aktuelle Zeit im Prozess P j

Protokoll:
P i sendet eine Nachricht an P j –

  • P i inkrementiert C i [i] und setzt den Zeitstempel t m = C i [i] für die Nachricht m.

P j empfängt eine Nachricht von P i –

  • Wenn Pj, j !=i, m mit dem Zeitstempel tm empfängt , verzögert es die Zustellung der Nachricht bis beide wie folgt.
    Cj [ i ] = tm[i] – 1; und
für alle k <= n und k != i, Cj[k] <= tm[k].
  • Wenn die Nachricht an P j geliefert wird , aktualisiere die Vektoruhr von P j .
  • Überprüfen Sie den Puffer, um festzustellen, ob er geliefert werden kann.

Beispiel -

  • Der Ausgangszustand für alle Prozesse ist 000.
  • M1 wird von P3 zu P1 und P2 gesendet. e31 aktualisiert die Vektoruhr auf (001) und sendet P1 und P2.
  • P2 akzeptiert die M1 mit dem Zeitstempel (001), weil es beim Vergleich mit seinem anfänglichen Zeitstempel, dh (000), feststellt, dass M1 die erste Nachricht ist, die es empfängt.
  • Nun betrachten wir, bevor M1 P1 erreichen konnte, sendet P2 M2 an P1 und P3 mit Zeitstempel (011).
  • P1 konnte M2 nicht akzeptieren, da beim Vergleichen des Zeitstempels von M2 mit seinem anfänglichen Zeitstempel eine Diskrepanz festgestellt wird, da P1 keine Nachricht mit Zeitstempel (001) früher empfangen hat, sodass M2 im Puffer gespeichert wird.
  • Nun wird M1 von P1 empfangen und akzeptiert.
  • M2 wird aus dem Puffer entfernt und von P1 akzeptiert.
  • M2 wird von P3 akzeptiert, da es keine Diskrepanz im Zeitstempel gibt.