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)– ei

k, k-simo evento generato da Pi

• Storia di una computazione– Storia locale: sequenza eventi generati da un singolo processo h1= e1

1 e1

2 e1

3 e1

4 e1

5 e16

– Storia locale parziale: prefisso della storia locale h1m= e1

1 … e1

m

– Storia globale: insieme delle storie locali H = hi per 1 i n

• L’evoluzione di una computazione può essere visualizzata con un diagramma spazio-tempo.

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 timestampingtimestamping: –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). (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). (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.1-10 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

• 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:

– (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 ae 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...

fast clock

slow clock

perfect clock

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

mtp 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

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.

747

7399

9

3

Network Time Protocol (NTP)

1

2

3

2

3 3

• 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

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

Ti

Ti-1Ti-2

Ti- 3

Server B

Server A

Time

m m'

Time

• 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

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)

NO in un sistema distribuito asincrono: clock diversi e impossibilità di sincronizzarli

Il tempo in un sistema asincrono

Tempo Fisico: proprietà globale… osservabile?

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:

gli eventi e ed e’ appartengono allo stesso processo ed e accade prima di e’;

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;

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: e32e2

2, e23e1

3 e quindi e32 e1

3, mentre gli eventi e2

1 e e33 sono concorrenti.

e11 e2

1 e31 e4

1 e51 e6

1

P1

e12 e2

2 e32 e4

2 e52 e6

2e7

2

P2

e13 e2

3 e33 e4

3 e53

e63

P3

eji

j-esimo evento del processo Pi

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

e11 e2

1 e31 e4

1 e51 e6

1

P1

e12 e2

2 e32 e4

2 e52 e6

2e7

2

P2

e13 e2

3 e33 e4

3 e53

e63

P3

eji

j-esimo evento del processo Pi

k Timestamp scalare associato

all’evento dal processo

1 2 5 6 7 8

1 3 4 5 8 9 10

1 2 3 6 7 11

e14

|| e35 : hanno timestamp diversi

e32

e13

e31

|| e11 : hanno stesso timestamp

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

• Comparare due vector clock associati a due eventi distinti permette di capire la relazione che lega i due eventi (se uno precede l’altro o se sono concorrenti)

• Associare vector clock ad eventi timestamping vettoriale

2

1

0

2

1

2

V(e) V(e’)

e e’

2

1

0

0

1

2

V(e) V(e’)

e || e’

Timestamping vettoriale\implementazione

Un sistema di vector clock è formato da n vettori di interi V ad n componenti, uno per ogni processo. La componente V i[x] indica ilnumero 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 V i[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

e11 e2

1 e31 e4

1 e51 e6

1

P1 eji

j-esimo evento del processo Pi

l Timestamp vettoriale associato

all’evento dal processo

e12 e2

2 e32 e4

2 e52 e6

2 e72

P2

e13 e2

3 e33 e4

3 e53

e63

P3

1

-

-

2

-

-

3

3

2

4

3

2

5

3

2

6

3

2

-

1

-

-

2

2

-

3

2

-

4

2

-

5

5

565

5

7

5

-

-

1

-

-

2

-

-

3

-

4

4

-

4

5

5

7

6

m

k

e14

|| e35

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 M i[i,i]=0) inbase 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. x[1,…,n] e x≠i: Mi[x,*]:=max(Mi[x,*],T[x,*])

2. y[1,…,n]: Mi[i,y]:=max(Mi[i,y],T[ j,y])3. esegue l’evento di ricezione (esegue la regola 1).

Timestamping con matrix clock\esempio

- -

- - -

- - -

0

- -

- 0 -

- - -

-

- -

- - -

- - 0

-

- -

- 1 -

- - -

-

1 1 -

- 1 -

- - -

- - -

- 1 -

- 1 1

- - -

- 1 -

- 1 2

2 1 2

- 1 -

- 1 2

3 1 2

- 1 -

- 1 2

3 1 2

3 2 2

- 1 2

Nota che p2 ora sa che sia p1 che p3 hanno ricevuto il messaggio m!

Assunzione di topologia

p2

p3

p1

m

m

p1

p2

p3

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

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´´.

Protocollo per la rilevazione della stabilità dei messaggi/esempio

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 locale: lo stato locale del processo Pi dopo aver eseguito l’evento ei

k si denota con sik. Lo stato iniziale si

indica con si0.

• Stato globale: insieme degli stati locali

S=U si per 1 i n

• Uno stato globale non sempre è consistente

Stato Globale/definizione

Pisi

0 ei1 si

1

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

A

B

sA0=300

sB0=500

eA1=send(trasf. 200)

sB1=700

sA1=100

TAGLIO CONSISTENTE

TAGLIO INCONSISTENTEeB1=receive(trasf. 200)

TAGLIO CONSISTENTE

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 ei

ci 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

e11 e2

1 e31 e4

1 e51 e6

1

P1

e12 e2

2 e32 e4

2 e52 e6

2e7

2

P2

e13 e2

3 e33 e4

3 e53

e63

P3

eji

j-esimo evento del processo Pi

K

K=(4,7,6)

Taglio(Stato Globale) Consistente

• Un taglio K è consistente see,e’: (eK) 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

e11 e2

1 e31 e4

1 e51 e6

1

P1

e12 e2

2 e32 e4

2 e52 e6

2e7

2

P2

e13 e2

3 e33 e4

3 e53

e63

P3

eji

j-esimo evento del processo Pi

K

Il taglio K=(5,5,5) e quindi lo stato globale S=(s15, s2

5, s35)

sono consistenti.

Il taglio K’=(4,5,6) e quindi lo stato globale S’=(s14, s2

5, s36)

sono inconsistenti.

K’

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

P2

P3

Registrazione dello stato localeInvio del messaggio marker

P1

monitorTAGLIO CONSISTENTE

Global Snapshot/esempio

P1

monitor

• Se i canali non fossero FIFO potrebbero venire calcolati stati globali inconsistenti

• In tal caso infatti un processo blu riceve il messaggio m da un processo rosso: violazione!

P2

P3

m

TAGLIO INCONSISTENTE