Universit`a degli Studi di Roma “La Sapienza”

Universit` a degli Studi di Roma

“La Sapienza”

Facolt` a di Ingegneria

Tesi di Laurea in Ingegneria Informatica

sessione estiva - Luglio 2005

Valutazione delle prestazioni di algoritmi peer-to-peer per

la manutenzione della connettivit`a in sistemi dinamici

Sirio Scipioni

Relatore: Prof. Roberto Baldoni Revisore: Prof. Fabrizio d’Amore

Co-relatore: Ing. Sara Tucci Piergiovanni

Indice

Introduzione 1

1 Group Membership Deterministica 5

1.1 Modelli di Sistema . . . 5

1.1.1 Sincronia . . . 6

1.1.2 Guasti dei Processi . . . 7

1.1.3 Guasti della Comunicazione . . . 8

1.1.4 Topologia della Rete . . . 9

1.1.5 Determinismo contro Randomizzazione . . . 9

1.2 Group Membership per LAN . . . 10

1.2.1 Modello matematico . . . 11

1.2.2 Propriet`a di safety . . . 12

Ordine dei View Identifier . . . 12

Evento di vista iniziale . . . 13

1.2.3 Partitionable e Primary Component Membership Service . . . . 14

1.2.4 Propriet`a di liveness . . . 15

Raffinare il modello . . . 16

Eventually perfect failure detector . . . 17

Precisione e Accuratezza della Membership . . . 18

1.3 Group Membership per WAN . . . 20

1.3.1 WAN e MNS . . . 21

1.3.2 Un’implementazione di MNS: Xpand . . . 22

Problematiche d’implementazione . . . 23

Network Event Notification Service . . . 24 iii

2 Gossip-Based Group Membership 27

2.1 Caratteristiche generali dei protocolli gossip-based . . . 27

2.1.1 I gossip-based e la Membership . . . 28

2.2 Lightweight Probabilistic Broadcast . . . 30

2.2.1 Messaggi di gossip e Strutture dati . . . 30

2.2.2 Procedure . . . 32

2.2.3 Dinamismo di Π . . . 34

2.2.4 Ottimizzazioni . . . 35

Rimozione dei messaggi con modalit`a Age-Based . . . 35

Rimozione dei membri con modalit`a Frequency-Based . . . 36

2.3 Scalable algorithm for local-view maintenance . . . 37

2.4 Scalable Membership Protocol: SCAMP . . . 39

2.5 CYCLON . . . 39

2.5.1 Funzionamento base . . . 40

2.5.2 Aggiungere nodi . . . 41

2.5.3 Rimuovere nodi . . . 41

3 P2P Membership per WAN 43 3.1 SCAMP . . . 44

3.1.1 Caratteristiche base di SCAMP . . . 45

Subscription . . . 46

Unsubscription . . . 49

Recupero dall’isolamento . . . 50

3.1.2 Meccanismi per ribilanciare i grafi . . . 53

Lease . . . 53

Indirection . . . 54

3.2 DET . . . 55

3.2.1 Modello di Sistema . . . 56

3.2.2 Specifica del Membership Service Notification . . . 57

Specifica . . . 57

Risultati di impossibilit`a . . . 58

Il problema di circolarit`a . . . 59

3.2.3 Implementazione . . . 60

Inizializzazione . . . 61

3.2.4 Messaggi e Strutture dati . . . 61

INDICE v

Strutture dati . . . 61

Messaggi . . . 62

3.2.5 Algoritmo di Subscription . . . 63

3.2.6 Algoritmo di Unsubcription . . . 64

3.2.7 Tecniche per ottenere partial view scalabili in DET . . . 66

Approccio Statico . . . 66

Approccio Adattativo . . . 67

4 Valutazione Sperimentale 69 4.1 Risultati sperimentali senza Bootstrapping . . . 74

4.1.1 Valutazione della topologia generata da SCAMP e DET . . . 74

Affidabilit`a . . . 75

Scalabilit`a . . . 77

4.1.2 Valutazione della Leave Latency in DET . . . 80

4.1.3 Impatto del meccanismo di Lease in SCAMP . . . 83

4.2 Impatto del Bootstrapping in SCAMP . . . 87

4.2.1 Valutazione del rate dei join in ∆_b . . . 88

4.2.2 Valutazione dell’affidabilit`a della topologia generata da SCAMP 89 5 Conclusioni 93 5.1 Contributo . . . 93

5.2 Sviluppi futuri . . . 94

Elenco delle figure

1.1 Classificazione dei failure model . . . 9

2.1 Ricezione dei messaggi . . . 33

3.1 Management dei messaggi di New Subscription . . . . 47

3.2 Management dei messaggi Forwarded Subscription . . . . 47

3.3 Sottografo ottenuto in una simulazione . . . 52

3.4 Sottografo ottenuto in una simulazione . . . 53

3.5 Management dei messaggi di Join . . . 63

3.6 Management dei messaggi di Leave . . . . 65

3.7 Leave sequenziali e non-sequenziali di tutti i nodi di rango 1 e 2 . . . 66

4.1 Intervalli di tempo in cui sono state divise le simulazioni . . . 70

4.2 Comparazione fra SCAMP e DET dopo ∆_p con un churn rate uguale a 240/∆_p . . . 75

4.3 Comparazione fra SCAMP e DET dopo ∆_p con un churn rate uguale a 240/∆_p . . . 76

4.4 Distribuzione del Degree per DET in t₃ per |contact| = n_tot . . . 77

4.5 Distribuzione del Degree per DET in t₃ per |contact| = n_tot/10 . . . . . 78

4.6 node-degree di ogni nodo per SCAMP in t₃ . . . 79

4.7 Distribuzione del Degree per SCAMP in t₃ . . . 80

4.8 Latenza delle Leave per la topologia pi`u scalabile generabile da DET . . 82

4.9 Numero di conflitti nella topologia pi`u scalabile generabile da DET . . . 83

4.10 Impatto del lease sull’affidabilit`a in SCAMP . . . 84

4.11 Impatto del lease sull’average node degree in SCAMP . . . 85

4.12 Node degree per nodo in SCAMP, con e senza lease . . . 86 vii

4.13 Nodi isolati in SCAMP, con e senza lease . . . 87 4.14 Misure effettuate all’istante t₁ con una dinamica del rate dei join pari a

40/∆_b . . . 88 4.15 Misure effettuate all’istante t₁ con una dinamica del rate dei join pari a

40/∆_b . . . 89 4.16 Valutazione dell’affidabilit`a di SCAMP con ∆_b > 0 e churn rate pari a

200/∆_p . . . 90 4.17 Valutazione del node degree per SCAMP con ∆_b > 0 e churn rate pari

a 200/∆_p . . . 91

Introduzione

All’inizio del 1999, Shawn Fanning, uno studente universitario della North-Eastern University di Boston, diede vita ad un’applicazione di nome Napster. Ne nacque un fenomeno planetario che mostr`o al mondo le potenzialit`a di rete di tipo peer-to-peer.

Un server centrale avrebbe mantenuto una lista dei file che gli utenti erano intenzionati a condividere e tale lista sarebbe stata poi aggiornata dal software degli utenti stessi al momento del log on e del log off dal sistema. Il punto debole di una rete siffatta era situato nel server centrale, il cui spegnimento per questioni legali port`o alla dissoluzione della rete. Da allora diverse applicazioni p2p si sono susseguite per i pi`u svariati scopi ma la tendenza generale `e tuttora rivolta al passaggio ad una struttura completamente decentralizzata, ad un p2p puro, con una molteplicit`a di punti di accesso in grado di permettere, anche nel caso in cui alcuni di essi siano disabilitati, alla rete peer-to- peer di sopravvivere. Un esempio molto famoso di reti di questo tipo `e costituito da GNUTELLA [14].

Il sistema peer-to-peer

Un sistema peer-to-peer `e un sistema distribuito senza alcun controllo centralizzato e non richiede alcun costo aggiuntivo legato ad infrastrutture specifiche per abilita- re la comunicazione diretta fra i client, che possono comunicare direttamente fra loro essendo peer all’interno della rete. Un’applicazione p2p `e connessa in maniera indis- solubile al concetto di dinamicit`a. Ogni analisi di un’applicazione di questo tipo non pu`o prescindere, infatti, da considerazioni legate alla dinamicit`a della rete stessa, pi`u specificatamente all’impredicibilit`a dei tempi di partecipazione dei peer alla rete: ogni peer `e in grado di entrare o uscire dalla rete in istanti arbitrari. L’osservazione delle statistiche online della rete GNUTELLA2, ci mostra come la dimensione della rete vari, nell’arco della giornata, passando dai 250.000 ai 370.000 nodi [7], e non pu`o far altro

1

che rafforzare la convinzione che la dinamica della partecipazione dei peer, o churn, sia una propriet`a intrinseca dei sistemi peer-to-peer.

