Le comunicazioni ordinate
Comunicazioni Ordinate
E’ importante (e utile) definire delle primitive di
comunicazione che diano qualche garanzia
sull’ordine di consegna dei messaggi inviati
all’interno di un gruppo di processi
Vedremo le seguenti:
Comunicazione che rispetta l’ordine FIFO di invio dei
messaggi
Comunicazione che rispetta l’ordine causale
Comunicazione che rispetta un ordine totale
Comunicazione in un gruppo di processi
Comunicazione di gruppo: gruppo definito di processi. Primitive di gruppo
che garantiscono vari tipi di reliability:
(1) Best-effort broadcast
(2) (Regular) reliable broadcast
(3) Uniform (reliable) broadcast
Rivediamo la specifica del (Regular) reliable brodcast, (d’ora in poi solo
Reliable broadcast) :
Safety.
Integrity (No Duplication, No Creation): per qualsiasi messaggio m,
ogni processo corretto consegna m al più una volta, e solo se m è stato
precedentemente inviato in broadcast da un processo mittente
Liveness:
Validity: se un processo corretto invia in broadcast un messaggio m,
allora tutti i processi corretti alla fine consegnano m.
Agreement : se un processo corretto consegna un messaggio m, allora
tutti i processi corretti alla fine consegnano m.
Utilità della comunicazione ordinata
Nel Reliable broadcast non c’è alcun requisito sull’ordine in
cui i messaggi sono consegnati
Per alcune applicazioni ciò può portare ad “anomalie”...
Esempio: sistema di prenotazione aerea. L’anomalia
consiste in una consegna di un msg di cancellazione di
una prenotazione che il server non ha ancora registrato!
client
server
“reserve”
“Prices
15% off”
“cancel”
t
FIFO Broadcast\specifica
Qual è la soluzione? Occorre che i messaggi di broadcast inviati
dallo stesso mittente vengano consegnati nello stesso ordine in
cui i messaggi sono stati inviati.
A questo scopo introduciamo una nuova primitiva di
comunicazione di gruppo in grado di implementare questa
soluzione: FIFO Broadcast
La specifica del FIFO broadcast è costituita dalle proprietà viste
per il Reliable broadcast alle quali si aggiunge un’altra proprietà
di Safety per catturare la nozione di ordine:
FIFO Order: se un processo invia in broadcast un messaggio m prima di
un messaggio m’, allora nessun processo corretto consegna m’ a meno
che non abbia precedentemente consegnato m.
FIFO Broadcast = Reliable Broadcast + FIFO Order
FIFO Broadcast\algoritmo
Each process q holds:
S p a count of messages broadcast by p
Rp the sequence number of the latest
message sent by p and delivered by q
For p to FO-multicast a message to g, it
piggybacks S p on the message,
rbBroadcasts it and increments S p by 1
Mes sage
process ing
deliver
On receipt of a message from q sent by
p with sequence number S, p checks
whether
S = Rp + 1. If so, q FO-delivers it
Rp +
if S >
1 then q places message in
hold-back queue until intervening
messages have been delivered. (note
that rbBroadcast does eventually deliver
messages unless the sender crashes)
Hold-back
queue
Incoming
mes sages
Delivery queue
When deliv ery
guarant ees are
met
Utilità della comunicazione ordinata(2)
Il FIFO order non preclude tutte le anomalie dovute ad uno strano ordine di
consegna…
Es: Applicazione di tipo newsgroup.
Prof.
m1:
“Fri exam cancelled”
m2:
Student 1
Student 2
“let’s party on Thu night”
m3:
“but we have an exam on Fri!”
Anche se il FIFO order è soddisfatto (banalmente), cosa non va? m2
dipende da m1 ma Student 2 consegna m2 prima di m1
Qual è la soluzione? Poiché m1 precede causalmente m2, allora m2 non
deve essere consegnato finchè prima non viene consegnato m1
A questo scopo introduciamo una nuova primitiva alle comunicazioni di
gruppo in grado di implementare questa soluzione: Causal Broadcast
Causal Broadcast\specifica
La specifica del Causal broadcast è costituita dalle proprietà
viste per il Reliable broadcast alle quali si aggiunge un’altra
proprietà di Safety per catturare la nozione di ordine:
Causal Order: se il broadcast di un messaggio m precede
causalmente il broadcast di un messaggio m’, allora nessun processo
corretto consegna m’ a meno che non abbia precedentemente
consegnato m.
Causal Broadcast = Reliable Broadcast+Causal Order
Causal Order FIFO Order,
ma FIFO OrderCausal Order
Quindi, Causal Order = FIFO Order + ?
Causal Broadcast\specifica
Causal Order = FIFO Order + Local Order.
Local Order:
se un processo consegna un msg m prima di
inviare in broadcast un msg m’, allora nessun processo corretto
consegna m’ a meno che non abbia precedentemente consegnato m.
Esempio:
p
q
t
m
m’
r
Viene ritardato e consegnato solo
dopo la consegna di m
Causal Broadcast\implementazioni
Due implementazioni
Un algoritmo blocking che usa vector clocks
Un algoritmo non-blocking che usa il passato
p1
COBcast(m1) COdelv(m1)
COdelv(m2)
IDEA DI BASE:
PIGGYBACKING DEI
MESSAGGI che fanno
parte del PASSATO
COdelv(m ) del msg inviato
3
m1
p2
COdelv(m2)
COdelv(m1)
COBcast(m3) COdelv(m3)
m1,m2 , m3
m2
p3
CObcast(m2) COdelv(m2)
COdelv(m1)
scarta
m2 già COdelivered!
COdelv(m3)
Utilità della comunicazione ordinata(3)
Anche il Causal Order non è abbastanza forte per assicurare l’assenza di
anomalie
Es. Applicazione banking. Conto bancario replicato su due siti
R1
R2
A:£100
Deposit
£20
A:£120
A:£132
Add 10%
interest
A:£110
A:£130
A:£100
Sebbene le repliche siano inizialmente identiche alla fine sono
inconsistenti anche se il Causal Order è soddisfatto (banalmente)
Qual è la soluzione? per garantire che le repliche siano sempre identiche, si
deve assicurare che tutti gli update siano consegnati nel medesimo ordine
anche quando non sono causalmente dipendenti.
A questo scopo introduciamo una nuova primitiva comunicazione di gruppo
in grado di implementare questa soluzione : Total Order (Atomic) Broadcast
Atomic Broadcast\specifica
La specifica del Total Order broadcast è costituita dalle
proprietà viste per il Reliable broadcast alle quali si aggiunge
un’altra proprietà di Safety per catturare la nozione di ordine:
Total Order: se due processi corretti p e q consegnano entrambi m ed
m’, allora p consegna m prima di m’ se e solo se q consegna m prima di
m’
Si noti che la proprietà di total order è una proprietà ortogonale
rispetto a FIFO order e causal order. Quindi il total order non è
una proprietà più forte rispetto alle altre due. Ad esempio tutti i
processi potrebbero consegnare due messaggi, inviati dallo
stesso processo, in ordine inverso rispetto a quello di invio.
Gerarchia delle Primitive di Broadcast
Reliable
broadcast
Total Order
Atomic
broadcast
FIFO Order
FIFO Order
Total Order
FIFO
broadcast
Local Order
Causal Order
Causal
broadcast
FIFO Atomic
broadcast
Causal Order
Total Order
Local Order
Causal Atomic
broadcast
Atomic Broadcast e Consenso
Si può realizzare il Consenso con l’atomic broadcast
Si può realizzare l’atomic broadcast con Consenso e reliable
broadcast: il messaggio viene inviato in Reliable Broadcast, i
processi riceventi propongono un numero di sequenza per il
messaggio (in realtà per tutti quelli in coda non ancora ordinati)
facendo partire un Consenso. Alla fine decideranno per la stessa
sequenza di consegna per i messaggi.
Quindi si può dimostrare che l’Atomic Broadcast e il
Consenso sono problemi equivalenti in un sistema con
canali affidabili
Ciò significa che non esiste alcun algoritmo che soddisfa la
specifica dell’atomic broadcast in un modello di sistema asincrono
con guasti di tipo crash: FLP per ATOMIC BROADCAST!!
System model
Static set of processes Π = {p1 … pn}
Message passing over perfect channels (message
exchanging between correct processes is reliable)
Asynchronous
Crash fault model for processes
We characterize the system in terms of its possible runs
R
TOcast(m)
TOdeliver(m)
r
R
m
p1
p2
m
m
pn
crash
A few notation
Property P: predicate on the system,
identifying a set of runs RP  R
P  P’ iff RP  RP’
RP’
RP
R
Specification S(P1,…,Pm): logical and of m
properties, identifying a set of runs
R
RS=RP1∩ … ∩ RPm  R
RP1
RS
S → S’ iff RS  RS’
RS
RS’
R
RPn
TO specifications
Total order specifications are usually composed by four
properties, namely Validity, Integrity,Agreement, and
Order.
A Validity property guarantees that messages sent by
correct processes will eventually be delivered at least by
correct processes;
An Integrity property guarantees that no spurious or
duplicate messages are delivered;
An Agreement property ensures that (at least correct)
processes deliver the same set of messages;
An Order property constrains (at least correct) processes
delivering the same messages to deliver them in the
same order.
TO specifications
Total Order Broadcast = S(V,I,A,O)
V =NUV
Validity
UI
I = Integrity
A = Agreement
O = Order
TO(A,O)
Distinct specifications arise from distinct
formulations of each property
uniform vs non-uniform
A uniform property imposes restrictions on the
behavior of (at least) correct processes on the basis
of events occurred in some process
TO Specifications
Crash failure + Perfect channels 
NUV. if a correct process TOCAST a message
m then some correct process will eventually
deliver m
UI. For any message m, every process p
delivers m at most once and only if m was
previously tocast by some (correct or not)
process.
The Agreement property
(Uniform Agreement, UA) If a process
(correct or not) todelivers a message m,
then all correct processes will eventually
todeliver m;
(Non-uniform Agreement, NUA) If a
correct process todelivers a message m,
then all correct processes will eventually
todeliver m
The Agreement property
Constrains the set of delivered messages
Correct processes always deliver the same set
of messages M
Each faulty process p delivers a set Mp
m4
UA: Mp  M
NUA: Mp can be s.t. Mp - M ≠ 
m3
m2
m1
p1
m3
m2
m4
p2
m3
m1
m1
m2
m3
m4
p2
m1
p3
m2
p1
m1
UA
m4
m4
m3
m1
m2
p3
m5
m4
m3
NUA
The Order property
Constrains the order of message deliveries and
possibly the set of delivered messages
SUTO: if p delivers m<m’, q delivers m’ only after m
same order
same prefix of the set of delivered messages
after an omission, disjoint sets of delivered messages
WUTO: if p,q deliver m,m’, they get the same order
no restrictions on the set of delivered messages
m
m
m1
m2
m3
m2
m3
SUTO
3
m3
m1
m7
6
m7
WUTO
p2
p2
m1
p3
m2
p1
p1
m1
m1
m6
m2
m4
m5
m1
p3
m2
m4
m5
The Order property (2)
SUTO and WUTO are uniform
They both have a non-uniform counterparts:
SNUTO and WNUTO
(Strong Non-uniform Total Order, SNUTO). If
some correct process todelivers some message
m before message m', then a correct process
todelivers m‘ only after it has todelivered m.
(Weak Non-uniform Total Order, WNUTO) If
correct processes p and q both todeliver
messages m and m', then p todelivers m before
m' if and only if q todelivers m before m‘
The Order property (2)
SUTO  WUTO
SNUTO  WNUTO
m2
m3
m1
m2
m3
m2
m1
m1
m6
p1
SNUTO
m7
p2
m4
m5
p3
m2
m3
m1
m2
m3
m2
m1
m1
m6
p1
WNUTO
m7
p2
p3
m4
m5
TO specifications
m1
TO(NUA,SUTO)
m3
m2
m1
The strongest TO spec.
m2
m3
p2
m1
m2
p3
TO(UA,SUTO)
(Strongest
total order)
m6
p1
m1
m2
m3
m6
p2
m1
p3
m2
m4
m4
p1
TO(UA,SUTO)
m1
m2
m5
TO(NUA,SUTO)
m3
m4
TO specifications (2)
TO(UA,WUTO)
m1
m2
m3
TO(UA,SUTO)
(Strongest
total order)
m4
p1
m1
m3
m2
m4
p2
m1
m3
m2
m4
TO(UA,WUTO)
TO(NUA,SUTO)
p3
TO(NUA,WUTO)
m1
m2
m3
m4
m2
m3
m4
m6
p1
m1
m6
p2
m1
p3
m3
m2
m4
m5
m6
TO(NUA,WUTO)
TO specifications (3)
TO(UA,WNUTO)
m1
m3
m2
TO(UA,SUTO)
(Strongest
total order)
m4
p1
m1
m3
m2
m4
p2
m1
m4
m2
m3
TO(UA,WUTO)
TO(NUA,SUTO)
TO(UA,WNUTO)
TO(NUA,WUTO)
p3
TO(NUA,WNUTO)
m1
m2
m3
m4
m2
m3
m4
m6
p1
m1
m6
p2
m1
p3
m4
m2
m3
m5
m6
TO(NUA,WNUTO)