“La Sapienza”
Facolt` a di Ingegneria
Tesi di Laurea Specialistica in Ingegneria Informatica
Sessione Invernale - Maggio 2006
Analisi e Confronto di Algoritmi di Mantenimento di
“Overlay Network” in ambiente p2p
Silvia Bonomi
Relatore: Prof. Roberto Baldoni Revisore: Prof. Giorgio Ausiello
Correlatore: Ing. Sara Tucci Piergiovanni
Ad Alessandro e ai miei genitori
Ringraziamenti
Scrivere i ringraziamenti `e sempre un lavoro difficile perch`e ci sono talmente tante per- sone che, in un modo o nell’altro, hanno contribuito alla buona (almeno spero) riuscita del lavoro e non vorrei dimenticare nessuna. Sar`a forse banale ma un primo ringrazia- mento va ai miei genitori che hanno sempre creduto in me e nelle mie capacit`a e spero, con questo lavoro, di dargli almeno una piccola soddisfazione, a mio fratello Marco e a tutta la mia famiglia in generale. Un grazie enorme,e non basta, va ad una persona speciale, Alessandro, che mi `e stato vicino in questi anni, sostenendomi e incoraggian- domi nei momenti pi`u pesanti e che ancora prima di me ha creduto che ce l’avrei fatta.
Grazie alla mia migliore amica Romina con cui ho condiviso pomeriggi interminabili sui tavoli della biblioteca a capire e studiare formule matematiche che non finivano mai. Grazie a Roberto Baldoni che mi ha dato l’opportunit`a di fare quest’esperienza di tesi veramente interessante che mi ha accresciuta. Grazie a tutto il gruppo di lavoro:
Sara, Leonardo, Alessia e Tony, a tutto il laboratorio C4 nelle persone di Sirio, Rug- gero, Daniele, Damiano, Ugo, Davide, Carola che con me hanno condiviso momenti di allegria, di fatica e di intenso lavoro. Grazie al mio “collega” Adriano con cui ho lavorato benissimo e a tutti i compagni di studio di questi magnifici cinque anni Fabio, Elisa, Maria Paola, Leo, Enrico, Alessandro, Simone, Hermann e tutti gli altri. Un ringraziamento va inoltre a Paola per il suo aiuto nella revisione. Spero di non aver domenticato nessuno e nel caso lo abbia fatto perdonate.
Introduzione 1
1 Stato dell’arte 5
1.1 I Sistemi Distribuiti . . . 5
1.1.1 Modelli di Sistema . . . 6
1.1.2 Modelli di Timing . . . 6
1.1.3 Modelli di Guasto . . . 8
Guasti dei processi . . . 8
Guasti della Comunicazione . . . 10
1.1.4 Topologia della Rete . . . 10
1.1.5 Determinismo contro Randomizzazione . . . 11
1.1.6 Propriet`a delle computazioni distribuite . . . 11
1.2 Il Problema della Group Membership . . . 12
1.2.1 La Group Membership Deterministica . . . 12
Modello matematico . . . 12
1.2.2 Propriet`a del Group Membership Service . . . 14
Partitionable e Primary Component Membership Service . . . . 15
Propriet`a di Safety . . . 15
Propriet`a di Liveness . . . 17
Eventually Perfect Failure Detector (3 P) . . . 18
Liveness per modelli eventually stable . . . 18
Liveness per modelli mai stabili . . . 20
1.2.3 Rilassamento della Specifica: Eventual Group Membership . . . 21
1.3 La Group Membership Probabilistica . . . 21
1.3.1 Caratteristiche dei Protocolli Gossip-based . . . 22 v
1.4 La Group Membership nei Sistemi p2p . . . 25
1.4.1 I Sistemi p2p . . . 25
Applicazioni . . . 26
Architettura . . . 26
1.4.2 Evoluzione del p2p: le generazioni . . . 28
Prima Generazione . . . 28
Napster . . . 28
Gnutella . . . 28
Seconda Generazione . . . 29
Chord . . . 29
CAN . . . 31
Terza Generazione . . . 31
Low Diameter . . . 31
Butterfly . . . 31
1.4.3 Overlay Networks . . . 31
I Sistemi Strutturati . . . 32
Sistemi Non Strutturati . . . 33
1.4.4 Il Mantenimento dell’Overlay . . . 36
Due Approcci al Problema dell’Overlay Manteinance: Protocolli Reattivi VS Protocolli Pro-attivi . . . 36
2 I Protocolli Probabilistici 39 2.1 Lightweight Probabilistic Broadcast . . . 39
2.1.1 Messaggi di gossip e Strutture dati . . . 40
2.1.2 Procedure Relative al Gossip . . . 41
Ricezione del messaggio di Gossip . . . 41
Invio del messaggio di Gossip . . . 42
Recupero di event notification . . . 44
2.1.3 Dinamismo di Π . . . 44
2.1.4 Ottimizzazioni . . . 46
Rimozione dei messaggi con modalit`a Age-Based . . . 46
Rimozione dei membri con modalit`a Frequency-Based . . . 47
2.2 SCAMP . . . 48
2.2.1 Caratteristiche base di SCAMP . . . 49
Subscription . . . 50
Unsubscription . . . 53
Unsubscription e Correttezza delle viste . . . 54
Recupero dall’isolamento . . . 54
Isolamento e Consegna . . . 54
2.2.2 Meccanismi per ribilanciare i grafi . . . 57
Lease . . . 57
Indirection . . . 58
2.3 ADH . . . 59
2.3.1 Il Protocollo . . . 59
Gestione delle Viste . . . 60
La procedura di Join . . . 61
La procedura di Leave e la gestione dei guasti . . . 61
2.4 Cyclon . . . 62
2.4.1 La procedura di Shuffling: lo scambio delle viste . . . 63
La procedura di Basic Shuffling . . . 64
La procedura di Enhanced Shuffling . . . 65
2.4.2 La procedura di Join . . . 67
2.4.3 La procedura di Leave e la gestione dei Guasti . . . 69
2.4.4 Propriet`a di base . . . 70
Connettivit`a . . . 70
Convergenza . . . 71
Distribuzione dell’ In-degree e dell’Out-degree . . . 72
3 Parametri e Metriche per l’Analisi dei Protocolli 75 3.1 Il Concetto di Churn . . . 75
3.2 Il Simulatore e l’Ambiente Simulativo . . . 76
3.2.1 Il Simulatore: Peersim . . . 76
3.2.2 L’Ambiente di Simulazione . . . 77
3.2.3 Parametri di Simulazione . . . 79
3.3 Metriche di Valutazione . . . 79
4 Analisi e Valutazione delle Performance di Algoritmi Reattivi 81 4.1 Valutazione di Lightweight Probabilistic Broadcast . . . 81
4.1.1 Esperimento 1 . . . 82
4.1.2 Esperimento 2 . . . 84
4.2 Valutazione di SCAMP . . . 86
4.2.1 Esperimento 1 . . . 87
4.2.2 Esperimento 2 . . . 89
4.2.3 Esperimento 3 . . . 91
4.2.4 Bound . . . 92
4.3 Valutazioni Complessive . . . 93
5 Il Caso SCAMP: Tecniche di Miglioramento e Valutazione 97 5.1 Il Problema delle Leave Conflitting . . . 98
5.2 Prevenzione dell’Isolamento . . . 99
5.3 Meccanismo di Ack . . . 101
5.4 Meccanismi di Heartbeat e Ping . . . 103
5.5 Un’Euristica per il Rejoin . . . 107
Conclusioni 109
Bibliografia 113
Elenco delle Figure 118
Tutti noi abbiamo utilizzato almeno una volta un’applicazione di peer-to-peer (p2p) e la maggior parte di queste senza accorgercene; le applicazioni di file sharing rappresen- tano l’espressione pi`u chiara dello spirito del p2p, ossia un numero di nodi equivalenti (peer, appunto) che fungono sia da client che da server verso altri nodi della rete met- tendo a disposizione della collettivit`a le loro risorse. In questo contesto riveste un’im- portanza fondamentale il problema del mantenimento della connettivit`a dell’overlay network, ossia della rete logica che viene costruita al di sopra dello strato fisico (si veda 1.4.3 per ulteriori chiarimenti), in quanto rappresenta un fattore cruciale per assicurare un’adeguata qualit`a del servizio.
Il contesto del p2p `e quello di un sistema dispiegato su larga scala in cui non
`
e possibile mantenere traccia di tutti i membri del gruppo e ciascun nodo mantiene esclusivamente una vista locale. Diventa quindi fondamentale riuscire a mantenere la connettivit`a facendo affidamento solo sulle viste parziale che ogni singolo nodo `e in grado di costruirsi. A tale scopo ci si pu`o servire dei cosidetti protocollo di overlay management (OMP), ossia di algoritmi che stabiliscono delle regole per l’entrata dei nodi nel gruppo (join) e per la loro uscita (leave).
Un sistema come quello descritto in precedenza `e, inoltre, contraddistinto dal com- portamento fortemente dinamico dei processi che vi appartengono; questo aggiunge un’ulteriore complicazione al problema del mantenimento della connettivit`a in quanto il grafo che rappresenta la rete non `e pi`u assimilabile ad una clique e quindi `e pi`u facile che l’azione congiunta di dinamismo e concorrenza conduca al partizionamento.
In letteratura esistono molti algoritmi che si propongono lo scopo di gestire e man- tenere una rete connessa ([8] [10] [45] [54]), ma in quasi tutti i risultati mostrati si mette in luce l’efficacia del protocollo in ambianti statici o quasi; i sistemi reali, tuttavia, sono ben pi`u complessi e non possono essere rappresentati con scenari privi di dinamismo.
1
Contributo
Il contributo della presente tesi consiste nello svolgere un’analisi di alcuni protocolli, tra quelli citati in precedenza, volti al mantenimento della rete, in un ambiente disturbato dal churn (paragrafo 3.1) e posto sotto pressione. Si cercher`a di evidenziare quale sia la risposta a questo tipo di sollecitazione ed eventualmente dove siano i limiti degli algoritmi considerati e da cosa derivino.
Un secondo contributo consiste, una volta evidenziati i punti deboli dei protocolli, nel proporre meccanismi di recupero o di gestione delle procedure considerate critiche e limitanti; tali meccanismi verranno prima introdotti e poi testati nelle medesime con- dizioni di stress della precedente analisi al fine di valutare la loro bont`a ed adeguatezza allo scenario considerato.
Organizzazione
La tesi `e strutturata come segue:
- nel Capitolo 1 `e descritto lo stato dell’arte che fornisce da prima le definizioni di base necessarie a comprendere il mondo dei sitemi distribuiti, per poi affrontare il problema della Group Membership;
- nel Capitolo 2 sono presentati e descritti dei protocolli probabilistici per la ges- tione della connettivit`a del grafo che rappresenta la rete;
- nel Capitolo 3 `e descritto il simulatore utilizzato e l’ambiente in cui sono state svolte le simulazioni;
- nel Capitolo 4 `e contenuto il primo contributo della tesi consistente nell’analisi simulativa sotto churn dei protocolli probabilistici presentati nel Capitolo 2;
- nel Capitolo 5 vengono descritti e testati i miglioramenti proposti per un parti- colare algoritmo tra quelli descritti.
Pubblicazioni
Parte del lavoro presentato nell’ambito della presente tesi `e contenuto anche in:
R. Baldoni, S. Bonomi, L. Querzoni, A. Rippa, S. Tucci Piergiovanni, A. Virgillito Evaluation of Unstructured Overlay Maintenance Protocols under Churn. to appear on July 2006 in International Workshop on Dynamic Distributed Systems
Stato dell’arte
In questo capitolo viene fatta una panoramica sul mondo dei sistemi distribuiti, con- centrando l’attenzione sui concetti e sulle definizioni basilari di sistema distribuito per poi giungere alla descrizione delle peculiarit`a di un sistema peer-to-peer (p2p).
1.1 I Sistemi Distribuiti
Un sistema distribuito `e composto da un insieme di processi che comunicano su canali (a banda stretta e ad alta latenza) con il fine di raggiungere un obiettivo comune (come ad esempio l’acceso ad una risorsa condivisa o la scelta di un processo particolare che possa guidare la computazione distribuita), prevedendo la possibilit`a di guasto dei pro- pri componenti. Un contesto siffatto `e solitamente formato da un elevato numero di processi: la crescita della quantit`a di componenti operanti in un sistema distribuito im- plica maggior potere computazionale ma, di contro, un elevato bisogno di cooperazione e coordinamento.
Un sistema distribuito `e modellato come un insieme Π ≡ {p1, p2, . . . , pn} di processi che interagiscono tra loro mediante scambio di messaggi attraverso canali di comu- nicazione. Esistono diverse astrazioni che modellano il comportamento dei canali ed i diversi tipi di guasti che possono occorrere e che consentono, quindi, di specificare un modello preciso; a seconda delle restrizioni imposte dall’astrazione il problema da risolvere pu`o essere pi`u o meno semplice: il passo principale da compiere `e quello di stabilire un protocollo di comunicazione (cio`e opportune regole per lo scambio di mes- saggi) mediante il quale far evolvere la computazione. Ovviamente la solvibilit`a del problema, e transitivamente la complessit`a del protocollo, sono strettamente dipenden-
5
ti dalle assunzioni fatte sul sistema e quindi dal modello preso in considerazione: in generale, quanto pi`u il modello di sistema `e restrittivo tanto pi`u il protocollo per gestire la comunicazione (se esiste) `e complesso.
Nelle descrizioni di un modello di sistema vengono considerati i seguenti parametri:
la sincronia e i tipi di guasti dei processi e delle comunicazioni nonch`e il grado di determinismo dei processi stessi e la topologia della rete .
1.1.1 Modelli di Sistema
Con il termine modello di sistema si intende la rappresentazione semplificata della re- alt`a, delle propriet`a e delle regole che caratterizzano il comportamento degli oggetti, che viene adottata nel processo di risoluzione del problema. Un modello si dice accu- rato se si avvicina molto alla realt`a dell’oggetto mentre si dice trattabile se `e possibile procedere all’analisi dell’ oggetto. Un buon modello per un problema dovrebbe es- sere al tempo stesso trattabile ed accurato e le propriet`a considerate dovrebbero essere solamente quelle che caratterizzano ed influenzano in maniera determinante il compor- tamento dell’oggetto. ´E importante sottolineare come non esista un modello buono ed adattabile a qualsiasi situazione, ma `e sempre possibile individuare modelli migliori di altri sotto opportune condizioni e in particolari ambienti.
1.1.2 Modelli di Timing
Definire la sincronia di un modello significa definirne le propriet`a in termini di temporizzazione.
Intuitivamente un modello pu`o ritenersi sincrono quando il succedersi degli eventi
`e scandito da un tempo comune. L’invio di un messaggio a, precedente a quello di un messaggio b, da un nodo allo stesso nodo, per esempio, sar`a preludio di una consegna che vedr`a giungere a destinazione il messaggio a precedentemente al messaggio b. Pi`u formalmente si dice che un sistema `e sincrono se soddisfa le seguenti propriet`a:
• Esiste un upper bound conosciuto δ sul ritardo dei messaggi (consistente nel tempo massimo necessario per mandare, trasportare e ricevere un messaggio su un canale).
• Ogni processo p ha un clock locale Cpcon un drift rate ρ ≥ 0 conosciuto e limitato
rispetto al tempo reale. Per tutti i p e per tutti gli istanti di tempo t > t0, quindi, (1 + ρ)−1 ≤ Cp(t) − Cp(t0)
(t − t0) ≤ (1 + ρ)
. Dove Cp(t) `e la lettura del clock Cp 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 e ci`o fornisce un meccanismo per la rilevazione di guasti. Si pu`o inoltre implementare clock approssima- tivamente 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 |Cp(t) − Cq(t)| ≤ [38, 16].
Intuitivamente un sistema asincrono contraddice le restrizioni dettate dalla sincro- nia. Definire un sistema asincrono, dunque, significa non avere un comportamento tracciabile in termini di tempistica e trovarsi nell’impossibilit`a di avere qualsiasi “tem- po comune” tra processi dello stesso sistema. In termini pi`u formali, dunque, un sistema si dice asincrono se non sono verificate le condizioni suddette ossia 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.
I sistemi sincroni ovviamente sono pi`u trattabili ma raramente considerabili; nella maggior parte dei casi, infatti, si assume di avere sistemi asincroni per i seguenti motivi:
• semplicit`a della semantica;
• generalit`a dell’assunzione (un protocollo che soddisfa determinate propriet`a in ambiente asincrono continua a soddisfarle anche in ambiente sincrono);
• la maggior parte dei sistemi distribuiti reali `e soggetto a varizioni improvvise di carico che non consentono di fare assunzioni di sincronia;
La maggiore attinenza alle situazioni reali e la sua genericit`a, quindi, rende il mod- ello asincrono la scelta ottimale in fase di modellazione. Stupisce per`o, come vedremo, che in molti lavori pubblicati recentemente si indichino ancora soluzioni ristrette ad un ambiente di lavoro sincrono totale o parziale, esplicito o implicito. I modelli ap- pena descritti sono i due estremi in termini di assunzioni di timing; al loro interno si
trovano tutti quei modelli che possono essere definiti parzialmente sincroni per cui vale la seguente assunzione
Esiste un tempo T oltre il quale la sincronia si mantiene e il sistema diventa
“stabile” in modo tale da consentire all’ algoritmo di evolvere e convergere ad una soluzione
La famiglia dei sistemi parzialmente sincroni `e altamente variegata ed i suoi compo- nenti si differenziano a seconda del proprio grado di asincronia. I processi, ad esempio, possono avere velocit`a limitata e clock perfettamente sincronizzati ( = 0) ma ritardo di trasmissione dei messaggi privo di bound [21] oppure sconosciuto seppur con dei limit [23].
1.1.3 Modelli di Guasto
Come gi`a accennato nel paragrafo 1.1, i guasti possono colpire tanto i singoli processi quanto i canali di comunicazione. Definire il failure model che caratterizza il sistema equivale a specificare come i componenti guasti si comportano (come dev`ıano cio`e dal comportamento canonico), cos`ı da poter capire quali effetti abbiano sulla computazione.
Nel seguito sar`a riportata la specifica delle modalit`a con cui processi e canali possono scostarsi da un comportamento idoneo.
Guasti dei processi
Un processo `e guasto, nell’ambito di un’ esecuzione, se il suo comportamento dev`ıa da quello previsto dall’ algoritmo che sta eseguendo; in caso contrario il processo si dice corretto. I failure model sono i seguenti [29]:
• Crash: un processo guasto termina prematuramente e non esegue alcuna azione da questo punto in poi. Prima di fermarsi, tuttavia, si `e comportato in modo corretto.
• Send omission: un processo guasto termina prematuramente e/o omette in modo intermittente di inviare dei messaggi che era supposto inviare.
• Receive omission: un processo guasto termina prematuramente e/o omette in modo intermittente di ricevere dei messaggi che gli sono stati inviati.
• General omission: un processo guasto `e soggetto a fallimenti di tipo send omission e/o receive omission.
• Arbitrary (detto anche Byzantine o malicious) : un processo guasto pu`o esi- bire qualsiasi comportamento cambiando il proprio stato, ad esempio, in modo arbitrario.
• Arbitrary con message authentication: un processo guasto pu`o esibire qualsiasi comportamento ma `e disponibile un meccanismo per l’ autenticazione dei messag- gi usando unforgeable signature: un processo soggetto ad un guasto arbitrario pu`o asserire di aver ricevuto un particolare messaggio da un processo corretto, pur, eventualmente, non avendolo 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 ma 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 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).
I failure model possono essere classificati in termini di severit`a. Un modello A `e pi`u severo di un modello B se l’ insieme dei comportamenti di guasto permessi da B
`
e un sottoinsieme proprio di quello costituito dai comportamenti di guasto permessi da A (Figura 1.1) . Un algoritmo che tollera guasti di tipo A, quindi, tollera anche guasti di tipo B. In termini di severit`a va notato come i guasti di tipo arbitrario siano i pi`u preoccupanti mentre i crash ne sono la controparte meno dannosa; all’interno di tali estremi si trovano, in ordine di severit`a, gli arbitrari con message autentication, i timing failures ed i general omission. I rimanenti guasti vengono raggruppati nella famiglia dei benign.
Un sistema `e detto f-fault tolerant se continua a soddisfare le proprie specifiche anche nel caso in cui f componenti (in questo caso i processi) siano guasti.
$UELWUDU\
$UELWUDU\ZLWKPHVVDJH DXWKHQWLFDWLRQ
7LPLQJ RQO\LQ
V\QFKURQRXVPRGHO
*HQHUDO2PLVVLRQ
5HFHLYH2PLVVLRQ
6HQG2PLVVLRQ
&UDVK
Benign
Figura 1.1: Classificazione dei failure model Guasti della Comunicazione
I canali di comunicazione possono essere soggetti ai seguenti tipi di guasti [29]:
• Crash: un canale guasto smette di trasportare messaggi essendosi comportato prima del crash in modo corretto.
• Omission: un canale guasto omette in modo intermittente di trasportare i messaggi inviati attraverso di esso.
• Arbitrary (o Byzantine o malicious): un canale guasto pu`o esibire un qualsiasi comportamento, generando ad esempio 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 in cui i nodi sono i processi e gli archi sono i canali di comunicazione tra essi. Questo modello si adatta sia a reti punto-punto che a reti broadcast. Nel caso in cui vengano considerati particolari
problemi, possono essere fatte, se necessario, particolari assunzioni che aiutino nella modellazione. Questo tipo di modellazione consente quindi di applicare tecniche della teoria dei grafi a problemi di computazione distribuita in modo tale da avere una buona base teorica su cui costruire (ed eventualmente validare) gli algoritmi. L’utilizzo dei grafi presuppone la conoscenza di alcune definizioni basilari; tra di esse trovano particolare rilevanza quelle di connettivit`a e di walk:
• Un grafo G si dice connesso se per ogni coppia di vertici appartenenti al grafo si ha un cammino che li collega.
• Un walk di lunghezza k in un grafo G `e una sequenza non vuota v0e0v1e1...ek−1vk di vertici ed archi di G tale che che e = vi, vi+1per tutti gli i < k.
1.1.5 Determinismo contro Randomizzazione
Il comportamento di un processo pu`o, in generale, essere rappresentato da un automa a stati (eventualmente anche infiniti) la cui funzione di transizione ne determina l’ap- partenenza alla categoria dei processi con un comportamento deterministico piuttosto che alla categoria dei processi con un comportamento randomizzato. Nel caso di pro- cessi deterministici, il comportamento che si pu`o osservare a fronte di un determinato input `e univocamente determinato in base specificato dalla coppia <stato presente, input ricevuto>; un processo randomizzato a fronte di un determinato input, invece, pu`o assumere un comportamento, appartenente ad un insieme specifico, con una certa probabilit`a associata alla funzione di transizione (es. la ricezione del messaggio). `E da osservare che questa caratteristica dei processi ne influenza fortemente il grado di solvibilit`a.
1.1.6 Propriet`a delle computazioni distribuite
Nell’ambito di una computazione distribuita esistono delle propriet`a che gli algoritmi dovrebbero soddisfare; tra queste le pi`u importanti sono senza dubbio le propriet`a di safety e di liveness, ortogonali tra loro. Un algoritmo si definisce safe se durante la sua esecuzione non compie azioni errate (es. un processo non dovrebbe “inventare” dei messaggi); tale propriet`a, presa singolarmente, non basta a garantire che l’algoritmo sia buono in quanto esiste una soluzione triviale, consistente nel non compiere alcuna azione, che la soddisfarebbe banalmente. Per questo motivo bisogna assicurare che
venga soddisfatta anche la propriet`a di liveness: un algoritmo soddisfa la propriet`a di liveness se assicura che prima o poi qualche azione venga compiuta.
1.2 Il Problema della Group Membership
Quando si pensa ad un sistema distribuito, che lavora per portare avanti una data computazione, ci si riferisce ad un sistema composto da milioni di nodi che si scambiano messaggi per terminare con successo il protocollo stabilito; la prima conseguenza `e che non tutti i partecipanti si conoscono e non sono quindi in grado di comunicare direttamente tra di loro. Non tutti i partecipanti, inoltre, perseguono lo stesso scopo ma si dividono per lo pi`u in gruppi, ciascuno identificato dal proprio nome. L’ostacolo principale alla realizzazione di Group Membership coerenti, affidabili e convenienti `e non tanto la dinamicit`a del sistema quanto invece la sua asincronia. Gli algoritmi di Group Comunication servono, appunto, a realizzare la comunicazione in sistemi come quelli appena descritti attraverso:
• Group Membership Service che si occupa di mantenere una lista di utenti attualmente attivi e connessi all’interno del gruppo (view ).
• Multicast Service il cui scopo `e quello di consegnare i messaggi a tutti i componenti della view.
1.2.1 La Group Membership Deterministica
Il problema della Group Membership pu`o essere visto come un problema di distribuited coordination [50] in cui l’obiettivo `e convergere su una vista comune. Attualmente esistono diversi sistemi che forniscono servizi di group membership, come ad esempio Isis toolkit [12] (che `e stato il primo), Transis [7], Newtop [24], ciascuno con la propria specifica; in [28] gli autori forniscono una serie di specifiche, chiare e rigorose, con l’intento di rappresentare la maggior parte dei sistemi attuali. In una situazione reale, il problema `e tuttora irrisolto e la via frequentemente scelta per affrontarlo `e quella del best effort.
Modello matematico
In questo paragrafo verr`a proposto un breve cenno al modello sfruttato per rappre- sentare il problema in termini rigorosi e matematici. L’interazione che un Group Co-
munication System (GCS) offre avviene sia “verso l’alto”, con le applicazioni che usano il servizio di group membership, che “verso il basso”, con l’overlay formata dai nodi.
In un primo tempo verranno definiti i “tipi” che saranno utilizzati nel modello e le azioni di interazione con il GCS. Saranno indicati con:
P l’insieme dei processi;
M l’insieme dei messaggi;
VID l’insieme degli identificatori delle viste, ordinate parzialmente tramite l’operatore “<”.
Le azioni che verranno prese in considerazione per specificare formalmente le propriet`a del servizio sono:
- input send(p, m), p ∈ P, m ∈ M - output recv(p, m), p ∈ P, m ∈ M
- output view chng(p, <id, members>, T ), p ∈ P, id ∈ VID, members ∈ 2P, T
∈ 2P
- output safe prefix(p, m), p ∈ P, m ∈ M - input crash(p), p ∈ P
- input recover(p), p ∈ P
V : VID × 2P `e l’insieme delle view consegnate dall’operazione di view chng. In questo modo, una vista V ∈ V `e una coppia, i cui elementi verranno indicati con V.id e V.members.
Verranno ora elencati altri insiemi che saranno funzionali nella specifica formale delle propriet`a di safety e di liveness. Si definisce
- Events l’insieme che rappresenta le occorrenze degli eventi e definito come segue:
{send(p, m) | p ∈ P, m ∈ M} ∪ {recv(p, m) | p ∈ P, m ∈ M} ∪ {view chng(p, V, T ) | p ∈ P, V ∈ V, T ∈ 2P} ∪
{safe prefix(p, m) | p ∈ P, m ∈ M} ∪ {crash(p) | p ∈ P} ∪ {recover(p) | p ∈ P}
- Trace l’insieme che rappresenta una sequenza di eventi che pu`o essere finita o infinita.
Occorre introdurre ora un’ulteriore definizione sulle viste.
Definizione 1.2.1. (viewof ) La vista di un evento ti, che occorre al processo p, `e la vista consegnata a p in un evento view chng, in modo tale che nessun evento view chng o crash occorra in p tra tj e ti; la vista `e ⊥ se non ci sono tj.
E necessario fare alcune assunzioni sull’ambiente tra cui quella basilare 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.
Per distinguere i messaggi inviati in differenti eventi di send, si suppone che og- ni messaggio inviato contenga un identificatore unico. In questo modo `e possibile 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 del Group Membership Service
Idealmente, ci si aspetta che un servizio di membership sia preciso, che consegni cio`e una vista che rifletta correttamente lo stato della rete a tutti i nodi vivi che la ricevono.
In un sistema altamente dinamico ed asincrono, in cui la situazione `e mutevole in ogni istante di tempo, appare impossibile intuitivamente, ed `e formalmente dimostrabile, riuscire a garantire simili caratteristiche. Tutto ci`o rende necessario rafforzare il modello eliminando per lo meno l’asincronia in favore di una sincronia parziale. Come gi`a detto in precedenza, lo scopo del servizio di group membership `e quello di mantenere una lista dei processi che partecipano e sono attualmente vivi e connessi all’interno del sistema; il sistema subisce cambiamenti in seguito all’ingresso (join) e all’uscita (leave) dei componenti del gruppo o al loro guasto (crash). A fronte di ciascuno di questi eventi, la membership deve essere aggiornata e comunicata a tutti i componenti in
modo tale che questi installino le nuove viste e vengano rispettate le proprieta di safety e di liveness specificate nel seguito.
Partitionable e Primary Component Membership Service
Un servizio di membership pu`o essere di tipo primary component1 oppure partitionable.
La differenza sostanziale che intercorre tra i due tipi di membership service sta nell’or- dinamento dei messaggi; nel primo caso l’ordinamento `e totale mentre nel secondo `e parziale. Tutte le propriet`a di safety che vedremo nella prossima sezione sono valide per entrambe le tipologie di servizio (con l’aggiunta, nel caso di primary component service, di un’ulteriore propriet`a che impone il total order sulla consegna delle viste), mentre le propriet`a di liveness possono essere soddisfatte solo da sistemi di tipo partitionable.
Per i lettori interessati ad approfondire l’argomento si rimanda a [28].
Propriet`a di Safety
Propriet`a 1.2.1. (Auto Inclusione) Se un processo p installa la vista V allora p `e membro di V. Formalmente:
installs(p,V) ⇒ p ∈ V.members
Questa propriet`a pu`o essere banalmente soddisfatta dal fatto che in un sistema di group comunication ogni nodo `e sempre in grado di comunicare con i membri della sua vista ed ogni processo `e in grado di comunicare con se stesso.
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:
ti = view chng(p, V, T ) ∧ tj = view chng(p, V0, T0) ∧ i > j ⇒ V.id > V0.id
Il rispetto di questa propriet`a `e molto importante in quanto non consente ai vec- chi messaggi, che avevano assorbito grandi ritardi durante il loro viaggio nella rete, di essere scambiati erroneamente per nuovi messaggi. A differenza della propriet`a 1.2.1, soddisfatta da ogni sistema di group membership, la Monotonicit`a locale non `e rispet- tata come regola di base: alcuni group membership system, infatti, possono violarla nel caso in cui un processo andato in crash esegua il ripristino mantenendo la medes- ima identit`a; in tal caso, un processo che, recuperando dal fault, installa la sua vista
1conosciuto anche come primary partition
iniziale avr`a un identificatore inferiore rispetto alla vista che aveva installato prima di guastarsi.
Alcune vie per rimediare a queste problematiche sono state indicate in Isis [36, 37] in cui un processo guasto, per fare restoring, deve inizializzarsi nuovamente con un nuovo identificatore. Esso pu`o anche salvare le informazioni inerenti la vista su memoria fisica e utilizzarle come recupero in caso di guasto.
Alcune metodologie sono indicate in letteratura anche per generare identificatori di viste: in Transis [18] l’id di una vista `e rappresentato da un intero positivo calcolato tramite un contatore locale mantenuto da ogni processo; ad ogni installazione di vista ogni processo incrementa il contatore locale. A metodologie semplici come questa sono accostabili metodi pi`u complessi: l’identificativo pu`o essere individuato, per esempio, da una coppia hp, ci, dove p rappresenta il processo che ha creato la vista e c il valore del contatore locale di p, oppure un timestamp logico.
L’ordinamento delle viste assume spesso i caratteri di propriet`a fondamentale; in [19] viene utilizzata la monotonicit`a locale per implementare un servizio di multicast dotato di total order.
Propriet`a 1.2.3. (Evento di Vista Iniziale) Ogni evento di send, recv e safe prefix occorre in alcune viste. Formalmente:
ti = send(p, m) ∨ ti = recv(p, m) ∨ ti = safe prefix(p, m) ⇒ viewof (ti) 6=⊥
La vista iniziale pu`o essere determinata in due modalit`a:
1. All’avvio i processi usano il servizio di membership per ottenere una vista; la peculiarit`a di questa metodologia risiede nel fatto che non `e richiesta alcuna conoscenza predefinita del sistema.
2. Ogni processo decide autonomamente la sua vista iniziale senza comunicare nulla agli altri. Questo approccio equivale a possedere una vista iniziale di default utilizzando, per`o, un evento esplicito di installazione di tale view. La vista iniziale pu`o contenere un unico processo oppure consistere nella lista di tutti i processi che possono appartenere al sistema. In [39], tali possibilit`a vengono chiamate individual startup e collective startup. Bisogna notare, inoltre, che per installare elementi che non siano una vista dotata di un singolo elemento, un processo deve possedere a priori una conoscenza riguardo gli altri processi del sistema.
Propriet`a di Liveness
Il soddisfacimento della propriet`a di liveness `e dipendente dal comportamento della rete sottostante; con il modello presentato in precedenza non `e possibile affermare che tutte le esecuzioni siano corrette, ma, al contrario, bisogna fare ulteriori assunzioni mentre, al contempo, il soddisfacimento della specifica va condizionato al sistema sottostante.
In particolare si giunge ad una specifica per sistemi eventually stable ed una per sistemi instabili [28].
Nelle situazioni in cui il sistema diventa sincrono ad un certo momento della sua evoluzione, si pu`o pensare di implementare un servizio che sia “prima o poi” preciso. Nel caso di completa asincronia, invece, questo obiettivo `e irraggiungibile se non attraverso l’implementazione di failure detector esterni per cui nelle simulazioni in cui essi si comportano come degli eventually perfect, la propriet`a di liveness viene rispettata.
L’introduzione di un failure detector, per`o, comporta la necessit`a di estendere il modello creato in modo da aggiungere le azioni che rappresentano le interazioni tra la rete ed il failure detector stesso. ´E quindi ovvio come il rispetto della liveness dipenda fortemente dal failure detector e dalle assunzioni necessarie per implementarlo.
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) ∧ ti = net send(p, m) → ∃j | tj = net receive(q, m)
E stato pi`` u volte affermato come si possa giungere ad un comportamento ideale del servizio di Group Membership solamente nel caso in cui prima o poi la rete raggiunga uno stato in cui almeno un suo componente sia stabile e il failure detector si comporti come un eventually perfect. Avendo sottolineato questo specifico punto, risulta idoneo definire in maniera formale il concetto, intuitivamente chiaro, di componente stabile.
Definizione 1.2.2. (Componente stabile) Un componente stabile `e un insieme di pro- cessi sopravvissuti nel tempo e connessi ad ogni altro membro del gruppo, e per i quali tutti i canali che li uniscono a processi che non appartengono al componente stabile sono down.
L’esistenza di componenti stabili implica che la comunicazione fra di loro risulter`a, da un certo istante in poi, simmetrica e transitiva senza per`o assumere che lo sia sempre all’interno del modello.
Eventually Perfect Failure Detector (3 P) Lo scopo di questo paragrafo `e fornire in maniera intuitiva prima e formale poi il modello usato per definire un Eventually Perfect Failure Detector.
Un Eventually Perfect Failure Detector `e un individuatore di errori che, da un certo istante in poi, inizia a lavorare in maniera perfetta cessando di commettere errori:
esiste, dunque, un istante t dopo il quale la situazione della network riflessa dal failure detector `e perfettamente consona alla realt`a.
Da quanto detto fino ad ora, appare pi`u semplice comprendere le motivazioni per le quali sia impossibile, in un ambiente completamente asincrono, implementare un failure detector come quello di cui si `e parlato. La soluzione al problema, dunque, va individuata nell’utilizzo di un modello parzialmente sincrono capace di simulare in maniera soddisfacente una situazione reale e, al contempo, in grado di offrire un “upper bound” alla latenza sulle comunicazioni o la possibilit`a, per i processi, di misurare il tempo.
In un modello che rispetti le specifiche date o su reti che soddisfino l’assunzione 1.2.3, l’implementazione di un Eventually Perfect Failure Detector risulta agevole.
Saranno descritte ora le propriet`a di liveness limitate a group membership partition- able; in una group membership di tipo primary component, infatti, le specifiche non avrebbero validit`a in quanto potrebbero richiedere, nell’ambito di alcune situazioni, che un componente installi delle viste pur essendo al di fuori del componente pri- mario; in un ambito simile le propriet`a di liveness sarebbero dipendenti dalla specifica implementazione e dalla politica utilizzata e, dunque, non generalizzabili.
Liveness per modelli eventually stable In questo paragrafo verranno offerte ve- locemente alcune definizioni di liveness relative a sistemi che, prima o poi, hanno un componente stabile. `E dimostrabile [28] come un servizio di membership preciso sia difficile da risolvere come un eventually perfect failure detector tanto che i due problemi possano essere ridotti uno all’altro; in Figura 1.2 viene illustrata questa riduzione.
Si propongono quattro propriet`a di liveness [28]: Membership Precision, Multicast Liveness, Self Delivery and Safe Indication Liveness. Ognuna di esse abbisogna di un sistema che, oltre a diventare prima o poi stabile, sia dotato anche di un eventually perfect failure detector ( P).
MEMBtoFDp
View_chng
Group Membership
Network and Failure Detector (NET)
Net_send Net_recv Net_reachable
set
net_reachabl e set
Eventual PerfectFailure Detector Precise GroupMembership
Figura 1.2: Riduzione di una Precise Membership a un Eventually Perfect Failure Detector.
Propriet`a 1.2.4. (Liveness) Se il failure detector si comporta come un ♦ P allora per ogni componente stabile S esiste una view V con il member-set S tale che che le seguenti quattro propriet`a siano mantenute per ogni processo p in S:
1. Membership Precision p installa V come sua ultima vista
2. Multicast Liveness Ogni messaggio che p manda in V `e ricevuto da ogni processo
3. Self Delivery p consegna ogni messaggio che ha mandato in ogni view a meno che non vada down dopo averlo mandato
4. Safe Indication Liveness Ogni processo che p ha mandato in V `e indicato come “safe” da ogni processo in S
Formalmente la stabilit`a del componente `e richiesta da un certo punto in poi e per
tutto il resto dell’esecuzione; in pratica, essa `e necessaria solo per un tempo “abbastanza lungo”2da consentire l’esecuzione del protocollo e la stabilizzazione del failure detector.
Liveness per modelli mai stabili La possibile assenza di componenti stabili in un modello rende necessaria la definizione di una diversa propriet`a di liveness accostabile a tale situazione. La Membership Precision e la Multicast Liveness vengono rese dunque pi`u lasche dando origine alla Membership Accutacy ed alla Termination of Delivery:
Propriet`a 1.2.5. (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 installa, prima o poi, una vista che include q ed ogni vista installata successivamente includer`a q.
Propriet`a 1.2.6. Se un processo p invia un messaggio m in una view V allora per ogni membro q di V q consegna m oppure p installa una view V’ posteriore in V
Il rispetto di simili propriet`a non obbliga i processi a terminare, prima o poi, l’in- stallazione delle viste e, al contempo, non implica la propriet`a di membership precision.
Di contro, data l’assenza di componenti stabili, la Membership Accuracy non richiede che i processi siano tutti connessi tra di loro per installare la stessa vista e consegnare ogni messaggio. Sono state dunque offerte ai sistemi di group comunication le seguenti propriet`a:
1. capacit`a di determinare l’insieme dei processi che sono correntemente attivi;
2. possibilit`a di assicurare che i processi concordino sul successivo valore di questo insieme.
Le propriet`a di liveness enunciate in questa sezione hanno sub´ıto, a seconda delle implementazioni, alcune modifiche. In effetti `e spesso necessario, o pi`u comodo, uti- lizzare requisiti meno stringenti per rendere possibili alcune implementazioni: questo, per`o, porta con s´e la necessit`a di effettuare delle premesse nell’incipit di un lavoro in cui si specifica cosa viene garantito dal proprio studio e cosa `e stato lasciato da parte.
Una delle cause pi`u frequenti per cui si tende ad utilizzare propriet`a pi`u lasche `e la scalabilit`a: il dover garantire requisiti pi`u stringenti, infatti, va ad impattare spesso sull’adattabilit`a in termini di carico di lavoro che il sistema riesce a sostenere in caso di crescita della rete.
2tale periodo non `e quantificabile in ambiente asincrono in quanto dipendente da molte variabili esterne al sistema.
1.2.3 Rilassamento della Specifica: Eventual Group Membership La continua dinamicit`a apportata dalle join e dalle leave dei nodi non consente di fare assunzioni di sincronia sul sistema implicando l’inadeguatezza, in tale contesto, delle specifiche e delle implementazioni definite nella sezione precedente. In [51] viene estesa la specifica del problema di Group Membership e viene definita l’Eventual Group Membership che pu`o essere sintetizzata nel seguente modo:
Nel momento in cui la rete raggiunge un periodo di stabilit`a (in cui tutte le join e le leave cessano), ciascun nodo pu`o convergere ad una vista con- sistente in un tempo finito. Ciascuna operazione di join o di leave, inoltre, viene terminata in un tempo finito.
La prima parte della specifica rappresenta la propriet`a di safety mentre la seconda `e una propriet`a di liveness. In [51] vengono inoltre forniti e dimostrati i seguenti risultati di impossibilit`a:
Teorema 1. Se esiste un tempo t ∈ T tale che G(t) ≡ ∅ allora l’eventual group membership non pu`o essere risolta.
Teorema 2. Se esiste un tempo t ∈ T tale che G(t) non contenga membri stazionari3 allora l’eventual group membership non pu`o essere risolta.
Per ulteriori dettagli e una possibile implementazione della specifica si rimanda al testo integrale [51].
1.3 La Group Membership Probabilistica
L’approccio “deterministico” visto in precedenza per i sistemi distribuiti classici, non risulta idoneo quando il sistema in esame diventa di grandi dimensioni, come la maggior parte dei sistemi reali, ed `e proprio per questo motivo che attualmente la maggior parte degli sforzi nella ricerca sono volti nella direzione degli algoritmi probabilistici per la disseminazione dell’informazione. Un algoritmo probabilistico (o algoritmo di gossip), per inviare una comunicazione in broadcast, sceglie casualmente, tra il suo vicinato, un sottoinsieme di processi a cui inviare il messaggio; un nodo che riceve il messaggio a sua volta lo invier`a ad un altro sottoinsieme di suoi vicini, scelti anche loro
3si dice membro stazionario un processo che non invoca mai l’operazione di leave.
a caso; l’iterazione di questo procedimento fa s´ı che il messaggio sia diffuso per tutta la rete. In aggiunta a quanto detto va sottolineato anche come l’assenza di messaggi di acknowledgment, di sincronizzazione e di recovery per mancata ricezione siano parte fondamentale nella capacit`a di scalare e nel basso carico di cui i protocolli epidemiologici sono portatori.
Algoritmi di questa tipologia, inoltre, sono caratterizzati da una buona resistenza di base alla perdita dei pacchetti. `E infatti evidente come la selezione casuale possa provocare ridondanza nell’invio dei messaggi: un nodo i pu`o essere scelto un numero di volte superiore ad un altro nodo j come destinatario del medesimo messaggio, risul- tando cos`ı “probabilmente” resistente ad un eventuale fallimento della send sub´ıto dal nodo mittente o ad un eventuale fallimento di una receive sub´ıta da se stesso. Non trascurabile `e anche l’assenza di un Single Point of Failure in quanto nessun nodo della rete ha un ruolo fondamentale in essa e nessuno ha compiti particolari.
1.3.1 Caratteristiche dei Protocolli Gossip-based
Gli algoritmi di gossip vengono definiti “epidemici” in quanto la modalit`a di trasmis- sione dell’informazione tra i nodi `e simile alla diffusione di una malattia. Introdotti nel 1987 da importanti personalit`a nel campo della sistemistica distribuita [1], i moderni protocolli gossip-based sfruttano generalmente una metodologia basata sul manteni- mento di view parziali, in modo da non obbligare ogni nodo a mantenere le informazioni sull’intera rete e garantendo cos`ı una scalabilit`a maggiore pagandola, per`o, in termini di connettivit`a o resistenza ai guasti. La prima applicazione di tali protocolli `e avvenuta nel campo delle basi di dati con lo scopo di mantenere la consistenza dei database repli- cati in Xerox Corporate Internet [5] assicurando un meccanismo di multicast affidabile, la failure detection e la garbage collection degli oggetti4. Le principali caratteristiche di questi protocolli sono le seguenti:
• Scalabilit`a;
• Adattabilit`a;
• Degradazione graduale.
Per scalabilit`a si intende la capacit`a del protocollo di continuare ad avere buone performance anche a fronte di un aumento del numero di processi coinvolti; questo `e
4procedura di pulizia degli oggetti; nel caso specifico con questo termine si intende la procedura volta a eliminare dati obsoleti ed inutili dalle basi di dati.
possibile in quanto ciascun nodo invia un numero di messaggi costante e predeterminato o al pi`u crescente nell’ordine di log(n) a prescindere dal numero totale di nodi nella rete e tutto ci`o `e dovuto all’assenza di una conoscenza globale dei partecipanti, in favore di una locale comprensiva dei soli identificatori di alcuni processi ed alcune altre informazioni costanti. Le prestazioni, cos`ı, si avvicinano sempre all’ottimalit`a.
Per adattabilit`a si intende la capacit`a del protocollo di far fronte ai cambiamenti che avvengono nel sistema; quando nella rete c’`e una modifica, sia essa dovuta all’entrata di un nuovo nodo, all’uscita di un nodo che faceva parte della rete o ad un guasto, un pro- tocollo probabilistico `e capace di gestire queste trasformazioni senza altri meccanismi aggiuntivi ma direttamente attraverso il gossip.
Per degradazione graduale si intende la capacit`a del protocollo di funzionare corret- tamente con una probabilit`a che non decresca rapidamente all’aumentare del numero dei guasti. I protocolli deterministici affidabili hanno una limitatezza, prestabilita, in termini di resistenza ai guasti. Sovente nelle specifiche del protocollo appare la capacit`a che esso ha di resistere a f guasti. Nel caso in cui questi diventino f + 1 il protocollo avr`a un comportamento non corretto. L’affidabilit`a di un protocollo siffatto, dunque, sar`a calcolabile tramite la probabilit`a che non avvengano contemporaneamente pi`u di f failure. Un protocollo Gossip-Based, diversamente, non ha un numero predeterminato di guasti che ne implichi la terminazione del funzionamento corretto; il suo degrado
`
e condizionato al numero di failure ed aumenta leggermente, senza drastici risvolti, al sorpasso della soglia f .
Quanto detto non vuole essere un mero elogio della modalit`a epidemica di diffusione delle informazioni; gli aspetti positivi elencati trovano, ovviamente, anche una parte negativa derivante proprio dal loro lato probabilistico: probabilit`a, infatti, spesso `e sinonimo di incertezza. I destinatari dei messaggi hanno una probabilit`a, di variabile entit`a, di non ricevere il dato inviato; in una clique tale possibilit`a rimane bassa [48], ma questo non `e vero nel caso in cui la connettivit`a della rete non sia uniforme. In Figura 1.3 viene mostrato un esempio di diffusione attraverso gossip che ne evidenzia il lato probabilistico. Un protocollo di gossip, inoltre, ha il problema di trovare con difficolt`a un’espressione analitica che ne descriva il comportamento: spesso i migliori risultati sono ottenibili tramite un’equazione descrittiva del suo comportamento asin- totico per particolari reti con particolare topologia; in caso di reti pi`u complesse non si pu`o, comunque, prescindere dai dati sperimentalmente ottenuti tramite simulazioni o test predeterminati. Occorre sottolineare come la scalabilit`a sia un concetto dato
A
I C
D
E E
D C B Vicini di A
E D C B Vicini di A
F G
H B
L
M H
G F C Vicini di B
H G F C Vicini di B
M L I D Vicini di C
M L I D
Vicini di C Nodo raggiunto 2 volte
Nodo raggiunto 0 volte Nodo raggiunto 1 volta Iniziatore del gossip Invio a vicini non considerati in figura Invio di un messaggio
Nodo raggiunto 2 volte Nodo raggiunto 0 volte Nodo raggiunto 1 volta Iniziatore del gossip Invio a vicini non considerati in figura Invio di un messaggio
Figura 1.3: Esempio (con struttura semplificata) di diffusione di informazioni tramite protocolli Gossip-Based.
per certo solamente in termini di invio messaggi e di bilanciamento del carico. Per quanto riguarda i risultati in termini di gestione della membership, invece, la questione
`
e pi`u complessa; `e frequente trovare nelle specifiche l’assunzione che ogni processo sia a conoscenza di ogni altro processo presente nella rete. In casi di piccoli gruppi `e evidente come tale premessa sia trascurabile ma all’aumentare della dimensione della rete il peso di una simile assunzione aumenta fino a divenire una barriera invalicabile: memorizzare e gestire viste di un numero cos`ı elevato di nodi, infatti, pu`o risultare complicato.
1.4 La Group Membership nei Sistemi p2p
Con il termine “peer-to-peer” ci riferiremo a quella classe di sistemi la cui caratteristica distintiva `e quella di impiegare risorse distribuite per effettuare il proprio lavoro che sia di computazione distribuita, di “data sharing”, di distribuzione dell’informazione ecc. . . in maniera distribuita [9, 22].
In questo capitolo verr`a osservato pi`u da vicino tale ambiente che rappresenta l’ambito nel quale si muove la parte di ricerca in cui questo lavoro pu`o essere inserito.
1.4.1 I Sistemi p2p
In sostanza il p2p `e un particolare sistema distribuito, privo di qualsivoglia organiz- zazione gerarchica o controllo centralizzato, in cui tutti i nodi svolgono la medesima funzione (sono sia client che server) e mantengono localmente una lista delle risorse che intendono condividere con il resto del sistema. Appare quindi evidente la differenza di funzionamento tra questo paradigma e quello client/server. Nel c/s (Figura 1.4(a)), l’approccio alla disseminazione dell’informazione `e focalizzato sul server che quindi rap- presenta il “collo di bottiglia” del sistema, nonch`e un Single Point of Failur ; d’altro canto `e ben noto dove si trovano fisicamente le risorse e la dinamicit`a dei nodi non crea problemi in quanto essi sono direttamente collegati soltanto con il server.
Nel p2p (Figura 1.4(b)) tutto `e distribuito e ciascun nodo ha la possibilit`a di effet- tuare delle query per trovare la risorsa desiderata, cos`ı come di fornire risorse agli altri peer; i vantaggi e gli svantaggi di questa concezione sono molteplici: tra i primi `e intu- itivo individuare una maggiore resistenza ai guasti (a seconda della struttura dell’over- lay possono essere tollerati diversi guasti, continuando ad avere il medesimo servizio), mentre tra i secondi `e evidente la maggiore sensibilit`a del sistema alla dinamicit`a dei nodi.
SERVER
CLIENT CLIENT
CLIENT CLIENT
CLIENT
CLIENT
(a) Modello di sistema client/server
PEER PEER
PEER
PEER
PEER PEER
PEER
PEER PEER
(b) Modello di sistema peer-to-peer
Figura 1.4: Modelli di sistema.
Applicazioni
Le principali applicazioni del paradigma del p2p sono senza dubbio rappresentate dal file sharing: sistemi come Napster [43], Kazaa [40] e Gnutella [27], noti a tutti, rappre- sentano la prima espressione concreta dello spirito del p2p; milioni di peer si uniscono per formare un’enorme rete che lavora, servendosi dei protocolli della pila di Internet, per lo scambio di contenuti per lo pi`u multimediali (file audio e video). Altra ap- plicazione conosciuta `e Freenet [30] nata per garantire la libert`a di parola elettronica tramite l’immagazzinamento e la ricerca di dati in maniera del tutto anonima. ´E una rete che elimina per chiunque la possibilit`a di imporre la sua scala di valori sugli altri;
in altre parole, a nessuno `e permesso decidere cosa sia accettabile e cosa invece con- dannabile e la tolleranza verso le opinioni altrui `e fortemente incoraggiata richiedendo agli utenti di non prestare attenzione ai contenuti che non approvano [55].
Architettura
Gli attuali modelli di sistema p2p sono suddivisibili in tre gruppi principali [13]
• Centralizzati ;
• Decentralizzati non strutturati ;
• Decentralizzati strutturati.
I sistemi centralizzati comprendono i sistemi “Napster-like” [43] che mantengono una directory delle risorse disponibili costantemente aggiornata risiedente su uno o pi`u serv- er centrali. Ogni volta che un nuovo peer si aggiunge alla rete non deve far altro che comunicare al server centrale le risorse di cui dispone, in modo tale da poter lavorare come server per gli altri peer; un nodo che desidera accedere alle risorse deve inviare la richiesta al server centrale ottenendo in risposta la lista dei peer che posseggono tali risorse per poi mettersi direttamente in comunicazione con loro. I problemi principali di tali sistemi risiedono nella loro debolezza in termini di scalabilit`a rispetto alla dimen- sione della rete nonch`e nella presenza di quello che chiameremo Single Point of Failure, ossia di un punto della rete il cui guasto provocherebbe la disconnessione della stessa.
In Figura 1.5 `e schematizzato un sistema di tipo centralizzato.
3,6,8 C
…
…
2,5,7,8 B
1,4,9 A
Nodi proprietari Risorsa
Server Centralizzato
Request (B)
Response (B)
Request (C)
Response (C)
Request (Address, C)
Response (6, C) 4
5 6
1
2
3
Figura 1.5: Modello di funzionamento di un sistema p2p centralizzato.
Tra i sistemi decentralizzati strutturati si trovano tutti quei sistemi che hanno una struttura topologica della rete obbligata in grado di offrire, tramite specifico piazza- mento delle risorse, primitive di individuazione dei dati altamente ottimizzate. A loro volta, tali sistemi possono essere suddivisi in loosely structured, dove la topologia della rete tende alla randomicit`a ma il piazzamento delle risorse `e determinato tramite speci- fici algoritmi, e highly structured, in cui sia la topologia della rete che l’organizzazione
delle risorse hanno strutturazione obbligata.
I sistemi decentralizzati non strutturati sono quelli in cui la topologia della rete `e pressoch`e randomica o costruita tramite lasche regole e, allo stesso tempo, il piazzamen- to delle risorse non `e controllato da alcuna entit`a o algoritmo. In tali sistemi l’overhead generato da operazioni di ingresso ed uscita dal sistema di un nodo `e generalmente pi`u basso rispetto ai precedenti ma, di contro, tende a rendere la fase di individuazione delle risorse pi`u costosa. La gran parte di algoritmi di resource discovery in tali ambienti ricorre a flooding sulla rete o a tecniche di random walk [15, 26].
In conclusione, una citazione `e dovuta ad una architettura che ha svariati punti in comune con i sistemi p2p: Mobile Ad Hoc Networks (MANETs). Essa consiste in una rete speciale costruita da nodi che sono in grado di muoversi in uno spazio limitato e comunicare tramite link wireless [49].
1.4.2 Evoluzione del p2p: le generazioni
Il peer-to-peer ha avuto in breve tempo un’evoluzione frenetica. In questo para- grafo saranno illustrate velocemente e con alcuni esempi, selezionati tra molti, le tre generazioni che hanno portato al p2p moderno [14].
Prima Generazione
La prima generazione di p2p `e facilmente illustrabile utilizzando come esempio i due sistemi pi`u diffusi ed iniziatori delle due sottofamiglie principali, Napster e Gnutella, i cui sistemi sono schematizzati in Figura 1.6.
Napster Napster [43], il sistema di scambio di file musicali iniziatore del p2p, ed altri ambienti simili hanno uno o pi`u server centrali che mantengono una directory sempre aggiornata di oggetti e che vengono usati dai peer come riferimento per l’individuazione delle fonti fisiche da cui scaricarli. Nella fattispecie, il nodo effettua il login al server a cui invia la lista dei file che pu`o offrire; da questo momento esso pu`o effettuare le proprie richieste e ricevere le informazioni per soddisfarle. La centralizzazione del server evita problemi come il routing delle query diffusi in altri sistemi ma lo rende sensibile a problemi dovuti a Single Point of Failure e poco scalabile.
Gnutella Gnutella [27], sistema di file sharing e base di partenza nello studio del p2p puro, `e un sistema caratterizzato dall’assenza tanto di una directory centralizzata
quanto di un controllo sulla topologia della rete o sul posizionamento dei dati rendendo distribuita la ricerca delle risorse. Un nodo che decide di utilizzare Gnutella deve collegarsi a un qualsiasi nodo gi`a presente nella rete del sistema ed ottenere da esso una lista di altri nodi esistenti. Nel momento in cui ha effettuato il proprio ingresso, un nodo pu`o effettuare query di ricerca rivolgendosi ai propri vicini; la richiesta viene inviata in broadcast a tutti i vicini entro un certo raggio sottostando al meccanismo del TTL5. Un’architettura di questo genere `e intuitivamente molto pi`u resistente ad ingressi ed uscite di nodi ed ai guasti nonostante essa abbia un meccanismo di flooding poco scalabile; recentemente sono stati pensati in merito dei meccanismi di random walk e di “dynamic TTL setting”.
Figura 1.6: Napster Model vs Gnutella Model.
5Time To Leave.
Seconda Generazione
Le architetture appartenenti a questa famiglia sono caratterizzate dall’assenza del serv- er centrale ma, al contempo, dalla presenza di una topologia di rete strettamente con- trollata e di una precisa struttura (Ring [32], albero k-ario [52] ecc.) nonch`e di un piazzamento fisico delle risorse studiato in modo da rendere consecutive le query pi`u facili da soddisfare; tali architetture supportano spesso meccanismi basati su tabelle hash.
In questo paragrafo verranno brevemente considerati due tra i pi`u famosi p2p di seconda generazione: Chord [32] e CAN [53] che nuovamente saranno messi a confronto in Figura 1.7.
Figura 1.7: Chord Model vs CAN Model
Chord Il funzionamento di tale algoritmo `e basato su Tabelle Hash Distribuite (DHT) e sul mantenimento di un key space. Il key space pu`o essere immaginato come una sequenza di locazioni, ordinate ed identificate dalla propria chiave, che costituiscono una sequenza ad anello; le chiavi sono rappresentate da numeri interi scelti in un intervallo predefinito con estremi [0, 2h] con h ∈ N. Per ogni possibile chiave esiste una locazione ed ogni nodo del sistema `e rappresentato da una chiave calcolata tramite una funzione di hash [35, 17] h(x) applicata all’indirizzo IP del nodo e definita id del nodo; tramite hashing consistente i nodi vengono distribuiti nel key space in modo da bilanciare il sistema e minimizzare l’overhead generato quando un nuovo nodo entra o esce dal
sistema. La strategia di assegnazione delle chiavi prevede che ogni locazione identificata da una chiave k sia memorizzata nel primo nodo il cui id `e uguale o seguente a k nel key space; tale nodo `e chiamato il successore del nodo con chiave k e denotato con la scrittura successor(k).
Figura 1.8: Esempio di Key Space con 16 locazioni e 3 nodi fisici.
In Figura 1.8 `e rappresentato un key space popolato da tre nodi e con h = 4. La locazione, identificata con chiave k = 7, `e memorizzata nel nodo con id = 10. Ogni nodo mantiene una tabella di route con h entry chiamata finger table; la i-esima entry in questa tabella mantiene l’identit`a del primo nodo, n0, la cui chiave, k0, succede la chiave k di n di almeno 2i-1 posti nel key space. Chiameremo n0 l’i-esimo finger del nodo n; va evidenziato come il primo finger di n sia il suo successore immediato sull’anello. In Figura 1.8 si pu`o osservare un esempio della finger table per il primo nodo rappresentato; le linee tratteggiate che partono da k = 1 rappresentano le chiavi puntate dai finger; quando un nodo vuole inviare un messaggio alla locazione identificata dalla chiave k e non compare nella sua finger table, esso inoltra il messaggio ad un altro nodo della rete pi`u vicino alla chiave cercata e tale meccanismo viene iterato. Ogni step dimezza, intuitivamente, la distanza di un nodo da ci`o che cerca rendendo dunque logaritmica rispetto alla grandezza della rete la complessit`a di ricerca e cosi ottimale tale operazione.
CAN In CAN [53], ogni chiave viene indirizzata uniformemente tramite hashing in uno spazio d-dimensionale. Quando un nodo effettua un’operazione di join, esso sceglie
casualmente un punto di tale spazio, ne divide in due parti la regione e diviene respons- abile di una delle due sezioni risultanti mantenendo tutte le chiavi i cui id appartengono alla propria regione. Il routing viene poi effettuato inoltrando le richieste alle regioni vicine alla posizione della chiave. La lunghezza attesa di una ricerca `e dunque O(√d
N ) e le informazioni di stato mantenute sono O(d).
Terza Generazione
In questa fase si `e cercato di trovare topologie alternative per il p2p e algoritmi nuovi, capaci di offrire una buona tolleranza ai guasti. In generale, la replicazione degli oggetti ed altre tecniche possono garantire un miglioramento in tal senso.
Low Diameter Questo protocollo [44] `e concepito per fare in modo di avere un grafo con un diametro breve O(log N ) ed un degree dei nodi limitato, garantendo cos`ı un overhead minore delle query e dei messaggi di controllo.
Butterfly Butterfly [4, 34] `e un sistema resistente per accedere ad N data items in una rete di N nodi. Le sue caratteristiche possono essere racchiuse nel fatto che ogni ricerca richiede O(log N ) tempo e, al pi`u, O(log 2N ) messaggi; inoltre ogni nodo necessita soltanto di O(log N ) memoria.
1.4.3 Overlay Networks
Un’overlay network `e una rete costruita al di sopra della rete fisica e, generalmente, da essa indipendente. La caratteristica con cui l’overlay integra la controparte fisica
`e rappresentata dal fatto che le connessioni tra i nodi possono essere viste come link diretti virtuali (o logici) corrispondenti a cammini sulla rete fisica fatti di un numero di step maggiore o uguale ad uno(Figura 1.9). Le Overlay Network possono essere utilizzate per permettere il routing dei messaggi verso destinazioni che non hanno un indirizzo IP specifico e, nel contesto del p2p, rappresentano quello che viene chiamato
“grafo delle conoscenze” e che consente l’interazione e lo scambio di risorse. Quan- to detto rende ovvio come il problema del loro mantenimento sia di grande rilevanza nell’ambito di sistemi decentralizzati in cui, a differenza delle strutture centralizzate, le connessioni tra o vari peer non vengono stabilite soltanto al momento della comu- nicazione effettiva e sono “permanenti”. Nelle pagine che seguono, dunque, verranno considerati esclusivamente i sistemi decentralizzati.
Physical Network Overlay Network
Figura 1.9: Schematizzazione di un’overlay network
I Sistemi Strutturati
Come precedentemente accennato, i sistemi strutturati hanno vincoli stringenti in ter- mini di modalit`a con cui i nodi della rete sono disposti. Una buona parte di essi [32, 2, 53] utilizza Tabelle Hash Distribuite (DHT) con le quali `e possibile fornire un mapping molti-ad-uno tra i dati ed i nodi tramite il mantenimento di un key space nel quale si pu`o facilmente fare storage e retrive delle risorse. In 1.4.2 `e stato illustrato Chord, un esempio di funzionamento di DHT e di spazio delle chiavi. Come gi`a detto,
`
e interessante notare come in sistemi basati su DHT sia possibile ottimizzare la ricerca (nel caso di Chord `e intuitivamente logaritmica); un altro punto di interesse di tali sistemi `e la resistenza a crash di nodi; quando un nodo fisico va down, tutte le locazioni di cui era responsabile sono mosse in un altro nodo ancora presente nella rete: questo
`
e possibile in quanto le locazioni sono luoghi astratti nello spazio virtuale delle chiavi facendo s´ı che, da un punto di vista astratto, le locazioni siano sempre raggiungibili anche se tendono a perdere il loro stato quando il nodo fisico che ne `e responsabile subisce un guasto che lo sconnette dalla rete. Di contro, il posizionamento delle risorse e la struttura della rete causano un overhead non indifferente per le operazioni di join e di leave: `e per questa ragione che sistemi di tipo strutturato sono spesso considerati non ottimali per applicazioni caratterizzate da alto dinamismo, appartenenti alla famiglia