In base a quanto detto fino ad ora siamo di fronte ad un modello in cui i processi comunicano fra loro facendo ricorso a protocolli di multicast di livello applicativo, al di sopra di una overlay network formata dai peer stessi [17, 23]. A causa del churn l’overlay, in tal modo generata, viene a mutare continuamente e per questo si possono avere disconnessioni di parti pi`u o meno ampie del sistema. Diventa allora cruciale il ruole dei protocolli di management della group membership per il successo del multicast e della rete p2p.

Il problema della Group Membership

Il problema della Group Membership `e un problema di coordinazione distribuita in cui tutti i nodi membri di un certo gruppo devono concordare sulla medesima vista, cio`e sui medesimi nodi correntemente attivi e membri del gruppo stesso. Riassumendo si devono poter soddisfare i seguenti requisiti: ogni nodo deve poter entrare o uscire in qualunque momento dal sistema; ogni processo deve poter contattare gli altri membri ed infine ogni gruppo deve essere considerato finito ma illimitato. ´E evidente come la soluzione di un tale problema ponga fine a tutte le problematiche legate al partizionamento della overlay e alla ricerca di una risorsa all’interno di una rete peer-to-peer. L’ambiente asincrono e la presenza di guasti, e recovery, di processi e di canali rendono molto complesso il compito dei protocolli che implementano un servizio di Group Management. Tali protocolli appartengono a due approcci, uno deterministico e l’altro probabilistico, e devono confrontarsi con due problematiche fondamentali:

• scalabilit`a: l’overhead delle operazioni da eseguire non deve crescere linearmente con la dimensione della rete;

• affidabilit`a: l’overlay deve essere mantenuta connessa indipendentemente dai mutamenti all’interno della rete e della membership.

I protocolli deterministici permettono di definire le propriet`a, dimostrabili anali- ticamente, che sono soddisfatte dal servizio di group membership ma, generalmente, soffrono per quello che riguarda la resistenza ai guasti e la scalabilit`a. I protocolli probabilistici, invece, detti anche epidemici o gossip-based poich´e basati sulla teoria

0intendendo con questo il continuo susseguirsi di ingressi ed uscite.

3

delle epidemie, permettono la diffusione di un messaggio attraverso la scelta casuale dei successivi destinatari tra i processi presenti nella vista locale del mittente. Vengono attualmente considerati dei buoni candidati per quello che concerne il soddisfacimento dei requisiti appena enunciati [4, 25]. Pi`u precisamente la ridondanza dei messaggi inviati da questi protocolli permette di aggirare i guasti presenti all’interno della rete, mentre l’overhead operazionale cresce soltanto logaritmicamente con la taglia della rete stessa. D’altra parte il comportamento di questi protocolli in condizioni di elevata dina- micit`a ha ottenuto, fino ad ora, una scarsa attenzione. Solo recentemente in riferimento ad [3] il problema `e stato analizzato e si `e mostrato come, nel caso del protocollo pre- sentato in [3], la probabilit`a di partizionamento cresca con l’aumentare del churn rate.

Questo fatto `e stato indirettamente confermato dagli autori di uno dei pi`u interessanti protocolli di group membership di tipo gossip-based, chiamato SCAMP [4]. Gli autori affermano che i protocolli di group membership gossip-based sono molto efficienti in sistemi quasi statici, cio`e con churn rate molto bassi.

Contributo

Il contributo di questa tesi consiste nel mostrare, e nel cercare di comprendere, la resistenza al churn rate da parte dei protocolli di group membership in un ambiente p2p, in termini di affidabilit`a e di scalabilit`a. Tale fattore `e stato scarsamente considerato e in questa tesi si `e cercato di mostrare quale influenza pu`o avere sul comportamento di un protocollo di membership la frequenza con cui i membri di un gruppo possono entrare o uscire dal gruppo stesso.

Pi`u specificatamente `e stato comparato il comportamento di SCAMP, protocollo di tipo gossip-based, con un protocollo di group membership deterministico, chiamato DET, che `e in grado, deterministicamente, di mantenere connessa l’overlay. A tal fine, entrambi i protocolli sono stati implementati all’interno di NS-2 in un ambiente di simulazione privo di guasti e teso, pertanto, a metterne in evidenza il comportamento sotto i soli effetti del churn.

Organizzazione

La tesi `e strutturata come segue: nel Capitolo 1 verr`a affrontato in modo teorico il problema della group membership, mostrando in cosa consiste e quali sono le propriet`a che devo essere soddisfatte da un sistema deterministico in grado di risolverlo, e verr`a suddiviso il problema affrontandolo in ambito locale o globale; nel Capitolo 2 sar`a

analizzato l’approccio probabilistico al problema della membership, e descritti alcuni dei pi`u importanti protocolli di group membership che fanno riferimento a questo approccio;

nel Capitolo 3 ci si soffermer`a in particolare sui due protocolli che verranno utilizzati nelle simulazioni oggetto della tesi, mostrando un approccio peer-to-peer al problema della membership in ambito WAN; infine nel Capitolo 4 verranno mostrati e analizzati i risultati ottenuti dalle simulazioni.

Capitolo 1

Group Membership

Deterministica

Un sistema distribuito comprende pi`u processi che comunicano su canali a banda stretta e ad alta latenza, con alcuni processi o canali che possono guastarsi. Avere pi`u processi significa avere pi`u potere computazionale ma richiede che essi siano coordinati.

I sistemi distribuiti sono modellati come un insieme di processi Π ≡ {p₁, p₂, . . . , p_n} che interagiscono scambiando messaggi tramite canali di comunicazione. Esistono una quantit`a di modelli che si distinguono tra loro per le restrizioni pi`u o meno forti im- poste sui componenti (processi e canali di comunicazione) del sistema. Dato un certo problema in un sistema distribuito la soluzione si raggiunge attraverso un opportuno protocollo (cio`e un insieme di opportuni messaggi scambiati tra i processi). Il protocol- lo, dato un certo problema, `e dipendente dal modello di sistema adottato: in generale meno restrizioni si assumono nel modello tanto pi`u un protocollo (se esiste) `e complesso.

Quando si descrive un modello di sistema vengono considerati i seguenti parametri:

la sincronia dei processi e delle comunicazioni, i tipi di guasti dei processi e della comunicazione, la topologia della rete e se i processi sono deterministici o sono processi randomizzati.

1.1 Modelli di Sistema

Un modello di sistema `e una semplificazione della realt`a in cui i problemi devono essere considerati. Un modello per un oggetto `e una collezione di attributi e un insieme di regole che governano come questi attributi interagiscono. Un modello si dice accurato

5

se si avvicina molto alla realt`a dell’ oggetto, un modello si dice trattabile se `e possibile procedere all’ analisi dell’ oggetto. Un buon modello dovrebbe essere accurato e trat- tabile al tempo stesso: gli attributi selezionati devono essere solo quelli che influenzano in modo significativo il fenomeno in esame. In assoluto non esiste un buon modello: un modello pu`o essere adeguato al tipo di problema e ambiente considerato.

1.1.1 Sincronia

La sincronia di un modello `e un attributo relativo alle assunzioni di timing relative al comportamento di processi e canali di comunicazione.

Diciamo che un sistema `e sincrono se soddisfa le seguenti propriet`a:

• Esiste un upper bound conosciuto δ sul ritardo dei messaggi; consiste nel tempo necessario per mandare, trasportare e ricevere un messaggio su un canale.

• Ogni processo p ha un clock locale C_pcon un drift rate ρ ≥ 0 conosciuto e limitato rispetto al tempo reale. Quindi per tutti i p e per tutti gli istanti di tempo t > t⁰,

(1 + ρ)⁻¹≤ C_p(t) − C_p(t⁰)

(t − t⁰) ≤ (1 + ρ)

