Sistemi Distribuiti
Ing. Sara Tucci Piergiovanni
La nozione di tempo
Modello della Computazione
•
•
Componenti del sistema: n processi e canali di comunicazione
Ogni processo genera una sequenza di eventi
– interni ed esterni (send/receive)
– eik, k-simo evento generato da Pi
• L’evoluzione di una computazione
può essere visualizzata con un
diagramma spazio-tempo.
• Storia di una computazione
– Storia locale: sequenza eventi generati da un singolo processo 
h1= e11 e12 e13 e14 e15 e16
– Storia locale parziale: prefisso della storia locale  h1m= e11 … e1m
– Storia globale: insieme delle storie locali  H =  hi per 1  i n
Il tempo nei sistemi distribuiti
• La nozione di tempo è vitale nei sistemi distribuiti per dare ordine
agli eventi che si susseguono;
–Es. Differenti computer devono ordinare transazioni di commercio
elettronico in modo consistente.
• Tecnica del timestamping:
–Ogni computer etichetta (con un timestamp) un evento. Ciò viene fatto
in modo da costruire un ordine tra tutti gli eventi generati nel sistema
distribuito (anche se hanno origine su computer diversi)
• Soluzione banale: ogni processo etichetta un evento con il valore
del proprio clock fisico...Perche’ non funziona?
L’ordine degli eventi locali ad un singolo processo si puo’ ricostruire...
...e l’ordine di due eventi generati da due processi diversi?
Il tempo nei sistemi distribuiti
•
In un sistema distribuito e’ impossibile avere un unico clock fisico condiviso
da tutti i processi;
•
Prima soluzione:
Tentare di sincronizzare con una certa approssimazione i clock fisici locali ad ogni
processo attraverso opportuni algoritmi . In questo caso il processo puo’ etichettare
gli eventi con il valore del suo clock fisico (in questo caso sincronizzato con gli altri
con una certa approssimazione). In questo caso il timestamping e’ basato sulla
nozione di tempo fisico (clock fisico).
•
Ma e’ sempre possibile eseguire questa sincronizzazione mantenendo
l’errore di approssimazione limitato?
•
No in un modello asincrono!!
•
In un modello asincrono il timestamping non si puo’ basare sul concetto di
tempo fisico. A questo scopo verra’ introdotta la nozione di clock basata su
un tempo logico (clock logici).
Il clock fisico
• All’istante di tempo reale t, il sistema operativo legge il tempo dal
clock hardware Hi(t) del computer, quindi produce il software clock
Ci(t)= aHi(t) + b che approssimativamente misura l’istante di tempo
fisico t per il processo pi.
– Es. . Ci(t) e’ un numero a 64 bit che da’ i nanosecondi trascorsi
all’istante t da un istante di riferimento (es. boot della macchina).
– In generale il clock non e’ completamente accurato: può essere
diverso da t.
– Se Ci si comporta abbastanza bene allora può essere usato come
timestamp per gli eventi che occorrono in pi.
• Quanto deve essere la risoluzione del clock (periodo che intercorre tra
gli aggiornamenti del valore del clock) per poter distinguere due
differenti eventi?
• Tempo di risoluzione < intervallo di tempo che intercorre tra due eventi
rilevanti
Clock fisici in un sistema distribuito
•
Diversi clock locali possono avere valori diversi:
– Skew: “the difference in time between two clocks” (Galli) (differenza
istantanea fra il valore di due qualsiasi clock)
– Drift: i clock contano il tempo con differenti frequenze (fenomeno dovuto a
variazioni fisiche dell’orologio), quindi divergono
– Drift Rate: “the gradual misalignment of once synchronized clocks caused
by the slight inaccuracies of the time-keeping mechanisms” (differenza per
unita’ di tempo rispetto ad un orologio ideale), es. drift rate di 2microsec/sec
significa che il clock incrementa il suo valore di 1sec+1microsec ogni
secondo.
• Normali orologi al quarzo deviano di circa 1 sec in 11-12 giorni. (10-6 secs/sec).
• Orologi al quarzo ad alta precisione hanno un drift rate di circa 10-7 o 10-8
secs/sec
Coordinated Universal Time (UTC)
• UTC è uno standard internazionale per mantenere il tempo.
• Basato su International Atomic Time, quindi e’ basato sul tempo
atomico ma e’ occasionalmente aggiustato utilizzando il tempo
astronomico. I clock fisici che usano oscillatori atomici sono i piu’
accurati (drift rate 10-13)
• L’output dell’orologio atomico e’ inviato in broadcast da stazioni radio
su terra e da satelliti (es. GPS) , In Italia: Istituto Galileo Ferraris
• Computer con ricevitori possono sincronizzare i loro clock con questi
segnali
• Segnali da stazioni radio su terra hanno un’accuratezza di circa 0.110 millisecondi; segnali da GPS hanno un’accuratezza di circa 1
microsec.
Sincronizzazione di clock fisici
• Sincronizzazione esterna
I clock Ci (per i = 1, 2, … N ) sono sincronizzati con una sorgente di tempo
S, in modo che, dato un intervallo I di tempo reale:
–|S(t) - Ci(t)| < D per i = 1, 2, … N e per tutti gli istanti in I
–I clock Ci hanno un’accuratezza che si mantiene all’interno del bound D.
• Sincronizzazione interna
I clock di due computer sono sincronizzati l’uno con l’altro in modo che:
–| Ci(t) - Cj(t)| < D per i = 1, 2, … N nell’intervallo I
–In questo caso i due clock Ci e Cj si accordano all’interno del bound D.
• I clock sincronizzati internamente non sono necessariamente esternamente
sincronizzati. Tutti i clock possono deviare collettivamente da una sorgente
esterna sebbene rimangano sincronizzati entro il bound D.
• Se l’insieme dei processi P e’ sincronizzato esternamente entro un bound D
allora segue dalle definizioni che e’ anche internamente sincronizzato entro
un bound 2D
Nozione di clock corretto
fast clock
•
Un clock hw H e’ corretto se il suo drift rate si
mantiene all’interno di un bound  > 0 limitato.
(es. 10-6 secs/ sec), il drift rate di un clock
corretto e’ almeno -  e al massimo + 
•
Se il clock H e’ corretto allora l’errore che si
commette nel misurare un intervallo di istanti
reali [t,t’] e’ limitato:
–
perfect clock
slow clock
(1 -  (t’ - t) ≤ H(t’) - H(t) ≤ (1 +  (t’ - t) (t<t’) (in
questo modo si evitano “salti” del valore del clock)
Per il clock sw C spesso basta una condizione di monotonicita’
• t' > t implica C(t’) > C(t)
Es. condizione richiesta da Unix make: 200 files compilati alle 17,00 e C(17,00)=17,30, 3 modificati alle
17,15.
Se no monotonicita’ e C(17,15)=17,20 non ricompila nulla!
Si puo’ garantire monotocita’ con un clock hw che va veloce: scelgo opportunamente i valori a e b
Clock guasto: se non rispetta le condizioni di correttezza
•crash failure – un clock che smette di funzionare
•arbitrary failure – qualsiasi altro guasto (es. Y2K bug che dopo il 31/1/1999 mette 1/1/1900 anziche’
1/1/2000)
Si noti che la correttezza non implica accuratezza...
Sincronizzazione interna in un sistema sincrono
Sistema sincrono
– the time to execute each step of a process has known lower and upper
bounds
– each message transmitted over a channel is received within a known
bounded time
– each process has a local clock whose drift rate from real time has a
known bound
Algoritmo:




One process p1 sends its local time t to process p2 in a message m,
p2 could set its clock to t + Ttrans where Ttrans is the time to transmit m
Ttrans is unknown but min ≤ Ttrans ≤ max
uncertainty u = max-min. Set clock to t + (max - min)/2 then skew ≤ u/2
SISTEMA ASINCRONO: Ttrans = min + x con x >= 0
Sincronizzazione mediante Time Server
• Time Service Centralizzati
– Request-driven
• Esempio Cristian Algorithm
– Broadcast-based
• Esempio Berkeley Unix algorithm - Gusella & Zatti
(1989)
• Distribuiti (Network Time Protocol)
Algoritmo di Cristian
• Un time server S riceve il segnale da una sorgente UTC
• Un processo p richiede il tempo con mr e riceve t in mt da S
– p setta il suo clock a t + Tround/2 Tround e’ il round trip time registrato da p
– Accuratezza ± (Tround/2 - min) : (min e’ il minimo tempo di trasmissione)
• S non puo’ mettere t nel messaggio mt prima che sia trascorso un tempo
min dall’istante in cui p ha inviato mr.
• S non puo’ mettere t nel messaggio mt dopo il momento che mt arriva a p
meno min.
• Il tempo di S quando mt arriva è compreso nel range [t+min, t + Tround - min]
mr
p
mt
Time server,S
Osservazioni:
• Un singolo time server potrebbe guastarsi,
• Cristian suggerisce l’uso di un gruppo di server sincronizzati
• Non prevede server maliziosi
Request-Driven Synchronization
RTT=20
Algoritmo Berkeley
• Algoritmo Berkeley: algoritmo per la sincronizzazione interna di un
gruppo di computer
– Il master richiede, attraverso broadcast, il valore dei clock delle altre
macchine del sistema distribuito, quindi colleziona i valori dei clock degli
altri (slaves)
– Il master usa i round trip time per stimare i valori dei clock degli slave
– Prende la media di questi
– Manda l’aggiustamento opportuno agli slave (se l’aggiustamento
prevede un salto indietro nel tempo, lo slave non setta il nuovo valore
ma rallenta)
– L’accuratezza del protocollo dipende da un round-trip time nominale
massimo: il master non considera valori di clock associati a RTT
superiori al massimo
– Fault tolerance:
• se un master cade un’altra macchina viene eletta master (in un tempo non
limitato a priori)
• E’ tollerante a comportamenti arbitrari (slave che inviano valori errati di
cllock): Il master prende un certo numero valori di clock (da un sottoinsieme
di slave). Questi valori non differiscono tra loro per una quantità specificata.
Berkeley Algorithm
747
739
9
9
3
NOTA: Che cosa significa rallentare un clock? Non si puo’
pensare di imporre un valore di tempo passato alla locazione B.
Cio’ provocherebbe un problema di ordinamento causa/effetto
di eventi locali a B. Quindi la soluzione e’ quella di mascherare
una serie di interrup che fanno avanzare il clock locale in modo
di rallentare l’avanzata del clock stesso. Il numero di interrupt
mascherati è pari al tempo di slowdown diviso il periodo di
interrupt del processore.
Network Time Protocol (NTP)
• Time service per Internet - sincronizza client a UTC:
• Reliability da server e path ridondanti, e’scalabile, autentica time sources
Primary servers are connected to UTC
sources
Secondary servers are synchronized to
primary servers
Synchronization subnet - lowest level servers
in users’ computers
1
2
3
2
3
3
NTP – sincronizzazione di server
• La sottorete di sincronizzazione si riconfigura in caso di guasti es.
– Un primary che perde la connessione alla sorgente UTC puo’
diventare un server secondario
– Un secondario che perde la connessione al suo primary (crash del
primary) può usare un altro primary
• Modi di sincronizzazione:
– Multicast: un server all’interno di una LAN ad alta velocita’ manda in
multicast il suo tempo agli altri che settano il tempo ricevuto
assumendo un certo ritardo (non molto accurato)
– Procedure call: un server accetta richieste da altri computer (come
algoritmo di Cristian). Alta accuratezza. Utile se non e’ disponibile un
multicast hw.
– Simmetrico: coppie di server scambiano messaggi contenenti info
sul timing. Usata quando e’ necessaria un’accuratezza molto alta
(per gli alti livelli della gerarchia)
Messaggi scambiati da coppie di peers
• Tutti i modi di sincronizzazione usano UDP
• Ogni msg porta timestamps di eventi recenti:
– Local times di Send e Receive del messaggio precedente
– Local times di Send del messaggio corrente
• Il ricevente segna il tempo in cui riceve il msg Ti ( si ha Ti-3, Ti-2, Ti-1,
Ti)
• Nel modo simmetrico il ritardo tra l’arrivo di un messaggio e l’invio
del successivo potrebbe essere non trascurabile
Server B
Ti-2
m
Ti-1
Time
m'
Time
Server A
Ti- 3
Ti
Accuratezza di NTP
• Per ogni coppia di msg scambiati tra i due server, NTP stima un offset oi
tra i 2 clock ed un ritardo di (tempo di trasmissione totale per i 2 msg)
• Supponi che il vero offset del clock di B rispetto ad A sia o e i tempi di
trasmissione dei msg m ed m’ siano rispettivamente t e t’
Ti-2 = Ti-3 + t + o e Ti = Ti-1 + t’ - o
• Quindi il tempo totale di trasmissione dei msg:
di = t + t’ = Ti-2 - Ti-3 + Ti - Ti-1
• E (sottraendo le equazioni)
o = oi + (t’ - t )/2 con oi = (Ti-2 - Ti-3 + Ti - Ti-1 )/2
• Considerando che t, t’>0 si può dimostrare che
oi - di /2 ≤ o ≤ oi + di /2 .
– Quindi oi è una stima dell’offset e di è una misura dell’accuratezza della
stima
• NTP servers filtrano le coppie <oi, di>, stimano l’affidabilita’ dei dati dalla
differenza con la stima, cosi’ seleziona i peers che usa per
sincronizzarsi
• Accuratezza di 10 millisecs su Internet paths (1 su LANs)
Il tempo in un sistema asincrono
Tempo Fisico: proprietà globale…
osservabile?
?

NO in un sistema distribuito
asincrono: clock diversi e
impossibilità di sincronizzarli

L’impossibilità di una sincronizzazione precisa deriva
dall’impredicibilità dei ritardi della comunicazione
Quindi, il tempo di due eventi che accadono in processi
diversi non può generalmente essere utilizzato per
decidere quando un evento precede l’altro

Nozione di Tempo Logico
• Basato sulle seguenti
ovvie assunzioni:
– Due eventi nello stesso
processo sono
“naturalmente” ordinati
– Una trasmissione precede
sempre una ricezione
– Gli eventi sono così
ordinati secondo la nozione
di causa-effetto
(precedenza causale o
happened before)
Happened-before
• Dati due eventi e ed e’ allora e precede e’,
indicandolo con e  e’ se:
1. gli eventi e ed e’ appartengono allo stesso
processo ed e accade prima di e’;
2. gli eventi e ed e’ appartengono invece a processi
distinti, e è l’evento di invio di un messaggio ed e’
l’evento di ricezione di tale messaggio;
3. se esiste un evento e’’ t.c. e  e’’ e e’’  e’
• Dati due eventi e ed e’ se (e  e’) ed (e’ 
e ), i due eventi sono detti concorrenti: e || e’
Happened-Before/esempio
• Dato un diagramma spazio-tempo allora e  e’ se è
possibile tracciare un percorso da e ad e’, procedendo
da sinistra verso destra, altrimenti sono concorrenti
• Nell’ esempio: e32e22, e23e13 e quindi e32 e13,
mentre gli eventi e21 e e33 sono concorrenti.
P1
e11
e31
e21
e41
e51
e61
j-esimo evento
del processo Pi
eji
P2
e12
e22
e32
e42
e52
e62
e72
P3
e13
e23
e33
e43
e53
e63
Clock Logico
• L’idea è di ordinare gli eventi del sistema assegnando un
numero naturale ad ogni evento (timestamping scalare)
• L’ordinamento è basato sulla relazione “happened
before ”
• Ad ogni evento e del sistema viene associato un
timestamp C(e), tale che:
se e  e’ allora C(e) < C(e’)
Timestamping scalare\implementazione
Pi mantiene un contatore Ci inizializzato a 0 e segue le
seguenti regole di aggiornamento:
1. quando Pi processa un evento, prima incrementa il contatore Ci
di una unità (Ci := Ci +1) e quindi associa un timestamp Ti
all’evento il cui valore è pari al valore corrente di Ci;
2. quando Pi invia un messaggio, esegue l’evento di trasmissione
e allega al messaggio il timestamp Ti associato a tale evento
ricavato dalla regola 1;
3. quando a Pi arriva un messaggio m con timestamp T, esso
pone Ci=max(Ci ,T) e quindi esegue l’evento di ricezione del
messaggio (regola 1).
Timestamping scalare\esempio
P1
1
2
e11
P2
5
e31
e21
1
6
4
3
7
e41
8
e51
5
8
j-esimo evento
del
processo Pi
ej
i
e61
9
10
k
e12
P3
1
e22
e32
2
3
e13
e23
e33
e32

e13
e42
e52
6
e43
7
e53
e62
e72
11
e63
e14 || e35 : hanno timestamp diversi
e31 || e11 : hanno stesso timestamp
Timestamp
scalare associato
all’evento dal
processo
Vector Clock
• Clock logici: non catturano completamente la
relazione happened-before. Infatti pur
soddisfacendo la seguente proprietà: se e  e’
allora C(e) < C (e’), non soddisfano il viceversa:
C(e) < C(e’) non implica e  e’
• In sostanza i clock logici non permettono di
stabilire se due eventi sono concorrenti
• Mattern nel 1988 ha introdotto la nozione di
vector clock, che invece caratterizza
completamente la relazione di causalità.
Vector Clock
• Ad ogni evento e viene assegnato un vettore V(e) di
dimensione pari al numero dei processi con la seguente
proprietà:
e  e’ se e solo se V(e) < V(e’)
• Che significato ha il comparatore di minoranza tra
vettori?
V(e) < V(e’) se e solo se
x[1,…,n]: V(e’)[x]  V(e)[x] 
x[1,…,n]: V(e’)[x] > V(e)[x]
Vector Clock
1
2
0
1
2
2
V(e)
V(e’)
1
2
0
1
0
2
V(e)
V(e’)


• Comparare due vector
clock associati a due
e  e’
eventi distinti permette di
capire la relazione che
lega i due eventi (se uno
precede l’altro o se sono
concorrenti)
e || e’
• Associare vector clock ad
eventi  timestamping
vettoriale
Timestamping vettoriale\implementazione
Un sistema di vector clock è formato da n vettori di interi V ad n
componenti, uno per ogni processo. La componente Vi[x] indica il
numero di eventi del processo Px osservati dal processo Pi. In
particolare, ogni processo Pi i[1,..,n] gestisce un vettore di interi
Vi[1…n] (inizializzato a [-,-,…,0,…,-]) in base alle seguenti regole:
1.
quando Pi processa un evento, incrementa Vi[i] di una unità e
poi associa un timestamp T all’evento il cui valore è pari al
valore corrente di Vi;
2.
quando Pi esegue un evento di trasmissione, allega al msg il
timestamp di quell’evento ottenuto dalla regola 1;
3.
quando arriva un msg a Pi da Pj con un timestamp T, Pi esegue
la seguente operazione: x[1,…,n]: Vi[x]:=max(Vj[x],T[x]),
quindi esegue l’evento di ricezione (esegue la regola 1);
Timestamping vettoriale\esempio
1
2
3
4
5
6
-
-
3
3
3
3
-
-
2
2
2
2
j-esimo evento
eji del processo Pi
P1
e11
e31
e21
e41
e51
e61
l
P2
-
-
-
-
-
1
2
3
4
5
-
2
2
2
5
e32
e42
e52
e12
e22
5
6
5
e62
5
m
7
k
5
e72
e14 || e35
-
-
-
-
-
5
-
-
-
4
4
7
1
2
3
4
5
6
P3
e13 e23
e33
e43
e53
Timestamp
vettoriale associato
all’evento dal
processo
e63
e13  e26
Il concetto di knowledge
•
Assumiamo che la “knowledge” sia una collezione di fatti. Con
un’appropriata codifica una quantità finita di “knowledge” può essere
rappresentata da un intero.
•
La “knowledge” che un processo ha di se stesso è rappresentata da questo
intero.
•
Assumiamo che un processo “non dimentica mai”, cioè che la knowledge
aumenti con il tempo per ogni processo. Inoltre l’unico modo in cui la
knowledge può essere comunicata a differenti processi è attraverso
messaggi. Se ogni processo include tutto ciò che sa in un messaggio e il
ricevente aggiorna la propria knowledge alla ricezione dello stesso, allora il
ricevente avrà più knowledge sia rispetto al mittente che rispetto a se
stesso prima di ricevere il messaggio. Ma questo meccanismo è quello dei
logical clock!
•
Se un processo vuole sapere non solo ciò che lui sa ma anche cosa gli altri
processi sanno, questa “knowledge” deve essere codificata con un vettore
di dimensione pari al numero dei processi. Vector clock!
•
E’ naturale chiedersi se clock con dimensione superiore possano fornire ai
processi più “knowledge”. La risposta è ovviamente si.
Matrix clock
• Matrix clock, ossia un vettore di dimensione n di vector clock.
Codifica un livello superiore di knowledge rispetto a un vector clock.
• L’idea è che l’elemento della matrice (i,j) rappresenta ciò che il
processo sa a proposito di ciò che il processo pi sa a proposito del
processo pj.
• Se pi nel suo matrix clock ha tutta la colonna relativa a se stesso
(colonna i) maggiore di un certo k, allora può concludere che tutti
sanno che pi è arrivato almeno all’evento k.
• Questo meccanismo è utile quando si vuole assicurare che una
certa informazione venga ricevuta da tutti i processi (in situazione di
comunicazione “incerta”, es. perdita di messaggi). In questo caso il
mittente pi può rilevare se l’informazione è stata ricevuta da tutti i
processi (informazione stabile) ispezionando la colonna i del matrix
clock. In caso affermativo può scartare la suddetta informazione (sa
che non la deve reinviare più).
Timestamping con matrix clock\implementazione
Un sistema di matrix clock è formato da n matrici M di interi di
dimensione nxn. In particolare, ogni processo Pi gestisce una matrice
Mi[1…n] (con tutte le componenti inizializzate a –, tranne Mi[i,i]=0) in
base alle seguenti regole:
1. Quando Pi processa un evento, Mi[i,i] si incrementa di una
unità e quindi associa un timestamp T all’evento il cui valore
è pari al valore corrente di Mi;
2. Quando Pi esegue un evento di trasmissione di un
messaggio, egli allega al messaggio il timestamp di
quell’evento ottenuto dalla regola 1;
3. Quando arriva un messaggio a Pi da Pj con allegato un
timestamp T, Pi esegue le seguenti operazioni:
1.
2.
3.
x[1,…,n] e x≠i: Mi[x,*]:=max(Mi[x,*],T[x,*])
y[1,…,n]: Mi[i,y]:=max(Mi[i,y],T[ j,y])
esegue l’evento di ricezione (esegue la regola 1).
Timestamping con matrix clock\esempio
0 - - -
-
1 1 - 1 - - -
2 1 2
- 1 - 1 2
3 1 2
- 1 - 1 2
p1
- - - 0 - - -
- - - 1 - - -
3 1 2
3 2 2
- 1 2
m
p2
m
- - - - - - 0
p3
Assunzione
di topologia
p2
p1
p3
- - - 1 - 1 1
- - - 1 - 1 2
Nota che p2 ora sa
che sia p1 che p3
hanno ricevuto il
messaggio m!
Tempo Logico e Algoritmi distribuiti
• Abbiamo visto tre meccanismi per ordinare eventi in un
sistema distribuito.
• Questi meccanismi sono utili per sviluppare algoritmi
distribuiti dato un certo problema.
• Es. l’algoritmo di Lamport per la mutua esclusione
utilizza il timestamping scalare mentre l’algoritmo che
implementa la comunicazione ordinata causale utilizza il
timestamping vettoriale. La rilevazione della stabilità dei
messaggi è un problema in cui viene utilizzato il matrix
clock.
Causal Broadcast
• Causal broadcast: per ridurre l’asincronia dei canali di comunicazione
percepita dai processi dell’applicazione.
• Garantisce che l’ordine in cui i processi consegnano i messaggi al livello
applicativo non possano violare l’ordine indotto dalla happend-before dei
corrispondenti eventi di broadcast.
• Specifica:
– Se 2 messaggi di broadcast m e m´ sono tali che broadcast(m) —>
broadcast(m´), allora ogni processo deve consegnare m prima di m´.
– Se i broadcast di m e m´ sono concorrenti, allora i processi sono liberi di
consegnare m e m´ in qualsiasi ordine.
Implementazione basata su vector clock
 Modello di sistema: asincrono, no guasti
 ogni processo Pi gestisce un vector clock VCi che traccia la conoscenza corrente del
numero di messaggi che ogni processo ha inviato. In particolare VCi[j] rappresenta la
conoscenza del numero di messaggi che Pj ha inviato inbroadcast e consegnati da Pi
 Ogni messaggio m ha in piggyback un timestamp m.VC, che rivela quanti messaggi
ogni processo ha inviato in broadcast nel passato causale del broadcast di m
 un processo ricevente Pi deve ritardare la consegna di un messaggio m fino a che
tutti i messaggi inviati in broadcast nel passato casaule di m sono consegnati da Pi.
Causal Broadcast\implementazione
Causal Broadcast\esempio
Quando m´ arriva a P2, la sua consegna deve essere ritardata
poichè m´ è arrivato a P2 primadi m, e l’invio in broadcast di m
precede causalmente m´.
Causal Broadcast\corretezza
SAFETY.Dobbiamo dimostrare che
Se 2 messaggi di broadcast m e m´ sono tali che
broadcast(m) —> broadcast(m´), allora ogni processo
deve consegnare m prima di m´
Dim. Per assurdo. Supponi che broadcast(m) —>
broadcast(m´), e che esista un processo p che consegna
m´ senza aver prima consegnato m
• Caso 1. Messaggi inviati dallo stesso processo pi.
• Caso 2. Messaggi inviati da processi diversi
Causal Broadcast\corretezza
•
•
Caso 1. m.Vi[i] <m’.Vi[i] (terza riga della procedura di broadcast)
Un processo ricevente che riceve m’ lo consegna solo se è verificata la condizione di
delivery. Se la condizione di delivery è verificata significa che sicuramente p ha
consegnato tutti i messaggi che pi ha inviato prima di m’. Poichè i vector clock sono
unici per ogni messaggio (due diversi messaggi hanno timestamp diversi e due
timestamp diversi sono associati a messaggi diversi), allora pi ha già consegnato m.
Contraddizione.
Caso 2. Induzione sulla relazione d’ordine happened-before. K indica la distanza tra
due eventi, nei termini del numero di eventi compresi per l’ordine causale tra i due
eventi
•
–
Supponi k=0, i.e. broadcast(m)broadcast(m’) e non esiste alcun evento di broadcast
broadcast(m’’) t.c. broadcast(m)broadcast(m’’) e broadcast(m’’)broadcast(m’). Se un processo
pj ha fatto il broadcast di m’’ allora ha consegnato m (visto che sono in relazione), ciò significa che
Vj[*]>=m.Vi[i] alla consegna di m. Quando pj invia m’ il timestamp associato è tale che: m’.V>=m.V.
Quindi un processo ricevente (come sopra) non può consegnare m’ se non ha già consegnato m.
Contraddizione
Per k>1 vale il caso 1, il caso 2 e la proprietà transitiva della happened-before
LIVENESS: ogni messaggio viene alla fine consegnato.
Garantita grazie a:
1) il numero di eventi di broadcast di messaggi che precedono
causalmente un certo evento di broadcast è finito e
2) assunzione di canali affidabili.
Stabilità dei messaggi
•
Considera applicazioni in cui i processi fanno broadcast di operazioni a tutti
gli altri processi, e dove ogni processo deve alla fine ricevere lo stesso
insieme di operazioni che i processi corretti inviano. Questo problema
astrae la nozione di reliable broadcast in cui le operazioni corrispondono a
messaggi.
•
Modello di sistema: crash and network partion (send/receive omission)
•
Quindi per garantire reliable broadcast in questo sistema ogni processo
deve bufferizzare una copia di ogni messaggio che manda o che riceve. In
caso di necessità, es. guasto di un processo p e mancato recapito da parte
di alcuni processi del messaggio m inviato da p , la copia del messaggio m
viene inoltrata da i processi vivi a quelli che non hanno ricevuto m
•
Rapida crescita del buffer! Rischio di overflow
•
Osservazione: Un messaggio consegnato da tutti i processi non è più
necessario. Tale messaggio è chiamato messaggio stabile.
•
I messaggi stabili possono essere eliminati dai buffer.
Protocollo per la rilevazione della stabilità dei messaggi
•
Un protocollo per la rilevazione della message stability gestisce i buffer dei
processi.
Implementazione basata su matrix clock:
 Modello di sistema: (per semplicità)
 canali FIFO
 no guasti
 Gli eventi di broadcast sono gli eventi rilevanti della computazione. Ogni
