Corso di Laurea Specialistica in Ingegneria Informatica ...unina.stidue.net/Sistemi...

1

Università degli Studi di Napoli Federico II Facoltà di IngegneriaCorso di Laurea Specialistica in Ingegneria Informatica

Corso di

Sistemi DistribuitiProf. Stefano Russo

Comunicazionidi gruppo

Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 2

Sommario

• Comunicazioni di gruppo • Multicast• Reliable multicast• Ordinamenti

- FIFO multicast- Causal multicast- Total multicast

• Implementazione

Riferimenti:

G. Coulouris et al.: Distributed Systems: Concepts and Design, Cap. 12 §4eccetto “Reliable multicast over IP multicast”, IV ed., 2005.


Comunicazioni di gruppo

Gruppo ApertoGruppo Chiuso

Gruppo chiuso: solo i membri possono inviare messaggi in multicastal gruppoGruppo aperto: anche i non membri possono inviare messaggi in multicastal gruppo

2


Comunicazioni di gruppo tolleranti ai guasti e/o ordinate

�Obiettivo�Assicurare che i processi possano scambiare messaggi

di gruppo anche in presenza di fallimenti dei canali dicomunicazione e/o dei processi stessi.

e/o�Assicurare che i messaggi inviati a un gruppo siano

ricevuti in maniera ordinata


Consegna affidabile dei messaggi

�Principali strategie:�Error Masking

⌧ridondanza spaziale

⌧ridondanza temporale

�Error Detection and Recovery⌧basata suacknowledgements(acks) e timeout


Error Masking (1/3)

�Ridondanza Spaziale: I processi sono connessi concollegamenti ridondanti

�Per mascherarek omissioni, occorronok+1 collegamenti

3


Error Masking (2/3)

�Ridondanza temporale: il messaggio viene inviato più volte

�Per mascherarek omissions, il messaggio deve essere inviatok+1 volte


Error Masking (3/3)

�In entrambi i casi si pone il problema dei messaggiduplicati: essi devono essere scartati dal ricevente

�È difficile in generale trovare il giusto compromessotra semplicità direcoverye consumo di banda.


Error detection e recovery

�Gli ackpossono essere inviati quando:� Un messaggio viene ricevuto (positive ack, v. figura)� Un timeoutscade al ricevente, che decreta la perdita di un

messaggio (negative ack)

4


Schemi per l’invio dei messaggi ack (1/2)

�Nello schema con positive ack, un messaggio viene ritrasmesso se non viene ricevuta una conferma al mittente entro un timeoutpredefinito. � La failure viene individuata più rapidamente in caso di

traffico sporadico


Schemi per l’invio dei messaggi ack (2/2)

�Nello schema con negative acks, il ricevente richiede una ritrasmissione inviando un acknegativo�Minimizza il traffico di rete ma richiede

l’implementazione di uno dei seguenti meccanismi:⌧Numerazione dei messaggi, in maniera tale da poter richiedere

la ritrasmissione di un particolare messaggio (se ad esempio viene ricevuto il messaggio i ma non il messaggio i-1)

⌧Una strategia time-triggered in maniera tale che il ricevente sappia quando deve ricevere un messaggio.


Livelli di affidabilità

�Livelli di affidabilità in comunicazioni multicast: �Unreliable multicast– Nessuno sforzo per superare

failures dei canali di comunicazione; il multicast èaffidabile se lo sono i canali e il mittente.

�Best-effort multicast– Il mittente compie qualche azione per assicurare la consegna del messaggio, come ad esempio ritrasmettere lo stesso, ma non ci sono garanzie

�Reliable multicast– I partecipanti (membri del gruppo) si coordinano per garantire che il messaggio venga consegnato a tutti i destinatari corretti.

5


Basic Multicast

�2 primitive: B-multicaste B-deliver�Garantiscono che un processo corretto prima o poi riceverà il

messaggio, a patto che il mittente non fallisca�La primitiva di B-multicastpuò essere implementata

