dr inż. Arkadiusz Danilecki
W oparciu o wykłady prof. J. Brzezińskiego
Nieformalnie, rozgłaszanie to mechanizm komunikacyjny, za pomocą którego proces może wysłać wiadomość do grupy procesów. Mechanizmy rozgłaszania niezawodnego gwarantują pewne własności, pomimo występowania awarii. Gwarancje te tyczą się przede wszystkim zapewnienia dostarczenia wiadomości do adresatów, identyczności zbioru wiadomości dostarczanych do wszystkich procesów poprawnych, oraz kolejności dostarczanych wiadomości.
MECHANIZM - abstrakcyjna specyfikacja czego chcemy; zbiór własności, które muszą być zagwarantowane procesom korzystającym z mechanizmu.
ALGORYTM - realizuje mechanizm, zapewniając wszystkie gwarancje/własności wyszczególnione w mechanizmie.
WAŻNOŚĆ - jeżeli procesy $\displaystyle P_{i}$ oraz $\displaystyle P_{j}$ są poprawne, to każda wiadomość rozgłaszana przez $\displaystyle P_{i}$ jest ostatecznie dostarczona do $\displaystyle P_{j}$.
BRAK POWIELANIA - jeżeli wiadomość jest dostarczona, to jest dostarczona co najwyżej raz.
BRAK SAMOGENERACJI - jeżeli wiadomość jest dostarczona, to została wcześniej rozgłoszona przez jakiś proces.
ZAŁOŻENIE: używamy kanałów niezawodnych (ang. perfect links)
when process ~~P_i~~ wants to broadcast a message ~~m~~ to ~~\mathcal{P}~~ do
for all ~~P_j \in \mathcal{P}~~ do
send ~~m~~ to ~~P_j~~
end for
end when
when a message ~~m~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
deliver ~~m~~
end when
Przy założeniach standardowych (pomijamy czasy przetwarzania lokalnego, przyjmujemy jednostkowy czas przesyłu wiadomości):
czasowa : 1
komunikacyjna : n (zakładając, że wysyłamy sami do siebie również)
Zapewnienie wszystkich własności mechanizmu w tym algorytmie wynika wprost z użycia kanałów niezawodnych i ich własności.
WAŻNOŚĆ - jeżeli proces $P_{i}$ jest poprawny, to każda wiadomość rozgłaszana przez $P_{i}$ jest ostatecznie dostarczona do $P_{i}$.
BRAK POWIELANIA - jeżeli wiadomość jest dostarczona, to jest dostarczona co najwyżej raz.
BRAK SAMOGENERACJI - jeżeli wiadomość jest dostarczona, to została wcześniej rozgłoszona przez jakiś proces.
ZGODNOŚĆ - jeżeli wiadomość jest dostarczona przez jakiś poprawny proces, to ostatecznie będzie dostarczona przez wszystkie inne poprawne procesy.
message ~~m~~ is a struct of ~~\langle~~data ~~appdata~~, processId ~~origin \rangle~~
local set of messages $delivered_i$ := $\emptyset$
ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort broadcast)
when process ~~P_i~~ wants to broadcast a message ~~m~~ to ~~\mathcal{P}~~ do
$m$.$origin$ := $P_i$
deliver $m$
$delivered_i$ := $delivered_i \cup m$
broadcast $m$ using best-effort primitive
end when
ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort broadcast)
when message $m$ arrives at process $P_i$ from $P_j$ do
if $m \not\in delivered_i$ then
deliver $m$
$delivered_i$ := $delivered_i \cup m$
broadcast $m$ using best-effort primitive
end if
end when
ZŁOŻONOŚĆ CZASOWA
Optymistyczna (nadawca nie ulega awarii) : 1
Pesymistyczna (wszyscy po kolei ulegają awarii) : $n$
ZŁOŻONOŚĆ KOMUNIKACYJNA PAKIETOWA
Optymistyczna (nadawca nie ulega awarii) : $n^2$
Pesymistyczna (wszyscy po kolei ulegają awarii) : $n^2$
WAŻNOŚĆ - jeżeli proces $P_{i}$ jest poprawny, to każda wiadomość rozgłaszana przez $P_{i}$ jest ostatecznie dostarczona do $P_{i}$.
BRAK POWIELANIA - jeżeli wiadomość jest dostarczona, to jest dostarczona co najwyżej raz.
BRAK SAMOGENERACJI - jeżeli wiadomość jest dostarczona, to została wcześniej rozgłoszona przez jakiś proces.
ZGODNOŚĆ - jeżeli wiadomość jest dostarczona przez jakiś poprawny proces, to ostatecznie będzie dostarczona przez wszystkie inne poprawne procesy.
BRAK SAMOGENERACJI - jeżeli wiadomość jest dostarczona, to została wcześniej rozgłoszona przez jakiś proces.
Wynika wprost z własności braku samogeneracji podstawowego rozgłaszania niezawodnego
WAŻNOŚĆ - jeżeli proces $P_{i}$ jest poprawny, to każda wiadomość rozgłaszana przez $P_{i}$ jest ostatecznie dostarczona do $P_{i}$.
BRAK POWIELANIA - jeżeli wiadomość jest dostarczona, to jest dostarczona co najwyżej raz.
ZGODNOŚĆ - jeżeli wiadomość jest dostarczona przez jakiś poprawny proces, to ostatecznie będzie dostarczona przez wszystkie inne poprawne procesy.
BRAK POWIELANIA - jeżeli wiadomość jest dostarczona, to jest dostarczona co najwyżej raz.
Podstawowe rozgłaszanie niezawodne nie duplikuje wiadomości, ale algorytm powoduje, że niektóre wiadomości są przesyłane kilkakrotnie i do jednego procesu mogą dotrzeć wielokrotnie. Algorytm jednak dostarcza tylko pierwszą, a pozostałe są ignorowane.
WAŻNOŚĆ - jeżeli proces $P_{i}$ jest poprawny, to każda wiadomość rozgłaszana przez $P_{i}$ jest ostatecznie dostarczona do $P_{i}$.
ZGODNOŚĆ - jeżeli wiadomość jest dostarczona przez jakiś poprawny proces, to ostatecznie będzie dostarczona przez wszystkie inne poprawne procesy.
WAŻNOŚĆ - jeżeli proces $P_{i}$ jest poprawny, to każda wiadomość rozgłaszana przez $P_{i}$ jest ostatecznie dostarczona do $P_{i}$.
Proces wysyłający wiadomość natychmiast ją dostarcza, więc jeżeli nie ulegnie awarii, na pewno wlasność będzie spełniona.
ZGODNOŚĆ - jeżeli wiadomość jest dostarczona przez jakiś poprawny proces, to ostatecznie będzie dostarczona przez wszystkie inne poprawne procesy.
ZGODNOŚĆ - jeżeli wiadomość jest dostarczona przez jakiś poprawny proces, to ostatecznie będzie dostarczona przez wszystkie inne poprawne procesy.
Jeżeli proces $P_i$ inicjujący rozsyłanie jest poprawny, to z własności podstawowego rozgłaszania niezawodnego wiadomość dotrze do wszystkich innych poprawnych procesów, które natychmiast ją dostarczą
Jeżeli proces $P_i$ nie jest poprawny, to kanały niezawodne nic nie gwarantują. Wiadomość może dotrzeć do części procesów, albo do żadnego.
ZGODNOŚĆ - jeżeli wiadomość jest dostarczona przez jakiś poprawny proces, to ostatecznie będzie dostarczona przez wszystkie inne poprawne procesy.
Jeżeli proces $P_i$ nie jest poprawny, to kanały niezawodne nic nie gwarantują. Wiadomość może dotrzeć do części procesów, albo do żadnego.
Jeżeli nie dotrze do żadnego procesu albo dotrze tylko do procesów, które uległy awarii, nic się nie stało - własność wymaga tylko, by jeżeli jakiś proces poprawny dostarczył, to inne poprawne muszą dostarczyć. (1)
Co się jednak stanie, jeżeli wiadomość dotrze...
... do jakiegoś procesu poprawnego? (2)
... do jakiegoś procesu niepoprawnego, który zdąży ją rozgłosić? (3)
Jeżeli proces $P_i$ inicjujący rozsyłanie jest poprawny, to z własności podstawowego rozgłaszania niezawodnego wiadomość dotrze do wszystkich innych poprawnych procesów, które natychmiast ją dostarczą
ZGODNOŚĆ - jeżeli wiadomość jest dostarczona przez jakiś poprawny proces, to ostatecznie będzie dostarczona przez wszystkie inne poprawne procesy.
Jeżeli proces $P_i$ nie jest poprawny, to kanały niezawodne nic nie gwarantują. Wiadomość może dotrzeć do części procesów, albo do żadnego.
Co się jednak stanie, jeżeli wiadomość dotrze...
... do jakiegoś procesu poprawnego? (2)
Jeżeli proces $P_i$ inicjujący rozsyłanie jest poprawny, to z własności podstawowego rozgłaszania niezawodnego wiadomość dotrze do wszystkich innych poprawnych procesów, które natychmiast ją dostarczą
... do jakiegoś procesu niepoprawnego, który zdąży ją rozgłosić? (3)
Jeżeli nie dotrze do żadnego procesu albo dotrze tylko do procesów, które uległy awarii, nic się nie stało - własność wymaga tylko, by jeżeli jakiś proces poprawny dostarczył, to inne poprawne muszą dostarczyć. (1)
ZGODNOŚĆ - jeżeli wiadomość jest dostarczona przez jakiś poprawny proces, to ostatecznie będzie dostarczona przez wszystkie inne poprawne procesy.
Co się jednak stanie, jeżeli wiadomość dotrze...
... do jakiegoś procesu niepoprawnego, który zdąży ją rozgłosić? (3)
Przez rekurencję powtarzamy rozumowanie jak poprzednio, czyli powtarzamy punkty (1), (2) oraz (3). A z tego wynika, że jeżeli jakiś proces poprawny dostarczył, to inne poprawne na pewno ją dostarczą. CND.
Jeżeli nie dotrze do żadnego procesu albo dotrze tylko do procesów, które uległy awarii, nic się nie stało - własność wymaga tylko, by jeżeli jakiś proces poprawny dostarczył, to inne poprawne muszą dostarczyć. (1)
... do jakiegoś procesu poprawnego? (2)
ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort broadcast); Dostępny jest doskonały detektor awarii $FD_i$
message ~~m~~ is a struct of ~~\langle~~data ~~appdata~~, processId ~~origin \rangle~~
local set of messages $delivered_i$ := $\emptyset$
local set of processes $correct_i$ := $\mathcal{P}$
local array of set of pair of $\langle$processId, message$\rangle$ $from_i$ := $\emptyset$
ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort broadcast); Dostępny jest doskonały detektor awarii $FD_i$
when process ~~P_i~~ wants to broadcast a message ~~m~~ to ~~\mathcal{P}~~ do
$m$.$origin$ := $P_i$
broadcast $m$ using best-effort primitive
end when
ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort broadcast); Dostępny jest doskonały detektor awarii $FD_i$
when message $m$ arrives at process $P_i$ from $P_j$ do
if $m \not\in delivered_i$ then
deliver $m$
$delivered_i$ := $delivered_i \cup m$
$from_i[j]$ := $from_i[j] \cup \left\{ m.origin, m\right\}$
if $P_j \not\in correct_i$ then
broadcast $m$ using best-effort primitive
end if
end if
end when
ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort broadcast); Dostępny jest doskonały detektor awarii $FD_i$
when $FD_i$ starts suspecting $P_j$ do
$correct_i$ := $correct_i \setminus P_j$
for all $\langle pId,m\rangle \in from_i[j]$ do
$m.origin$ := $P_j$
broadcast $m$ using best-effort primitive
end if
end when
ZŁOŻONOŚĆ CZASOWA
Optymistyczna (nadawca nie ulega awarii) : 1
Pesymistyczna (wszyscy po kolei ulegają awarii) : $n$
ZŁOŻONOŚĆ KOMUNIKACYJNA PAKIETOWA
Optymistyczna (nadawca nie ulega awarii) : $n$
Pesymistyczna (wszyscy po kolei ulegają awarii) : $n^2$
WAŻNOŚĆ - jeżeli proces $P_{i}$ jest poprawny, to każda wiadomość rozgłaszana przez $P_{i}$ jest ostatecznie dostarczona do $P_{i}$.
BRAK POWIELANIA - jeżeli wiadomość jest dostarczona, to jest dostarczona co najwyżej raz.
BRAK SAMOGENERACJI - jeżeli wiadomość jest dostarczona, to została wcześniej rozgłoszona przez jakiś proces.
JEDNOLITA ZGODNOŚĆ - jeżeli wiadomość jest dostarczona przez dowolny proces (poprawny lub nie), to ostatecznie będzie dostarczona przez wszystkie poprawne procesy.
ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort broadcast) oraz kanały niezawodne; Dostępny jest doskonały detektor awarii $FD_i$
message ~~m~~ is a struct of ~~\langle~~data ~~appdata~~, processId ~~origin \rangle~~
local set of messages $delivered_i$ := $\emptyset$
local set of messages $pending_i$ := $\emptyset$
local set of processes $correct_i$ := $\mathcal{P}$
local set of pair of $\langle$processId, message$\rangle$ $acks_i$ := $\emptyset$
ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort broadcast) oraz kanały niezawodne; Dostępny jest doskonały detektor awarii $FD_i$
when process ~~P_i~~ wants to broadcast a message ~~m~~ to ~~\mathcal{P}~~ do
$m$.$origin$ := $P_i$
$pending_i$ := $m$
broadcast $m$ using best-effort primitive
end when
when $FD_i$ starts suspecting $P_j$ do
$correct_i$ := $correct_i \setminus P_j$
end when
ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort broadcast) oraz kanały niezawodne; Dostępny jest doskonały detektor awarii $FD_i$
when message $m$ arrives at process $P_i$ from $P_j$ do
$acks_i$ := $acks_i \cup \langle P_j, m\rangle$
if $m \not\in pending_i$ then
$pending_i$ := $pending_i \cup m$
broadcast $m$ using best-effort primitive
end if
end when
ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort broadcast) oraz kanały niezawodne; Dostępny jest doskonały detektor awarii $FD_i$
when $\exists m\in pending_i :: \forall P_j \in correct_i, \langle P_j, m\rangle\in acks_i$
if $m \not\in delivered_i$ then
$delivered_i$ := $delivered_i \cup m$
$pending_i$ := $pending_i \setminus m$
deliver $m$
end if
end when
ZŁOŻONOŚĆ CZASOWA
Optymistyczna (nadawca nie ulega awarii) : 2
Pesymistyczna (wszyscy po kolei ulegają awarii) : $n$+1
ZŁOŻONOŚĆ KOMUNIKACYJNA PAKIETOWA
W obu przypadkach : $n^2$
W praktyce rzadko zdarza sie więcej, niż jedna awaria naraz; sytuacje, w których awarii ulega większość procesów, są praktycznie niespotykane i zwykle wymagają interwencji człowieka
Algorytm z potwierdzeniami od większości
Algorytm będzie działał, o ile większość procesów faktycznie będzie poprawna. Dlaczego?
Algorytm z potwierdzeniami od wszystkich
Algorytm z potwierdzeniami od wszystkich
Co, jeżeli liczba procesów dramatycznie wzrośnie?
Rozwiązanie - wirtualne drzewo/las, gossiping, osłabienie własności - ostateczna spójność...
WAŻNOŚĆ - Dane jest prawdopodobieństwo takie, że jeżeli procesy $P_{i}$ oraz $P_j$ są poprawne, to każda wiadomość rozgłaszana przez $P_{i}$ jest ostatecznie dostarczona przez $P_{j}$ z tym prawdopodobieństwem.
BRAK POWIELANIA - jeżeli wiadomość jest dostarczona, to jest dostarczona co najwyżej raz.
BRAK SAMOGENERACJI - jeżeli wiadomość jest dostarczona, to została wcześniej rozgłoszona przez jakiś proces.
ZAŁOŻENIE: używamy kanałów rzetelnych (ang. fair-loss)
message ~~m~~ is a struct of ~~\langle~~data ~~appdata~~, processId ~~origin~~, int ~~ttl \rangle~~
local set of messages $delivered_i$ := $\emptyset$
constant int $fanout, maxRoundNo$
ZAŁOŻENIE: używamy kanałów rzetelnych (ang. fair-loss)
procedure GOSSIP( message $m$ )
local set of processes $targets_i$
$targets_i$ := pick $fanout$ random processes from $\mathcal{P}$
for all $P_k \in targets_i$ then
send $m$ to $P_k$ using fair-loss primitive
end if
end procedure
ZAŁOŻENIE: używamy kanałów rzetelnych (ang. fair-loss)
when process ~~P_i~~ wants to broadcast a message ~~m~~ to ~~\mathcal{P}~~ do
~~m.origin~~ := ~~P_i~~
~~m.ttl~~ := ~~maxRoundNo~~
deliver ~~m~~
~~delivered_i~~ := ~~delivered_i \cup m~~
GOSSIP( ~~m~~ )
end when
ZAŁOŻENIE: używamy kanałów rzetelnych (ang. fair-loss)
when a message ~~m~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
if ~~m \not\in delivered_i~~ then
deliver ~~m~~
~~delivered_i~~ := ~~delivered_i \cup m~~
end if
if ~~m.ttl > 0~~ then
~~m.ttl~~ := ~~m.ttl~~ - 1
GOSSIP( ~~m~~ )
end if
end when
Rozgłaszanie dowolną metodą (zawodną).
Po otrzymaniu wiadomości, proces dostarcza ją oraz zapamiętuje z pewnym prawdpodobieństwem celem ewentualnej retransmisji.
Procesy jakoś wykrywają zagubienie wiadomości i rozsyłają prośby o retransmisję przy pomocy plotkowania.
Po otrzymaniu wiadomości, proces dostarcza ją oraz zapamiętuje z pewnym prawdpodobieństwem celem ewentualnej retransmisji.
Procesy jakoś wykrywają zagubienie wiadomości i rozsyłają prośby o retransmisję przy pomocy plotkowania.
Na przykład wymuszamy FIFO - nadajemy numery wiadomościom i w ten sposób wykrywamy "luki".
Po otrzymaniu wiadomości, proces dostarcza ją oraz zapamiętuje z pewnym prawdpodobieństwem celem ewentualnej retransmisji.
Procesy jakoś wykrywają zagubienie wiadomości i rozsyłają prośby o retransmisję przy pomocy plotkowania.
Proces odbierający prośbę o retransmisję spełnia ją, jeżeli zapamiętał wcześnej tę wiadomość, w przeciwnym wypadku rozsyła prośbę dalej.
ZAŁOŻENIE: używamy kanałów rzetelnych (ang. fair-loss)
message ~~m~~ is a struct of ~~\langle~~data ~~appdata~~, processId ~~origin~~, int ~~seqNo \rangle~~
message ~~req~~ is a struct of ~~\langle~~processId ~~origin~~, int ~~seqNo~~, int ~~ttl \rangle~~
constant int $fanout, maxRoundNo, storeThr$
local set of messages $delivered_i$ := $\emptyset$
local set of messages $stored_i$ := $\emptyset$
local set of messages $pending_i$ := $\emptyset$
local int ~~seqNo_i~~ := 0
local array of int $vSeqNo_i$ := ~~\{~~ 0, ~~\ldots~~, 0 ~~\}~~
ZAŁOŻENIE: używamy kanałów rzetelnych (ang. fair-loss)
procedure GOSSIP( message $m$ )
local set of processes $targets_i$
$targets_i$ := pick $fanout$ random processes from $\mathcal{P}$
for all $P_k \in targets_i$ then
send $m$ to $P_k$ using fair-loss primitive
end if
end procedure
procedure DeliverPending( ~~P_k~~ )
while ~~\exists m \in pending_i :: m.origin = P_k \land~~
~~m.seqNo~~ = ~~vSeqNo_i[k]~~ + 1 do
$vSeqNo_i[k]$ := ~~m.seqNo~~
$pending_i$ := ~~pending_i \setminus m~~
$delivered_i$ := ~~delivered_i \cup m~~
deliver ~~m~~
end while
end procedure
ZAŁOŻENIE: używamy dowolnego zawodnego mechanizmu rozgłaszania
when process ~~P_i~~ wants to broadcast a message ~~m~~ to ~~\mathcal{P}~~ do
$seqNo_i$ := ~~seqNo_i~~ + 1
$m.seqNo$ := ~~seqNo_i~~
$m.origin$ := ~~i~~
$delivered_i$ := ~~delivered_i \cup m~~
deliver ~~m~~
broadcast ~~m~~ to ~~\mathcal{P}~~
end when
when a message ~~m~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
if ~~m\not\in delivered_i~~ then
$r$ := a random number from specified range
if $m\not\in stored_i \land r < storeThr$ then
$stored_i$ := $stored_i \cup m$
end if
~~k~~ := ~~m.origin~~
if $m.seqNo$ = $vSeqNo_i[k]$ + 1 then
$vSeqNo_i[k]$ := ~~m.seqNo~~
$delivered_i$ := ~~delivered_i \cup m~~
deliver ~~m~~
DeliverPending( ~~P_k~~ )
else if ~~m \not\in pending_i~~ then
/* continued on the next slide */
ZAŁOŻENIE: używamy kanałów rzetelnych
else if ~~m \not\in pending_i~~ then
~~pending_i~~ := ~~pending_i \cup m~~
for all ~~s :: s > vSeqNo_i[k] \land s < m.seqNo~~ do
~~req.origin~~ := ~~P_i~~
~~req.ttl~~ := ~~maxRoundNo~~
~~req.seqNo~~ := ~~s~~
GOSSIP( ~~req~~ )
end for
end if
end if
end when
ZAŁOŻENIE: używamy kanałów rzetelnych
when a message ~~req~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
if ~~\exists m\in stored_i :: m.seqNo = req.seqNo\mbox{ }\land~~
~~m.origin = req.origin~~ then
send $m$ to $req.origin$
else
~~req.ttl~~ := ~~req.ttl~~ - 1
if ~~req.ttl > 0~~ then
GOSSIP( ~~req~~ )
end if
end if
end when
WAŻNOŚĆ, ZGODNOŚĆ, BRAK POWIELANIA i SAMOGENERACJI - jak w zgodnym
UPORZĄDKOWANIE PRZYCZYNOWE - jeżeli proces $P_i$ dostarcza wiadomości $m^k$ oraz $m^l$, a zdarzenie wysłania $m^k$ poprzedza przyczynowo zdarzenie wysłania $m^l$, to proces $P_i$ musi dostarczyć $m^k$ przez wiadomością $m^l$
WAŻNOŚĆ, ZGODNOŚĆ, BRAK POWIELANIA i SAMOGENERACJI - jak w zgodnym
ZAŁOŻENIE: Zakładamy dostępność jakiegoś mechanizmu gwarantującego zachowanie własności zgodnego rozgłaszania niezawodnego.
ZAŁOŻENIE: Zakładamy dostępność jakiegoś mechanizmu gwarantującego zachowanie własności zgodnego rozgłaszania niezawodnego.
message ~~m~~ is a struct of ~~\langle~~data ~~appdata~~,
set of pair of ~~\langle~~processId, message~~\rangle\mbox{ }past\mbox{ }~~
~~\rangle~~
local set of messages $delivered_i$ := $\emptyset$
local set of pair of ~~\langle~~ processId, message ~~\rangle~~ $past_i$ := $\emptyset$
ZAŁOŻENIE: Zakładamy dostępność jakiegoś mechanizmu gwarantującego zachowanie własności zgodnego rozgłaszania niezawodnego.
when process ~~P_i~~ wants to broadcast a message ~~m~~ to ~~\mathcal{P}~~ do
$m.past$ := ~~past_i~~
broadcast ~~m~~ to ~~\mathcal{P}~~
$past_i$ := ~~past_i \cup \{ m, P_i \}~~
end when
when a message ~~m~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
if ~~m\not\in delivered_i~~ then
for all $\{m^{\prime},P_k\} \in m.past$ do
if ~~m^{\prime}\not\in delivered_i~~ then
deliver ~~m^{\prime}~~
~~past_i~~ := ~~past_i \cup \{ m^{\prime}, P_k\}~~
end if
end for
deliver ~~m~~
$past_i$ := ~~past_i \cup \{ m, P_j \}~~
$delivered_i$ := ~~delivered_i \cup \{ m \}~~
end if
end when
... Aaaale masz jakieś wady, prawda?
Rosnący zbiór $past$ powoduje, że trudno myśleć o implementacji algorytmu wprost, chociaż można ten problem rozwiązać dzięki mechanizmowi garbage collecting
WAŻNOŚĆ, ZGODNOŚĆ, BRAK POWIELANIA i SAMOGENERACJI - jak w zgodnym
GLOBALNE UPORZĄDKOWANIE WIADOMOŚCI - Wszystkie procesy dostarczają wiadomości w tym samym porządku