. Dove C_p(t) `e la lettura del clock C_p all’ istante di tempo reale t.

• Esistono upper bound conosciuti sul tempo richiesto da un processo per eseguire uno step.

In un sistema sincrono `e possibile misurare i time-out dei messaggi, ci`o fornisce un meccanismo per la rilevazione di guasti. Inoltre `e possibile implementare clock ap- prossimativamente sincronizzati, cio`e clock che, oltre ad avere un drift rate limitato, soddisfano anche la seguente condizione: esiste un ² t.c. per ogni t presi due qualsiasi processi p e q vale |C_p(t) − C_q(t)| ≤ ² [20, 8].

Un sistema `e asincrono se non esiste alcun bound su (i) ritardo dei messaggi, (ii) drift del clock, o (iii) tempo richiesto da un processo per eseguire uno step. In realt`a assumere che un sistema sia asincrono `e una non-assunzione. Ogni sistema `e asincrono:

anche un sistema in cui i processi girano in lock-step e in cui la consegna dei messag- gi `e istantanea soddisfa la definizione di sistema asincrono. Questo modello `e quello pi`u usato per diverse ragioni: ha una semantica semplice; un protocollo pensato per girare in un sistema asincrono pu`o essere usato per girare in qualsiasi sistema distri- buito; i sistemi distribuiti aperti, come i sistemi che coprono grandi aree geografiche,

1.1. MODELLI DI SISTEMA 7

o sistemi soggetti a workload variabili e inaspettati imposti dai loro utenti sono fonda- mentalmente asincroni (in questi sistemi le assunzioni sincrone diventano al massimo probabilistiche).

I modelli sincrono e asincrono sono i due estremi di un vasto spettro di possibili modelli. Questi modelli intermedi sono chiamati sistemi parzialmente sincroni. I sistemi parzialmente sincroni si distinguono tra loro a seconda del livello di sincronia assunto.

Ad esempio i processi possono avere velocit`a limitata e clock perfettamente sincronizzati (² = 0) ma ritardo di trasmissione dei messaggi non limitato [11], oppure il ritardo dei messaggi `e limitato ma sconosciuto [12].

1.1.2 Guasti dei Processi

Un processo `e guasto in un’ esecuzione se il suo comportamento devia da quello pre- scritto dall’ algoritmo che sta eseguendo; altrimenti il processo `e corretto. Un failure model specifica in quale modo un processo guasto pu`o deviare dal suo algoritmo. I failure model sono i seguenti [16]:

• Crash: un processo guasto termina prematuramente e non esegue alcuna azione da questo punto in poi. Tuttavia prima di fermarsi si `e comportato in modo corretto.

• Send omission: un processo guasto termina prematuramente, o omette in modo intermittente di inviare dei messaggi che era supposto inviare, o entrambe le cose.

• Receive omission: un processo guasto termina prematuramente, o omette in modo intermittente di ricevere dei messaggi che gli sono stati inviati, o entrambe le cose.

• General omission: un processo guasto `e soggetto a guasti di tipo send omission o receive omission, o entrambi.

• Arbitrary (alle volte chiamato Byzantine o malicious) : un processo guasto pu`o esibire qualsiasi comportamento. Ad esempio cambia stato in modo arbitrario.

• Arbitrary con message authentication: un processo guasto pu`o esibire qualsiasi comportamento ma `e disponibile un meccanismo per l’ autenticazione dei mes- saggi usando unforgeable signature. Un processo soggetto ad un guasto arbitrario pu`o asserire di aver ricevuto un particolare messaggio da un processo corretto,

anche se non l’ ha mai ricevuto. Un meccanismo di autenticazione dei messaggi permette agli altri processi corretti di validare o meno questa asserzione.

I modelli sopra menzionati possono essere applicati sia a sistemi sincroni che asincroni. Tuttavia esistono altri tipi di guasti che sono applicabili solo a sistemi sincroni:

• Timing failure: un processo soggetto ad un timing failure `e un processo che viola una delle assunzioni di sincronia. Un simile processo pu`o guastarsi in uno o pi`u dei seguenti modi:

1. commette un general omission failure;

2. il suo clock locale eccede il bound specificato (clock failure);

3. viola il bound relativo al tempo richiesto per eseguire uno step (performance failure).

Questi failure model possono essere classificati in termini di severit`a. Un modello A

`e pi`u severo di un modello B se l’ insieme di comportamenti di guasto permessi da B `e un sottoinsieme proprio di quello costituito dai comportamenti di guasto permessi da A (Figura 1.1) . Quindi un algoritmo che tollera guasti di tipo A tollera anche guasti di tipo B. I guasti di tipo arbitrario sono i pi`u severi mentre i guasti di tipo crash sono i meno severi.

I timing failures sono pi`u severi dei general omission e meno severi degli arbitrari con message authentication.

Tutti i tipi di guasti che non sono pi`u severi dei timing sono chiamati benign.

Un sistema `e detto f-fault tolerant se continua a soddisfare le sue specifiche anche quando f componenti (in questo caso i processi) sono guasti.

1.1.3 Guasti della Comunicazione

I canali di comunicazione possono essere soggetti ai seguenti tipi di guasti [16]:

• Crash: un canale guasto smette di trasportare messaggi. Prima del crash si `e comportato in modo corretto.

1.1. MODELLI DI SISTEMA 9

$UELWUDU\

$UELWUDU\ZLWKPHVVDJH DXWKHQWLFDWLRQ

7LPLQJRQO\LQ V\QFKURQRXVPRGHO

*HQHUDO2PLVVLRQ

5HFHLYH2PLVVLRQ

6HQG2PLVVLRQ

&UDVK

Benign

Figura 1.1: Classificazione dei failure model

• Omission: un canale guasto omette in modo intermittente di trasportare i messaggi inviati attraverso di esso.

• Arbitrary (alle volte chiamato Byzantine o malicious): un canale guasto pu`o esibire un qualsiasi comportamento. Per esempio pu`o generare messaggi spuri.

Nel caso di sistemi sincroni, si hanno anche:

• Timing failures: un canale guasto trasporta messaggi in modo pi`u veloce o pi`u lento rispetto alle sue specifiche.

1.1.4 Topologia della Rete

La rete di comunicazione pu`o essere modellata come un grafo, dove i nodi sono i processi e gli archi sono i canali di comunicazione tra i processi. Questo modello si adatta sia a reti punto-punto che a reti broadcast. Assunzioni precise sulla topologia di rete possono essere fatte se necessarie quando vengono considerati particolari problemi.

1.1.5 Determinismo contro Randomizzazione

Il comportamento di un processo pu`o essere deterministico o randomizzato. In generale un processo pu`o essere modellato come un automa a stati (anche infinito). La relazione

di transizione di stato di un processo deterministico determina in modo unico lo stato risultante dall’ esecuzione di ogni step sullo stato corrente. In un processo randomizzato l’ esecuzione di un dato step sullo stato corrente porta in uno stato facente parte di un insieme di possibili stati, ed ognuna di tali transizioni ha associata una certa probabilit`a.

Informalmente un processo tira una moneta per determinare quale transizione scegliere.

La solvibilit`a di molti problemi `e fortemente influenzata dalla caratteristica dei processi di essere deterministici o meno.

1.2 Group Membership per LAN

Introdotte le nozioni fondamentali necessarie per comprendere un modello di sistema distribuito, occore passare ad affrontare la problematica fondamentale oggetto di questa tesi: il problema della Group Membership.

Il problema della Group Membership `e un esempio di problema di distributed coordination [28].

L’obiettivo di un Group Membership service `e di mantenere una lista dei proces- si correntemente attivi e connessi al sistema, lista che viene chiamata membership.

L’output del membership service viene chiamato view e consiste, appunto, nella lista dei nodi correntemente attivi e connessi al sistema, identificati da un Id univoco. La complementazione di un servizio di membership cos`ı definito `e data da un servizio di multicast che consegna i messaggi ai processi contenuti nella view, restituita dal Group Membership Service, formando un Group Communication service.

La lista pu`o cambiare con le operazioni di join dei nuovi membri e le uscite dei membri pi`u vecchi, o pi`u semplicemente per guasti occorsi ai processi membri. Quando una lista cambia, il Group Membership service riporta i cambiamenti ai membri del gruppo, installando una nuova view. Il servizio tenta di installare la medesima vista a tutti i modi mutuamente connessi.

Definire in maniera coerente un servizio di group communication non `e un obiettivo semplice, poich´e spesso tali sistemi vengono eseguiti in ambienti asincroni nei quali non

`e possibile risolvere i problemi che definiscono i servizi forniti dal group communication service. In un sistema reale il problema pu`o essere impossibile da risolvere ma si pu`o solo cercare di operare in modo best-effort. Infatti un avversario pu`o forzare un algoritmo di membership deterministico a prendere decisioni che non riflettono la situazione della rete. D’altra parte nelle reti reali pu`o avvenire che le comunicazioni tendano ad essere

1.2. GROUP MEMBERSHIP PER LAN 11

stabili e, temporalmente, a durare per un lungo periodo, in queste situazioni un servizio di group communication che cerca di operare il modo best-effort pu`o avere molto spesso successo