utilizzato una primitiva per la comunicazione punto-punto su canale affidabile:� B-multicast(g,m):for each process p ∈∈∈∈ g, send(p,m)� B-receive(m) at p:B-deliver(m) at p

� Soffre del problema dell’ack-implosion� Spreca larghezza di banda� … e comunque il mittente può fallire in ogni istante

durante l’esecuzione del B-multicast!


Reliable Multicast

�Hadzilacos e Toueg (1994), Chandra e Toueg (1996)

�Soddisfa le seguenti proprietà:� Integrity – un processo correttop riceve m al più un

volta. Inoltre, p ∈∈∈∈ group(m)e m è stato inviato via multicast da sender(m)

� Validity – se un processo corretto p invia m in multicast, prima o poi riceveràm

� Agreement– se un processo corretto riceve m, allora tutti i processi corretti in group(m)prima o poi riceverannom


Uniform reliable multicast

�Le definizioni delle proprietà del reliable multicastfanno riferimento a processi corretti (cioè che non falliscono mai).

�Una proprietà valida a prescindere dal fatto che i processi siano corretti o meno si dice uniforme.

�In particolare si ha:� Uniform agreement– se un processo (corretto o

meno) ricevem, allora tutti i processi corretti in group(m)prima o poi riceverannom

6


Implementazione del Reliable Multicast con B-multicast (1/3)


Implementazione del Reliable Multicast con B-multicast (2/3)

• Questa implementazione è corretta in un sistema asincrono, ma inefficiente (il messaggio è inviato |g| volte a ciascun processo)

L’implementazione soddisfa le proprietà del reliable multicast:Integrità : discende dall’integrità dei canali di comunicazioneValidità : è evidente che un processo corretto prima o poi fa il B-delivera sé stessoAccordo: discende dal fatto che ogni processo corretto esegue B-multicastdopo B-deliver. Se dunque un processo corretto non effettua R-deliver, ciò può essere dovuto solo al fatto che non ha fatto B-deliver; ciò può sussistere solo se nessun altro processo corretto ha fatto il B-deliver: in tal caso nessuno faràR-deliver


Implementazione del Reliable Multicast con B-multicast (3/3)L’implementazione soddisfa anche la proprietà di uniform agreementSe ad esempio un processo non è corretto e va in crashdopo aver effettuato R-deliver, poiché in precedenza ha sicuramente effettuato B-deliver, nondimeno dunque tutti i processi corretti riceveranno il messaggio.

N.B.: Se si invertono le istruzioni ‘R-deliver m’ e ‘ if(q≠p) then B-multicast(g,m) endif’, l’implementazione non soddisfa più la proprietà di uniform agreement.

7


Ordinamento FIFO

�Se un processo corretto invia in multicasti messaggim e poim’ , allora ogni processo corretto che riceveràm’ avrà già ricevutom

�Versione uniforme: idem senza ‘corretto’

F3

F1

F2

P1 P2 P3

tempo


Ordinamento causale (1/2)

�Semulticast(g,m) →multicast(g,m’), dove → è la relazione happened-before nell’ambito del gruppo g, allora ogni processo correttoche riceveràm’ avràgià ricevutom

�Versione uniforme: idem senza ‘corretto’P 1 P2 P 3

C3

C1

C2 tempo


Ordinamento causale (2/2)

�L’ordinamento causale implica quello FIFO, poichégli invii di uno stesso processo sono in relazione HB

�L’ordinamento causale estende l’ordinamento FIFO con l’ordinamento della ricezione dei messaggi che, pur inviati da processi diversi, sono in relazione di potenziale causalità� Se un processo p invia in multicastun messaggio m ed

un processo p’≠p riceve m prima di inviare in multicastm’ , allora nessun processo corretto riceve m’ a meno che non abbia già ricevuto m

8


Ordinamento totale

�Se un processo corretto riceve i messaggi m e poim’ , allora ogni altro processo corretto che ricevem’ avràgià ricevutom

�Uniform Version:idem senza ‘corretto’

�L’ordinamento totale nonimplica quello FIFO néquello causale

T2

T1