processo Pi mantiene un matrix clock MCi. MCi[k] indica qual’è la
conoscenza di Pi a proposito dei messaggi consegnati da Pk. In
particolare:
rappresenta la conoscenza di Pi del numero di messaggi che Pk ha consegnato e Pl
inviato; MCi[i][i] rappresenta il numero di sequenza del prossimo messaggio inviato da
Pi. Quindi il minimo valore sulla colonna j di MCi —cioè,
rappresenta la conoscenza di Pi a proposito del numero di sequenza dell’ultimo
messaggio stabile che Pj ha inviato.
Protocollo per la rilevazione della stabilità dei messaggi
 Per propagare stability information, ogni messaggio m che Pi invia
ha in piggyback l’identità del suo mittente (m.sender) e un
timestamp m.VC, indicante quanti messaggi Pi ha consegnato da
ogni altro processo Pl, (m.VC corrisponde al vettore MCi[i][*]).
 Due operazioni aggiornano il buffer locale (bufferi):
 deposit(m) inserisce un messaggio m nel buffer
 discard(m) rimuove m dal buffer
 Un processo inserisce un messaggio immediatamente dopo la sua
ricezione e lo elimina dal buffer appena il messaggio diventa stabile
 predicato di stabilità per il messaggio m

m.VC[m.sender] rappresenta il numero di sequenza di m
Protocollo per la rilevazione della stabilità dei
messaggi/implementazione
Protocollo per la rilevazione della stabilità dei messaggi/esempio
P3 scarta immediatamente m
dopo la ricezione di m´,
questo perchè
che corrisponde al numero di
sequenza di m.
Alla fine della computazione i
buffer di P1 e P3 contengono
m´e m´´, mentre il buffer di
P2 contiene m´´.
La nozione di stato globale
Stato di un sistema distribuito
• Supponiamo di interrompere una computazione
distribuita mediante interruzione simultanea di
tutti i processi
• Lo stato globale è dato da:
– Stato di ogni singolo processo
– Contenuto di ogni canale di comunicazione
• Sapendo lo stato globale si potrebbe, ad
esempio, riconoscere se il sistema è o no in
deadlock
Stato globale e asincronia
• In un sistema asincrono non esiste alcun
concetto di simultaneità
• Quindi, nessun processo ha accesso allo stato
globale del sistema
• Per molte applicazioni è sufficiente catturare lo
stato globale avvenuto nel passato (es. per
recovery, per rilevare la perdita di un token)
• Ciò viene fatto attraverso un algoritmo chiamato
global snapshot
Stato Globale/definizione
• Stato locale: lo stato locale del processo Pi dopo aver
eseguito l’evento eik si denota con sik. Lo stato iniziale si
indica con si0.
s i0
ei 1 s i 1
Pi
• Stato globale: insieme degli stati locali
S=U si per 1  i  n
• Uno stato globale non sempre è consistente
Stato e consistenza/esempio
• Sistema distribuito per un’applicazione di banking costituito da due
siti che mantengono conti per un cliente. L’applicazione ritorna la
somma totale disponibile per il cliente
• Sito A: 300€, sito B: 500€. Somma: 800 €.
• Trasferimento di 200€ da sito A a sito B. La procedura di somma
potrebbe erroneamente ritornare 1000€. Ciò accade quando il
valore al primo sito è usato prima del trasferimento ed il valore al
secondo sito dopo il trasferimento.
• Qual è il problema? I due stati sommati non sono concorrenti
TAGLIO CONSISTENTE
sA0=300
A
sB0=500
B
TAGLIO CONSISTENTE
eA1=send(trasf. 200) sA1=100
sB1=700
eB1=receive(trasf. 200)
TAGLIO INCONSISTENTE
Taglio di una Computazione
• Un taglio (cut) K in una computazione distribuita
è un insieme di storie locali parziali:
K=U hici per 1  i  n
• La frontiera di taglio è l’insieme degli ultimi
eventi eici per (i=1,…,n).
• Per brevità si indicherà un taglio con l’indice
degli eventi della frontiera: K=(c1,c2,…cn)
Taglio di una computazione: esempio
P1
e11
e31
e21
e41
e51
e61
eji
P2
e12
e22
e32
e42
e52
e62
e72
P3
e13 e23
e33
e43
e53
K=(4,7,6)
e63
K
j-esimo
evento del
processo Pi
Taglio(Stato Globale) Consistente
• Un taglio K è consistente se
e,e’: (eK)  e’  e  e’K
• Ogni taglio K=(c1,c2,…cn) è associato ad uno stato
globale S=(s1,s2,…sn)
• Uno stato globale consistente è uno stato che
corrisponde ad un taglio consistente
• I termini stato globale, taglio, snapshot globale sono
intercambiabili
Tagli Consistenti/esempio
P1
e11
e31
e21
e41
e51
e61
eji
P2
e12
e22
e32
e42
e52
e62
e72
P3
e13 e23
e33
e43
e53
K
j-esimo
evento del
processo Pi
e63
K’
Il taglio K=(5,5,5) e quindi lo stato globale S=(s15, s25, s35)
sono consistenti.
Il taglio K’=(4,5,6) e quindi lo stato globale S’=(s14, s25, s36)
sono inconsistenti.
Algoritmo di Snapshot Globale
• E’ un algoritmo in grado di calcolare stati globali (tagli)
consistenti
• La sua naturale applicazione è il monitoring. Per
implementare il monitoring, nel sistema è presente un
particolare processo monitor il cui scopo è costruire uno
stato globale della computazione. Sulla base di questo
stato il sistema potrà eseguire quindi opportune azioni.
• Lo stato calcolato deve essere consistente per essere
significativo.
Global Snapshot/implementazione
• I canali di comunicazione sono FIFO (i messaggi su un canale
arrivano nell’ordine in cui sono stati inviati).
• Ad ogni processo è associato un colore: blu o rosso.
• Un global snapshot corrisponde allo stato globale del sistema
appena prima che i processi diventino rossi.
• Presenza di un messaggio speciale chiamato marker
• Regole:
–
–
–
–
Tutti i processi sono inizialmente blu
Un processo quando riceve un marker registra il suo stato locale
Dopo aver registrato il suo stato locale il processo diventa rosso
Una volta che un processo diventa rosso deve inviare il marker prima di
inviare qualsiasi altro messaggio
• Poiché i canali sono FIFO queste regole assicurano che non
esisterà mai un processo blu che riceverà un messaggio (relativo
alla generica computazione) da un processo rosso. Ciò assicura che
gli stati registrati siano mutuamente concorrenti!
Global Snapshot/esempio
P1
P2
P3
TAGLIO CONSISTENTE
monitor
Registrazione dello stato locale
Invio del messaggio marker
Global Snapshot/esempio
• Se i canali non fossero FIFO potrebbero venire calcolati stati globali
inconsistenti
P1
P2
m
P3
TAGLIO INCONSISTENTE
monitor
• In tal caso infatti un processo blu riceve il messaggio m da un
processo rosso: violazione!