Nella sezione 1.2.2 descriveremo le propriet`a base di safety mantenute da molti sistemi di group communication; nella sezione 1.2.3 confronteremo i due approcci: par- titionable e primary component. Si rimanda per considerazioni pi`u dettagliate a [15].

Vedremo inoltre alcune propriet`a di liveness che per essere soddisfatte richiedono delle assunzioni sul failure detector e sulla rete sottostante. Mentre le propriet`a di safe- ty posso essere pi`u facilmente soddisfatte, le propriet`a di liveness possono non essere ottenibili senza alcune garanzie sulla rete sottostante.

1.2.1 Modello matematico

Indicheremo di seguito con:

P l’insieme dei processi;

M l’insieme dei messaggi;

VID l’isieme degli identificatori delle viste, ordinate parzialmente tramite l’operatore <.

V `e l’insieme delle view consegnate dall’operazione di view chng, definito come VID x 2<sup>P</sup>. In questo modo la vista V ∈ V `e una coppia, i cui elementi verranno indicati con V.id e V.members.

Events Occorrenze degli eventi. L’insieme degli eventi `e definito in questo modo:

{send(p, m) | p ∈ P, m ∈ M} ∪ {recv(p, m) | p ∈ P, m ∈ M} ∪ {view chng(p, V, T ) | p ∈ P, V ∈ V, T ∈ 2^P} ∪

{safe prefix(p, m) | p ∈ P, m ∈ M} ∪ {crash(p) | p ∈ P} ∪ {recover(p) | p ∈ P}

Trace Sequenza finita o infinita di eventi.

Occorre introdurre un’ulteriore definizione sulle viste.

Definizione 1.2.1. (viewof) La vista di un evento t_i, che occorre al processo p, `e la vi- sta consegnata a p in un evento view chng, in modo tale che nessun evento view chng o crash occorre in p tra t<sub>j</sub> e t<sub>i</sub>; la vista `e ⊥ se non ci sono t_j.

Devono essere fatte alcune assunzioni sull’ambiente, per prima cosa che nessun evento avvenga tra un crash ed un recovery.

Assunzione 1.2.1. (Execution Integrity) L’evento successivo che intercorre in un pro- cesso dopo un crash `e un evento di recovery, e l’evento prima di un recovery `e un crash.

Inoltre per distinguere tra messaggi inviati in differenti eventi di invio, supponiamo che ogni messaggio inviato contenga un identificatore unico. In questo modo possiamo richiedere che ogni messaggio sia inviato al pi`u una volta all’interno del sistema. Tale assunzione non `e fondamentale poich´e un servizio di group communication pu`o ottenere il medesimo risultato senza numeri di sequenza ma questi semplificano la presentazione.