P1P2 P3

tempo


Confronto degli ordinamenti

tempo

� NB: nell’esempio i messaggi TO sono ricevuti nell’ordine opposto rispetto all’invio: la definizione di TOM richiede infatti che l’ordine sia lo stesso per tutti, ma può essere arbitrario

F3

F1

F2

T2

T1

P1 P2 P3

C3

C1

C2


Un approccio modulare ai protocolli di multicast

ReliableMulticast

FIFO ReliableMulticast

CausalReliable Multicast

AtomicMulticast

FIFO AtomicMulticast

Causal AtomicMulticast

[ da Hadzilacos e Toueg - 1994 ]

Total Order

Total Order

Total Order

FIFO Order FIFO Order

Causal Order Causal Order

9


Esempio: bulletin board

Bulletin board: OS

Item From Subject

23 A.Hanlon Mach

24 G.Joseph Microkernels

25 A.Hanlon Re: Microkernels

26 T.L’Heureux RPC performance

27 M.Walker Re: Mach

end

Un gruppo per argomento; gli utenti si sottoscrivono agli argomenti di interesse.Un utente invia un messaggio su un argomento � broadcastal gruppo.Serve la semantica del reliable multicastse si vuole garanzia che tutti gli iscritti ricevano i messaggi.Serve la semantica dell’ordinamento FIFO se si vuole che tutti i messaggi inviati da uno stesso utente siano ricevuti nell’ordine di invio.Serve la semantica dell’ordinam. causalese si vuole, ad es., che il messaggio “Re: Microkernels” sia ricevuto dopo il messaggio “Microkernels” cui si riferisce.Serve la semantica dell’ordinam. totale se si vuole che la numerazione dei messaggi sia la stessa per tutti gli utenti.


Implementazione dell’ordinamento FIFO

� L’ordinamento si realizza mediante l’utilizzo di numeri di sequenza

� Assunzione: i gruppi nonsi sovrappongono

� Sp – contatore dei messaggi inviati dal processo p al gruppogRq - numero di sequenza dell’ultimo messaggio deliveredda p, inviato a g da q.

� Hold-Back-Queue(p) – coda dei messaggi fuori sequenza in attesa di essere ricevuti da p

To FO-multicast(m,g):piggy-.back Sp onto m;B-multicast(m,g);Sp = Sp +1;

To FO-deliver(q,m) with m bearingS= Rq +1:

FO-deliver(q,m);Rq = S ;

To FO-deliver(q,m) with m bearingS> Rq +1:

put m in Hold-Back-Queue;wait until S(m) = Rq +1;FO-deliver(q,m);


Implementazione del FIFO Reliable Multicast

�Si può usare la stessa implementazione del FIFO multicast, usando R-multicastal posto di B-multicast

To FO-multicast(m,g):piggy-.back Sp onto m;R-multicast(m,g);Sp = Sp +1;

To FO-deliver(q,m) with m bearingS= Rq +1:

FO-deliver(q,m);Rq = S ;

To FO-deliver(q,m) with m bearingS> Rq +1:

put m in Hold-Back-Queue;wait until S(m) = Rq +1;FO-deliver(q,m);

10


Implementazione dell’ordinamento causale (1/3)

�L’implementazione tiene conto solo delle relazioni HB tra i messaggi multicast, non di quelle tra messaggi diretti (one-to-one) scambiati tra i processi

�Si può far uso di orologi vettoriali (Vector Clocks)�l’elemento i-esimo conta il numero di messaggi inviati dal

processo i-esimo in relazione HB con il prossimo messaggio

�Assunzione: gruppi chiusi non sovrapposti

�Per effettuare il CO-multicast, un processo incrementa il “proprio” elemento nel vettore ed esegue B-multicastal gruppo g del messaggio marcato col vector clock



�Quando pi fa il B-deliverdi un messaggio inviato da pj, prima di effettuare il CO-deliver deve inserirlo nella hold-back queuefinché non ha fatto il CO-deliver di tutti i messaggi in relazione HB con esso

�Pi deve perciò verificare di aver fatto:�il CO-deliverdi tutti i messaggi precedenti inviati da pj, e:

�il CO-deliverdi tutti i messaggi di cui pj aveva fatto il CO-deliverprima di inviare il messaggio in questione

�Queste condizioni possono essere verificate esaminando i vector timestamps dei messaggi ricevuti



NB: il CO-deliverdi un proprio messaggio può essere effettuato immediatamente

11


Implementazione di Causal Reliable Multicast

�Il multicast con ordinamento causale affidabile può essere implementato a partire dalla implementazione del Causal Multicast, usando R-multicastal posto di B-multicast


Implementazione dell’ordinamento totale (1/4)� Basata sulla marcatura dei messaggi con identificatori totalmente

ordinati, in modo che tutti i processi possano prendere le stesse decisioni

� Il deliveryè come per l’ordinamento FIFO, ma i numeri di sequenza si riferiscono al gruppo, non al processo

� Primo metodo: implementazione mediante processo sequenziatore�un messaggio m è inviato sia a g sia a sequencer(g),etichettato con un id

univoco id(m)

�sequencer(g)può coincidere con un membro di g

�sequencer(g)gestisce un numero di sequenza per il gruppo sg, con cui marca i messaggi di cui effettua B-deliver

�sequencer(g)annuncia i numeri di sequenza inviando messaggi di ordinamentoa g tramite B-multicast

�un messaggio resta nella hold-back queuefinché non può esserne effettuato il TO-deliver, in base al suo numero di sequenza


Implementazione dell’ordinamento totale (2/4)

TO-multicastcon sequenziatore

12


Implementazione dell’ordinamento totale (3/4)

� Secondo metodo: Algoritmo ISIS (Birman, 1987), valido per gruppi aperti o chiusi

� I processi concordano collettivamente sui numeri di sequenza, con un algoritmo distribuito

1

1

2

2

1 Message

2 Proposed Seq

P2

P3

P1

P4

3 Agreed Seq

3

3Ogni ricevente propone il numero di sequenza al multicaster, che genera il numero “agreed”

Ogni processo q di g possiede:Aq

g: il più alto numero di sequenza finora convenuto Pq

g: il più alto numero di sequenza finora proposto dallo stesso q


Implementazione dell’ordinamento totale (4/4)Ogni ricevente propone:

Pqg:=Max(Aq

g,, Pqg)+1

e assegna temporaneamente al messaggio il numero proposto, inserendolo nella hold back queue; questa è ordinata con il valore più piccolo in testa.

Il multicasterraccoglie le proposte e seleziona il valore maggiore a, quindi effettua B-multicast<i,a> (i è l’id univoco con cui il multicaster ha etichettato m)

Ogni ricevente assegna:Aq

g:=Max(Aqg, a)

e associa il valore a al messaggio, quindi riordina la hold-back queue se il valore convenuto è diverso da quello proposto. Quando al messaggio in testa alla coda viene assegnato lo stesso numero proposto, viene inserito in una delivery queue.


Implementazione del Causal Total Multicast

�Se si combina l’algoritmo per l’ordinamento causale (CO) con quello per il multicasttotalmente ordinato (TO) basato sul sequencersi ottiene un ordinamento che è ordinato sia causalmente sia totalmente (C&TO)�il sequenziatore deve fare il deliverysecondo l’ordinamento causale, e il

multicastdei numeri di sequenza dei messaggi nell’ordine con cui li riceve

�i processi nel gruppo di destinazione non effettuano il deliverprima di aver ricevuto un messaggio orderdal sequenziatore eil messaggio è il prossimo nella sequenza

�in tal modo, poiché il sequencereffettua il deliver in ordine causale, e tutti gli altri processi lo effettuano nell’ordine del sequencer, l’ordinamento è sia totale sia causale

Corso di Laurea Specialistica in Ingegneria Informatica ...unina.stidue.net/Sistemi...

Documents

Transcript of Corso di Laurea Specialistica in Ingegneria Informatica ...unina.stidue.net/Sistemi...