Assunzione 1.2.2. (Unicit`a dei Messaggi) Non esistono due differenti eventi di invio con lo stesso contenuto.

1.2.2 Propriet`a di safety

La prima propriet`a di safety richiesta `e che il processo sia sempre membro della sua view.

Propriet`a 1.2.1. (Auto Inclusione) Se un processo p installa la view V allora p `e membro di V. Formalmente:

installs(p,V) ⇒ p ∈ V.members

Poich´e la membership riflette la capacit`a di comunicare con il processo membro della vista, e un processo `e sempre in grado di comunicare con s`e stesso, allora questa propriet`a `e sottesa a tutti i sistemi di comunicazione ed `e presente in tutte le specifiche.

Ordine dei View Identifier

Le propriet`a successive richiedono che gli identificatori delle view che ogni processo installa siano monotonicamente crescenti.

Propriet`a 1.2.2. (Monotonicit`a Locale) Se un processo p installa una vista V dopo aver installato una vista V’ allora l’identificatore di V `e pi`u grande dell’identificatore di V’. Formalmente:

t_i = view chng(p, V, T ) ∧ t_j = view chng(p, V⁰, T⁰) ∧ i > j ⇒ V.id > V⁰.id

1.2. GROUP MEMBERSHIP PER LAN 13

La propriet`a 1.2.2 ha due importanti conseguenze: garantisce che un processo non possa installare la medesima view pi`u di una volta, e che se due processi installino le stesse due view allora lo devono fare nel medesimo ordine.

La propriet`a di Monotonicit`a Locale risulta essere soddisfatta dalla maggioranza dei sistemi di group membership anche se alcuni sistemi possono violare la Monotonicit`a Locale, nel caso in cui un processo vada in crash e esegua il recupero con la medesima identit`a: quando un processo si guasta, si recupera, installa la sua vista iniziale che avr`a un identificatore inferiore rispetto a quello dell’ultima vista che ha installato prima del guasto. Alcune violazioni della Monotonicit`a Locale possono essere causate da un vecchio messaggio che viaggia nella rete se esiste la possibilit`a che possa venire scambiato per uno pi`u recente.

Per rimediare a queste problematiche esistono diverse vie: in Isis [18, 19] un processo che recupera dopo un guasto si rinizializza con un diverso identificatore. `E anche possibile salvare le informazioni su disco prima che venga istallata una nuova vista e recuperare queste ultime in caso di guasto.

Esistono, inoltre, molti metodi per generare identificatori di viste: in Transis [9]

l’identificatore della vista `e un intero positivo, calcolato in base al valore di un contatore locale al processo stesso, e mantenuto da ogni processo. Questo contatore locale `e incrementato ad ogni installazione. Altri esempi pi`u complessi possono essere fatti riguardo l’identificatore: pu`o essere una coppia hp, ci, dove p `e `e il processo che ha creato la vista e c `e il valore del contatore locale di p, oppure un timestamp logico.

L’importanza dei propriet`a di ordinamento delle viste `e evidenziata dall’enfasi che ad essa viene data in molti lavori: ad esempio in [10] viene utilizzata la Monotonicit`a Locale per implementare un servizio di multicast dotato di total order.

Evento di vista iniziale

Abbiamo gi`a visto che in un sistema di comunicazione di gruppo di tipo view-oriented, possono occorrere eventi nel contesto delle viste. Daltra parte, dalle nostre definizioni, questo non accade per tutti gli eventi: eventi che occorro prima del primo view event non sono considerati come occorsi in ogni vista. I servizi di group communication generalmente installano una vista iniziale al momento dello startup o dopo un crash, e cos`ı ogni evento di send, recv e safe prefix occorre in alcune viste.

Propriet`a 1.2.3. (Evento di Vista Iniziale) Ogni evento di send, recv e safe prefix

occorre in alcune viste. Formalmente:

t_i = send(p, m) ∨ t_i = recv(p, m) ∨ t_i = safe prefix(p, m) ⇒ viewof (t_i) 6=⊥

La vista iniziale pu`o essere determinata in due modalit`a:

• All’avvio, i processi usano il servizio di membership per ottenere una vista, come possono fare per ogni altra vista. In tal modo non `e richiesta alcuna conoscenza predefinita del sistema. Alcuni sistemi di group communication utilizzano questa modalit`a, ad esempio Isis.

• Ogni processo decide unilateralmente la sua vista iniziale senza comunicare con gli altri processi. Quest’approccio equivale a possedere una vista iniziale di default ma possedendo un evento esplicito di installazione della vista iniziale.

La vista iniziale pu`o contenere un unico processo oppure pu`o consistere nella lista di tutti i processi che possono appartenere al sistema. In [21] tali possibilit`a vengono chiamate individual startup e collective startup. Bisogna notare, inoltre, che per installare qualunque cosa di differente da una vista dotata di un singolo elemento, un processo deve possedere a priori una conoscenza riguardo gli altri processi del sistema.

1.2.3 Partitionable e Primary Component Membership Service Un servizio di membership pu`o essere di tipo primary component¹oppure partitionable.

In un servizio di membership di tipo primary service, le viste installate da ogni componente del sistema sono totalmente ordinate, in un servizio di tipo partitionable le view sono solo parzialmente ordinate. Un servizio di group communication risulta essere partitionable se il suo servizio di membership `e partitionable altrimenti `e primary component.

Tutte le propriet`a di safety suvviste valgono per entrambe le tipologie di servizio.

Poich´e nelle specifiche viste non compare una propriet`a di ordine totale delle viste, la specifica cos`ı presentata `e, in pratica, una specifica di tipo partitionable. Per specificare un servizio di tipo primary component, occorre aggiungere una propriet`a di safety che impone un total order sulle viste. La propriet`a 1.2.4 richiede che l’insieme delle viste installate in una traccia formi una sequenza tale che due viste consecutive, nella sequenza, si intersecano. La sequenza `e modellata come una funzione dall’insieme delle viste installate all’insieme dei numeri naturali.

1conosciuto anche come primary partition

1.2. GROUP MEMBERSHIP PER LAN 15

Propriet`a 1.2.4. (Primary Component Membership) Esiste una funzione f uno ad uno fra le viste installate in una traccia e l numeri naturali, tale che f soddisfa le seguenti propriet`a:

per ogni view V con f(V) ¿ 1 esiste una view V’, tale che f(V) = f(V’) + 1, e un membro p di V che installa V al posto di V’ (cio`e V `e il successore di V’ nel processo p). Formalmente:

∃f : {V |∃p : installs(p, V )} → N tale che:

(f(V) = f(V’) ⇒ V = V’) ∧

∀V (f (V ) > 1 ⇒ ∃V⁰(f (V ) = f (V⁰) + 1 ∧ ∃p ∈ V.members : installs in(p, V, V⁰))) Questa propriet`a implica che per ogni coppia di viste consecutive, esiste un processo che sopravvive dalla prima vista alla seconda, non andando in crash nel periodo di tempo fra l’installazione delle due viste. In tal modo il processo pu`o convogliare le informazioni riguardo lo scambio di messaggio con i membri della seconda vista.

Il servizio di group membership pi`u conosciuto e studiato del tipo primary compo- nent `e Isis, mentre il primo servizio di membership di tipo partitionable `e stato Transis [33]. Molti altri servizi di membership sono stati sviluppati sulla base delle due tipologie appena viste.

I servizi di tipo partitionable sono stati utilizzati in un’ampia variet`a di applica- zioni, per esempio di resource allocation, di monitoring, di system management o load balancing.

All’opposto applicazioni che mantengono stati condivisi globalmente consistenti usualmente prevengono l’inconsistenza permettendo solo ai membri di una vista, la vista primaria, di aggiornare lo stato condiviso in un determinato. istante. A causa dei benefici di queste applicazioni, alcuni servizi di membership partitionable notificano ai processi se sono in una primary view o meno, in modo tale che le viste primarie soddisfino la propriet`a 1.2.4 Il beneficio di utilizzare un servizio di tipo partitionable per alcune applicazione risulta nel fatto che anche i membri di una vista non-primaria possono accedere ai dati per leggere gli stessi.

1.2.4 Propriet`a di liveness

Occorre specificare, dopo le propriet`a di safety, le propriet`a di liveness di un group membership service poich´e altrimenti le sole propriet`a di safety possono essere soddi- sfatte semplicemente non compiendo alcuna azione. Tramite le propriet`a di liveness verranno inoltre definiti i compiti che devono essere svolti dal servizio. Idealmente si

desidererebbe un servizio di membership che sia preciso, cio`e che consegni una vista che rifletta correttamente lo stato attuale della rete. D’altra parte come si pu`o argomentare relativamente ad una corretta situazione di rete se la situazione `e in continuo mutamen- to? Si pu`o dimostrare che non `e possibile garantire la correttezza in ogni esecuzione senza rafforzare il modello di comunicazione passando da un sistema completamente asincrono ad un modello parzialmente sincrono.

Possono essere date due tipi di definizioni di liveness: il primo valido solo per le esecuzioni per cui il sistema eventualmente si stabilizza, intendiamo cio`e che dopo un certo intervallo di tempo nessun processo va in crash o in recovery, le comunicazioni divengono simmetriche e transitive e non avviene nessun cambiamento nella connetti- vit`a di rete; il secondo tipo richiede una forma pi`u debole di liveness nelle esecuzioni instabili.

Nelle esecuzioni in cui il sistema diviene stabile possiamo desiderare che il servizio di membership sia preciso ma non `e possibile implementare alcun servizio preciso in un sistema puramente asincrono e in presenza di guasti.

Per superare questo problema si assume di utilizzare un failure detector esterno e di richiedere di rispettare le propriet`a di liveness solo nelle esecuzioni per cui il failure detector si comporta come un eventually perfect.

Occorre dire che le propriet`a di liveness condizionali cos`ı definite sono garantite solo in alcune esecuzioni e che le condizioni di queste esecuzioni sono esterne dall’implemen- tazione del servizio di membership. Ci`o che otteniamo, dunque, `e che il servizio cerca comunque di essere preciso, non essendo a conoscenza del fatto se ci siano componenti stabili o se il failure detector si comporter`a o meno come eventually perfect.

Raffinare il modello

Dato che le propriet`a di liveness dipendono dalla condizioni di rete e dall’output del failure detector `e necessario estendere il modello presentatato in 1.2.1. per aggiungere le azioni che rappresentano le interazioni con la rete e il failure detector. Tale estensione viene fatta aggiungendo alla lista Events il seguente insieme:

{channel down(p, q) | p, q ∈ P} ∪ {channel up(p, q) | p, q ∈ P} ∪ {net send(p, m) | p ∈ P, m ∈ M} ∪ {net recv(p, m) | p ∈ P, m ∈ M} ∪ {net reachable set(p, S) | p ∈ P, S ∈ 2^P}

1.2. GROUP MEMBERSHIP PER LAN 17

Senza soffermarci a discutere approfonditamente sul significato di queste esten- sioni, invero abbastanza chiaro, e la cui discussione esula dai nostri scopi occorre aggiungere che l’implementazione dell’eventually perfect failure detector richiede un’ulteriore assunzione sulla struttura di rete:

Assunzione 1.2.3. (Live Network) Se esiste un punto, durante l’esecuzione, in cui due processi p e q sono vivi e il canale fra p e q `e up, allora da questo punto in poi ogni messaggio inviato da p eventualmente arriva a q. Formalmente:

alive af ter(p, i) ∧ alive af ter(q, i) ∧ up af ter(p, q, i) ∧ t_i = net send(p, m) → ∃j | t_j = net receive(q, m)

Come suddetto possiamo sperare di ottenere un comportamento ideale del servizio di group membership solo se eventualmente esiste un componente stabile e il failure detector si comporta come un eventually perfect.

Occorre definire cosa si intende per componente stabile

Definizione 1.2.2. (Componente stabile) Un componente stabile `e un insieme di pro- cessi che sono eventualmente sopravvissuti e connessi ad ogni altro, e per i quali tutti i canali fra loro e gli altri processi, che non appartengono al componente stabile, sono down.

Occorre notare che l’esistenza di un componente stabile implica che la comunica- zione, fra i componenti stabili, sar`a eventualmente simmetrica e transitiva ma non si assume che lo sia sempre all’interno del modello.

Eventually perfect failure detector

Tralasciando in questa sezione tutte le considerazioni legate alla teoria dei failure de- tector, e alle loro possibilit`a di implementazione a seconda delle assunzioni di rete, affronteremo soltanto i punti salienti per comprendere le assunzioni fatte e le propriet`a di liveness richieste da un servizio di group membership.

Detto approssimativamente un eventually perfect falure detector `e un failure detec- tor che eventualmente cessa di commettere errori, cio´e per cui esiste un istante t_i dopo il quale il failure detector riflette correttamente la situazione della rete.

Per dare la definizione di eventually perfect failure detector che ci interessa occorer aggiungere la definizione di eventually perfect-like trace.

Definizione 1.2.3. (Eventually perfect-like trace) Il failure detector si comporta in modo simile ad un eventually perfect in una data traccia, se per ogni componente stabile S, e per ogni processo p ∈ S, l’insieme dei processi raggiungibili riportato a p dal failure detector `e eventualmente S.

Detto questo si pu`o finalmente definire l’eventually perfect failure detector.

Definizione 1.2.4. (Eventually perfect failure detector) un eventually perfect failure detector `e un’automa di rete e di failure detector che si comporta in modo simile ad un eventually perfect in ogni traccia.

In generale risulta impossibile implementare un eventually perfect failure detector in un modello completamente asincrono e per questo si deve far ricorso a modelli par- zialmente sincroni per catturare il comportamento della rete. In questi modelli pu`o essere presente un limite superiore alle latenze sulle comunicazioni, o i processi possono misurare il tempo. Eventually perfect failure detector possono essere implementati fa- cilmente in questi modelli o su reti che soddisfino l’assunzione 1.2.3. Le implementazioni di un failure detector utilizzano la rete per inviare o ricevere messaggi, e generano even- ti di net reachable set quando cambiano valutazione riguardo la connettivit`a della rete. Un automa di Network e Failure Detector pu`o essere ottenuto dalla composizione del modulo del failure detector con la rete sottostante, nascondendo le informazioni relative ai messaggi del failure detector.

Precisione e Accuratezza della Membership

Nel discorso fatto fino ad ora si `e affermato pi`u volte che un eventually perfect failure detector corrisponda ad un prerequisito per la liveness. Si pu`o dimostrare, cosa che noi non faremo rimandando a [15] per chi fosse interessato, che un servizio di membership preciso `e difficile da risolvere come un eventually perfect failure detector. Per prima cosa definiamo cosa sia un servizio di membership preciso.

Definizione 1.2.5. (Membership Precisa) Un servizio di membership `e preciso se sod- disfa i seguenti requisiti: per ogni componente stabile S, esiste una vista V , con insieme dei membri l’insieme S, tale che V `e l’ultima vista di ogni processo p in S. Formal- mente:

stable component(S) → ∃V (V.members = S ∧ ∀p ∈ Slast view(p, V ))

1.2. GROUP MEMBERSHIP PER LAN 19

Possiamo ora enunciare le due propriet`a di liveness che interessano un servizio di group membership, tralasceremo in questo scritto le propriet`a che riguardano pi`u stret- tamente l’invio di messaggi e pi`u in generale il servizio di group communication che si pu`o costruire al di sopra di un group membership service [15]. Le propriet`a verran- no specificate per un servizio di group membership di tipo partitionable, e non sono valide per una tipologia di tipo primary component poich´e possono richiedere ai pro- cessi, in alcune situazioni, di installare delle viste anche se questi non sono nel primary component. Le propriet`a di liveness per servizi primary component non verranno spe- cificate perch´e dipendono dalla specifica implementazione e dalla politica utilizzata per garantire la propriet`a 1.2.4.

Propriet`a di liveness per esecuzioni stabili La propriet`a esplicitata di seguito

`e condizionale: deve essere valida nelle esecuzioni per cui vi `e la presenza di una componente stabile S e il failure detector si comporti come un eventually perfect.

Propriet`a 1.2.5. (Liveness: Membership Precision) Se il failure detector si comporta come un eventually perfect, allora per ogni componente stabile S esister`a una vista V , composta dall’insieme S, tale che, per ogni processo p in S, p installer`a V come sua ultima vista. Formalmente:

♦P − like ∧ stable component(S) → ∃V |(V.members = S ∧ ∀p ∈ Slast view(p, V ))

Propriet`a di liveness per esecuzioni prive di componenti stabili La propriet`a di liveness enunciata nel paragrafo precedente ci garantisce che se un componente sta- bile, esister`a eventualmente all’interno del sistema allora il servizio di membership installer`a una vista precisa a tutti i membri. Quando per`o un componente stabile non esiste allora il comportamento che si desidera da parte del servizio di membership viene catturato dalla propriet`a seguente, formulata originariamente in [24]:

Propriet`a 1.2.6. (Membership Accuracy) Se esiste un tempo dopo il quale i processi p e q sono vivi e il canale fra p e q `e up, allora p eventualmente installa una vista che include q ed ogni vista installata successivamente include q.

Membership Accuracy non richiede ai processi di terminare, eventualmente, l’in- stallazione delle viste ed inoltre non implica la propriet`a 1.2.5. D’altra parte, poich´e non esistono componenti stabili, la propriet`a di Membership Accuracy non richiede che i processi siano direttamente connessi ad ogni altro per installare la medesima vista,

o consegnare ogni altro messaggio. Questo fatto diminuisce l’utilizzabilit`a di questa propriet`a per le applicazioni, ad esempio non `e fornita da quei servizi di membership che non installano viste se i componenti stabili non esistono.

Abbiamo ottenuto in questo modo un supporto a sistemi di group communication che fornisce le seguenti due propriet`a:

1. determinare l’insieme dei processi che sono correntemente attivi;

2. assicurare che i processi concordino sul successivo valore di questo insieme.

Le due propriet`a di liveness relative ai servizi di membership hanno trovato le pi`u diverse applicazioni ed implementazioni. Sono state definite in pi`u modi, spesso ren- dendole pi`u deboli per poter, di conseguenza, indebolire i due prerequisiti. Ad esempio Phoenix [6] ricorre ad un failure detector pi`u debole ma permette di garantire soltanto che l’invocazione del protocollo di membership terminer`a senza assicurare che non ven- gano rimossi dalle viste dei nodi corretti. Il problema di tutte queste implementazioni rimane sempre il medesimo: la scalabilit`a, infatti pi`u forti sono i prerequisiti sotto cui si trovano ad operare tali implementazioni pi`u decadranno le prestazioni dei protocolli al crescere delle dimensioni. Ammesso inoltre che le assunzioni fatte conservino la loro validit`a in sistemi di pi`u ampia portata, dove `e difficile immaginare una stabilizzazione della rete o ammettere delle latenze di rete limitate superiormente. Uscendo dall’am- bito ristretto delle LAN rischiamo di tornare nelle condizioni per cui questi servizi di group membership possano solo fare del loro meglio, lavorando in modalit`a best-effort appunto.

1.3 Group Membership per WAN

L’approccio di group membership affrontato fino a questo punto richiede periodi di tempo abbastanza lunghi nel quali il sistema deve stabilizzarsi cio´e:

1. non devono avvenire cambiamenti nella membership;

2. il sistema di rete sottostante deve mostrare un comportamento sincrono.

Ma la scala e la natura intrinsecamente dinamica di molte applicazioni rendono molto arduo ottenere un periodo abbastanza lungo di stabilit`a e sincronia del sistema, inoltre, come `e gi`a stato affermato, gli approcci suddetti manifestano prestazioni che

1.3. GROUP MEMBERSHIP PER WAN 21

degradano significativamente all’aumentare della taglia del gruppo, mentre allo stesso tempo il volume dei messaggi trasmessi cresce. A questi problemi va aggiunto il venire meno della possibilit`a di garantire le assunzioni minime di sincronie necessarie all’im- plementazione dell’eventually perfect failure detector, visto nella precedente sezione, e alla conseguente impossibilit`a di garantire le propriet`a di liveness richieste in una wide-area network.

1.3.1 WAN e MNS

In una wide-area network, e pi`u in generale in una rete che coinvolge un elevato numero di utenti, in particolare si dovranno affrontare le seguenti problematiche:

• Latenza elevata: la latenza sofferta dai messaggi tende ad essere elevata ed al- tamente impredicibile in una WAN, soprottutto se comparata con la relativa prevedibilit`a dei ritardi sofferti dai messaggi all’interno delle LAN. Le perdite di messaggi, inoltre, che risultano essere molto rare nelle LAN, sono comuni nelle wide-area network. Le ritrasmissioni che ne conseguono ritardano ulteriormente i messaggi inviati. L’alta latenza `e in grado di porre un ostacolo molto forte a quegli algoritmi che si scambiano ripetutamente messaggi per raggiungere una decisione.

• Frequenti cambiamenti: i cambiamenti della connettivit`a sono pi`u frequenti in una WAN che in una LAN, inoltre la failure detection risulta essere meno ac- curata in una WAN rispetto a quanto `e possibile ottenere in una LAN, grazie alle sua parziale sincronia. La combinazione di questi due fattori pu`o portare un algoritmo di membership a cambiare vista molto frequentemente. Un siffatto comportamento determina un costo molto elevato dell’algoritmo di membership stesso che pu`o costringere le applicazioni ad eseguire comunicazioni addizionali al fine di sincronizzare nuovamente lo stato condiviso.

• Instabilit`a: lo status dei cammini di comunicazione in una WAN fluttua frequente- mente a causa di guasti e congestioni. Di conseguenza violazioni della transitivit`a non sono di certo rare su Internet. Riferendosi ai periodi in cui si hanno comu- nicazioni non-transitive e frequenti cambiamenti della connettivit`a come periodi instabili, occorre dire che un algoritmo di group membership su WAN deve es- sere progettato per tenere in conto che periodi di instabilit`a possono incorrere e perdurare anche per lungo tempo.

I servizi di group membership rispondono agli eventi della rete, che possono essere guasti di processi, di link di comunicazione, recovery, e alle richieste di un processo di entrare o uscire da un particolare gruppo di multicast. A questo fine un algoritmo di group membership deve ricorrere ad un meccanismo di network event notification o di failure detection che lo informi degli eventi che coinvolgono la rete sottostante.

In [31] gli autori hanno proposto la nozione di Membership Notification Service (MNS) che fornisce ad ogni processo un’approssimazione della stato corrente, senza essere sincronizzati con lo stream dei messaggi dati. Il membership notification service svolge appunto i compiti di ricezione e rilevazione di eventi accaduti all’interno della membership e della rete, comunicando al servizio di membership i cambiamenti avve- nuti, o che almeno crede lo siano stati, sar`a poi compito del servizio di membership determinare le azioni da compiere sulla vista locale. Questo approccio permette di maneggiare concorrentemente un numero molto elevato di eventi di join e leave simul- tanei, e fornisce affidabilit`a per la consegna dei messaggi a quei membri che rimangono permanentemente attivi nonostante i cambiamenti della membership. Un servizio di questo tipo `e in grado solamente di fornire un’approssimazione della membership cor- rente senza poter garantire la propriet`a di liveness della membership precision a causa, come gi`a detto, dell’asincronicit`a del sistema.

Esamineremo il concetto di Membership Notification Service nella sezione seguente per una sua implementazione su un’architettura di tipo client/server. Verr`a descritto in generale il protocollo a cui si fa riferimento e il tipo di topologia che vuole generare.

Rimandiamo al Capitolo 3 per un’analisi pi`u approfondita del medesimo problema sempre in ambito di reti WAN su ampia scala ma con particolare riferimento alle reti di tipo peer-to-peer, oggetto di analisi e del contributo prestato da questa tesi.

1.3.2 Un’implementazione di MNS: Xpand

Gli autori [31] presentano un algoritmo di membership implementato in Xpand, pro- gettato per essere flessibile e garantire soprattutto una buona efficienza a quelle ap- plicazioni che non richiedono una forte semantica. Per lo stesso motivo vengono usati in esso due differenti flussi per i messaggi di controllo e per quelli applicativi, di cui i primi fanno ricorso ad un servizio di trasporto affidabile.

L’algoritmo di membership implementato in Xpand `e ottimizzato per fornire le seguenti propriet`a:

1.3. GROUP MEMBERSHIP PER WAN 23

Smooth-Join : Un nuovo membro deve poter entrare nel gruppo senza modificare il flusso dei messaggi del gruppo;

Fast-Join : una volta che un processo entrante si `e registrato nella sua LAN deve poter iniziare ad inviare messaggi;

Dynamic Membership : deve poter permettere ai processi di entrare o uscire dal gruppo in un ambiente di tipo WAN.

Il servizio di membership permette di fornire queste propriet`a senza compromettere le due propriet`a base di consegna di Xpand, cio`e:

FIFO order : ogni ricevente, che inizia a ricevere messaggi da una data sorgente, ricever`a tutti i messaggi emessi in ordine FIFO dal momento in cui ha eseguito il join al flusso;

Gap-Free : due processi che rimangono connessi durante cambiamenti consecutivi della membership continueranno a ricevere ogni altro messaggio senza interruzioni nello stream dei messaggi.

Problematiche d’implementazione

Allo scopo di riuscire a mantenere un elevato numero di client, Xpand `e stato implemen- tato utilizzando un’architettura gerarchica a due livelli: ogni LAN `e rappresentata da un delegato che coordina le attivit`a del protocollo riguardo alla sua LAN di competen- za con il gruppo distribuito su base WAN. Per incrementare la scalabilit`a un delegato potrebbe essere visto come una collezione di sender, o di receiver, della sua LAN e il sender potrebbe non essere un membro esplicito del gruppo. L’informazione relativa al sender, in una LAN, potrebbe essere mantenuta dal solo delegato che riceverebbe le informazioni inviate dal sender per poi distribuirle all’interno del gruppo.

Abbiamo, quindi, che i processi partecipanti ad un sistema Xpand sono raggruppati in cluster, in modo tale che i membri dello stesso cluster si trovino sulla stessa LANi cluster sono distribuiti su di una WAN e possiamo distinguere in essi due tipi di processi:

regolari e delegati. I processi regolari eseguono l’user application mentre i delegati sono demoni designati a servire come rappresentanti della LAN per gli altri cluster.

I delegati, quindi, non solo rilevano i cambiamenti all’interno della propria LAN ma son incaricati di comunicare questi cambiamenti agli altri delegati loro pari in modo da

diffondere l’informazione sui nodi che hanno mutato il loro stato all’interno del sistema.

Devono inoltre gestire situazioni di partizionamento, di disconnessione o di aggiunta di nuove reti, attraverso il management con i nuovi delegati che si aggiungono ad un gruppo.

Un delegato di una LAN `e replicato per scopi legati alla tolleranza ai guasti ma solo un delegato `e attivo in un determinato istante. Tutti gli altri delegati non attivi, chiamati delegati di backup, vengono utilizzati come copie di emergenza del delegato designato.

Network Event Notification Service

L’architettura gerarchica appena descritta si combina con un’implementazione client/server del servizio di Membership Notification in cui i client utilizzano il no- tification service per richiedere l’ingresso o l’uscita dal gruppo, o per aggiornare le informazioni riguardo al gruppo stesso. Esistono cio`e un insieme di server, i delegati appunto, ognuno dei quali `e incaricato dei seguenti compiti:

1. essere il punto di accesso dei nodi in joining;

2. tracciare le partenze dei processi, siano esse a causa di guasti o di leave volontarie;

3. fornire viste della membership a chiunque ne faccia richiesta.

Il servizio fornisce ai client un’interfaccia che consiste fondamentalmente di tre funzioni base:

• NS join(G) `e una richiesta di un client di entrare a far parte del gruppo G;

• NS leave(G) `e una richiesta di un client di lasciare il gruppo G;

• NS resolve(G) `e una richiesta di ricevere la lista della membership corrente, cos`ı come viene vista dal notification service.

Il servizio permette ai processi regolari l’iscrizione a gruppi che non si trovino sulla stessa LAN, e nel caso in cui un processo client voglia iscriversi ad un gruppo di cui il suo delegato non `e ancora membro dovr`a prima aspettare il join al gruppo in questione da parte del processo delegato.

Il notification service contiene un modulo di failure detector che, poich`e staimo assumendo un ambiente di esecuzione asincrono, `e costretto ad essere inaffidabile in

1.3. GROUP MEMBERSHIP PER WAN 25

alcune sue esecuzioni, pu`o cio`e sospettare erroneamente alcuni processi corretti. Dato che uno degli obiettivi `e proprio l’implementazione del servizio in un ambiente asin- crono gli autori non hanno richiesto al NS di essere accurato ma hanno supposto che sia sempre completo, nel senso che se un processo fallisce nel ricevere un messaggio inviatogli allora il processo sar`a eventualmente sospettato. Secondo gli autori il sod- disfacimento delle propriet`a di liveness di Xpand non dipende, inoltre, dalla capacit`a del membership notification service di fornire una vista consistente poich´e Xpand `e in grado di comunicare con ogni insieme connesso di client.

I risultati mostrati in [31] vengono a confemare che Xpand rispetti le propriet`a su enunciate anche se non `e fatto alcun riferimento alla effettiva dinamicit`a, in termini di frequenza di operazioni di join e di leave, su cui sono state effettuate le prove speri- mentali. Vedremo nel Capitolo 4 come tale parametro risulti invece di fondamentale importanza per quello che concerne le sorti di un protocollo di group membership.

Capitolo 2

Gossip-Based Group Membership

L’espansione di applicazioni distribuite su Internet ha ampliato la richiesta e ha mo- strato la necessit`a di un sempre maggiore sviluppo di meccanismi di comunicazione all’interno di un gruppo di utenti. In quest’ottica i protocolli probalistici basati su una disseminazione di tipo gossip stanno emergendo e si stanno affermando come una valida alternativa, in grado di fornire buona scalabilit`a e affidabilit`a.

2.1 Caratteristiche generali dei protocolli gossip-based

I protocolli di gossip, detti anche epidemiologici, sono protocolli di tipo probabilistico.

In questa tipologia di protocolli ogni membro, per inviare in broadcast un messaggio, recapita il messaggio ad un sottoinsieme, scelto casualmente, dei membri del gruppo.

Ogni processo che lo riceve ne rinvier`a una copia ad un altro sottoinsieme, anch’esso scelto casualmente, e cos´ı via.

La scalabilit`a `e determinata dal fatto che ogni processo invia soltanto un nume- ro limitato di messaggi, indipendentemente dalla dimensione complessiva del sistema.

Inoltre il processo non deve attendere messaggi di acknowledgment ed eseguire delle procedure di recovery nel caso di mancata ricezione di tali messaggi. L’uso di messaggi ridondanti fornisce un meccanismo per assicurare una buona affidabilit`a anche nel caso di alto tasso di perdita di pacchetti nella rete e di guasti nei nodi: uno stesso nodo pu`o infatti ricevere copie del medesimo messaggio da parte di pi`u processi. Nessun processo ha un ruolo particolare da svolgere, in questo modo un processo guasto non inficia la possibilit`a di inviare messaggi da parte dei processi corretti.

Pi`u precisamente i protocolli di gossip godono delle seguenti propriet`a:

27

• scalabilit`a Le loro performance non degradano rapidamente al crescere del nu- mero dei processi. Generalmente ogni processo invia un numero di messaggi indipendente dal numero dei processi e predeterminato. In un protocollo siffato un processo necessita di conoscere solo gli identificatori degli altri processi pre- senti nella rete ed alcune costanti. In queste condizioni, se la stabilit`a della rete fisica non degrada con il numero dei processi, il protocollo di gossip `e scalabile.

• graceful degradation Per molti protocolli di broadcast, deterministici ed affidabili,

`e definito un numero f di guasti per il quale il protocollo `e in grado di funzionare correttamente. In presenza di f + 1 guasti il protocollo non sar`a in grado di funzionare. L’affidabilit`a del protocollo sar`a uguale alla probabilit`a che non oc- corrano contemporaneamente pi`u di f guasti. D’altra parte i protocolli di gossip hanno un comportamento meno sensibile ai guasti e la probabilit`a di funzionare correttamente non decresce in modo netto al superamento di un valore di soglia f , ma decresce in modo graduale gracefully appunto..

• adattabilit`a Non `e difficile aggiungere o rimuovere processi nella rete. Il problema risiede nella configurazione dei parametri utilizzati dai protocolli che spesso sono configurati in modo statico in base alle dimensioni previste della rete. Un aumento imprevisto, e consistente, del numero di processi di un gruppo pu`o portare, in questi casi, ad una degradazione delle prestazioni.

Dato che i destinatari dei messaggi inviati da ogni processo sono scelti in modo casuale, esiste la probabilit`a che un messaggio non venga consegnato a tutti i processi appartenenti ad un gruppo anche in assenza di guasti. In una clique questa probabilit`a

`e bassa [27], ma questo non `e vero nel caso in cui la connettivit`a della rete non sia uniforme.

Risulta essere, inoltre, molto difficile ottenere un’espressione analitica che descriva il comportamento di un protocollo di gossip; spesso il miglior risultato possibile `e ottenere un’equazione in grado di descrivere il comportamento asintotico per semplici topologie di rete. Nel caso di reti pi`u complesse le analisi non possono trascendere dai dati ottenuti in via sperimentale tramite delle simulazioni.

2.1.1 I gossip-based e la Membership

Si `e detto che i protocolli di tipo gossip, o epidemici, risultino essere scalabili in termini di messaggi inviati dai singoli processi e di bilanciamento del carico. Diverso il discorso

2.1. CARATTERISTICHE GENERALI DEI PROTOCOLLI GOSSIP-BASED 29

per quanto riguarda la scalabilit`a in termini di management della membership dove, spesso, si parte dall’assunzione che ogni processo sia in grado di conoscere ogni altro.

E evidente come tale assunzione, seppur di poco conto nel caso di gruppi di piccole´ dimensioni, possa risultare una barriera quasi invalicabile quando si trattai di operare con un numero di processi molto elevato. Infatti, le strutture dati necessarie per memo- rizzare le view di un cos´ı elevato numero di processi possono consumare molte risorse di memoria, anche trascurando le comunicazioni necessarie per mantenere la coerenza delle view fra tutti i processi coinvolti.

Il problema della membership si pone quindi, con particolare urgenza e rilevanza, non appena si mostra che la scelta casuale ed uniforme, fra i presenti, dei processi a cui inviare un messaggio, non `e un criterio capace di garantire una vera scalabilit`a agli algoritmi gossip-based. Alcune volte si `e delegata la responsabilit`a della membership a server dedicati ma in questo modo si `e solo rimandato il problema, poich`e anche questi hanno risorse limitate, ed inoltre si `e aggirata la vera natura dell’architettura peer-to- peer. Queste considerazioni hanno spinto a lavori [22, 13] in cui si `e cercato di fornire ad ogni nodo una vista parziale del sistema senza che il nodo stesso abbia una conoscen- za globale della membership. D’altra parte la dimensione della membership parziale necessaria per ottenere con successo un gossip `e legata alla taglia del sistema: quando la taglia del gruppo cresce anche la taglia della vista parziale deve crescere di conse- guenza. Determinare il fan-out `e semplice nel caso si lavori in un modello centralizzato o distribuito su un numero limitato di server, poich`e tali modelli permettono in manie- ra sufficientemente rapida la determinazione del numero dei partecipanti alla sessione.

In un modello totalmente decentralizzato, dove ogni nodo possiede solo una piccola porzione della vista globale non `e per nulla semplice ottenere il medesimo risultato, poich`e risulta estremamente complesso calcolare la dimensione del sistema complessivo a partire dalle local view dei singoli nodi. Ulteriore attenzione merita il problema della suddivisione della view complessiva del sistema nelle local view dei singoli nodi, che per prevenire problematiche di isolamento e partizionamento della membership dovr`a con- tenere una certa ridondanza, delle informazioni che vengano condivise da pi`u membri della membership stessa.

In molti studi `e stato affrontato questo problema e altrettanti protocolli sono stati presentati per risolverlo. Nel resto del capitolo focalizzeremo la nostra attenzione su alcuni di essi che risultano essere di maggior interesse. Esporremo due dei protocolli pi`u importanti per quanto riguarda questo paradigma di Group Membership Protocols

in ambiente completamente decentralizzato: il Lightweight Probabilistic Broadcast nella Sezione 2.2 e lo Scalable Membership Protocol nella Sezione 2.4. Verranno poi accennati altri due protocolli: CYCLON [32] e scalable gossip-based alghoritm [3], in parte ispirati ai lavori suddetti. SCAMP, che sar`a poi oggetto delle simulazioni affrontate nel Capitolo 4, verr`a affrontato in modo pi`u approfondito e critico nel Capitolo 3.

2.2 Lightweight Probabilistic Broadcast

Il lightweight probabilistic broadcast `e un protocollo completamente decentralizzato in quanto non viene mai richiesta ad ogni processo che lo esegue, e in nessuna sua fase, la conoscenza completa del sistema o una disseminazione dei messaggi. Definito in [25], Lpbcast ricorre ad un approccio probabilistico nel trattare la membership: ogni processo ha, infatti, un vista parziale del sistema scelta in maniera casuale e di una lunghezza l determinata, cos`ı come il fan-out F . Entrambi i valori sono fissati per ogni membro del gruppo, e gli autori hanno ottenuto il risultato per cui, dato F ≤ l, l’ammontare della conoscenza che ogni processo mantiene riguardo la membership complessiva non impatta nelle performance del protocollo che risultano influenzate solo dal fan-out F . Ci`o non significa che il valore di l non abbia alcun impatto per quello che riguarda le prestazioni dell’algoritmo, infatti al decrescere di l aumentano le probabilit`a di incappare in un partizionamento del sistema. Gli autori hanno determinato che la probabilit`a Ψ(i, n, l) di creazione di una partizione di dimensione i in un sistema di taglia n con una dimensione della view di l, risulta monotonicamente decrescente, una volta fissato n, al crescere di l. Detto questo bisogna aggiungere che lpbcast `e lightweight, almeno nelle intenzioni degli autori, poich`e utilizza un quantit`a limitata di risorse di memoria e non richiede messaggi dedicati per la gestione della membership: i messaggi di gossip vengono utilizzati non solo per disseminare le notifiche degli eventi e per propagare il digest delle notifiche degli eventi di ricezione ma anche per propagare informazioni relative al sistema stesso e ai suoi membri.

2.2.1 Messaggi di gossip e Strutture dati

L’algoritmo lpbcast `e basato sull’invio periodico di messaggi di gossip, attraverso periodi non sincronizzati. Un messaggio di gossip contiene diversi tipi di informazioni e viene utilizzato per vai scopi:

• Event Notifications. un messaggio di gossip trasporta le informazioni relative a