Rimuovere nodi

In un’overlay in ambiente dinamico i nodi possono uscire dal sistema per varie ragioni, volontarie o meno. In CYCLON non viene utilizzato alcun sistema esplicito per le operazioni di leave volontarie, limitando a rilevarle come viene effettuato con i guasti.

In pratica, quando un nodo inizia un’operazione di shuffle con un vicino e non ottiene risposta, dopo un timeout, di durata ad esempio pari al periodo di shuffle ∆T , il nodo verr`a rimosso.

La presenza del parametro age definisce un valore chiave per determinare l’ordine con cui i nodi vengono contattati. Una entry pi`u recente, e quindi molto probabilmente ancora attiva, avr`a molte meno probabilit`a di essere scelta di una entry ormai da lungo tempo nella cache, e a cui corrisponde una probabilit`a maggiore di uscita dal sistema. In conclusione gli autori vogliono mostrare, in base ai dati ottenuti dalle prove spe-rimentali, che l’overlay ottenuta da questo meccanismo converga, in molte situazioni, ad un grafo casuale4 dopo un certo numero di cicli di esecuzione dell’algoritmo. Tale convergenza si ottiene, ad esempio, per il valor medio dello shortest path lenght mentre per altri parametri, come per la distribuzione del node-degree, si ottiene un comporta-mento migliore rispetto a quello di un grafo casuale. Inoltre CYCLON, sempre nelle

3Vedremo in 3.2.2 che questo semplicemente non `e poi cos`ı semplice

simulazioni mostrate dagli autori, sembra essere in grado di sopportare cambiamenti consistenti nella overlay pur mantenendone la connettivit`a5.

La dimensione della shuffle lenght non sembra influenzare di molto il comporta-mento del protocollo, a meno di scegliere valori estremi tipo l = 0 o l = c per cui il comportamento di CYCLON peggiora.

Capitolo 3

P2P Membership per WAN

Scopo di questo capitolo `e mostrare approfonditamente due protocolli di group mem-bership completamente distribuiti (o p2p). In particolare ogni implementazione di un protocollo di group membership completamente distribuito si trova ad affrontare due problematiche fondamentali relative all’accesso e alla scalabilit`a.

Accesso In una soluzione server-based i punti di accesso sono costituiti da dei server tolleranti ai guasti, che si suppone siano sempre disponibili; in una soluzione p2p i punti di acceso sono peer comuni. I peer sono dinamici per natura e quindi i punti di accesso possono cambiare continuamente. Questo porta a tre problemi fondamentali:

1. un’operazione di join non ha alcuna garanzia di avere termine in un tempo finito;

2. complesso definire l’insieme iniziale dei peer che sono considerati come access point;

3. join concorrenti in un gruppo vuoto possono formare due, o pi`u, insiemi di processi completamente partizionati.

Scalabilit`a In un’implementazione server-based i server possono manipolare solo le informazioni di membership senza partecipare alle comunicazioni applicative, in un sistema peer-to-peer, invece, ogni membro compie entrambe le operazioni. In questa situazione la dimensione delle viste mantenute da ogni peer fornisce una misura dell’overhead di un messaggio. A causa di questo, la size deve essere

propriamente scelta e mantenuta anche in condizioni dinamiche, e dovrebbe rap-presentare un buon trade-off tra scalabilit`a e robustezza. Usualmente per venire incontro ai requisti di scalabilit`a, ogni peer ha solamente una vista parziale, cio`e comunica soltanto con i suoi vicini. questa neighborhood relation pu`o essere vi-sta come un grafo non pienamente connesso rappresentante l’overlay network su cui avviene la comunicazione. Questa overlay pu`o partizionarsi se una numero molto elevato di peer contigui esce dal sistema simultaneamente. Considerando i guasti molto meno probabili di una leave in un sistema altamente dinamico, la possibilit`a di controllare leave concorrenti pu`o essere vista come un sistema per irrobustire la soluzione.

SCAMP e DET affrontano questi problemi con due approcci diametralmente op-posti: l’uno probabilistico, l’altro deterministico. Nel Capitolo 4 si confronteranno i risultati ottenuti da entrambi in contesti di alta dinamicit`a.

3.1 SCAMP

SCAMP `e un protocollo completamente decentralizzato e auto-configurante, in grado di variare la size della local view del singolo nodo in base alle dimensioni complessive del gruppo. Come gi`a detto le dimensioni della local view e il conseguente numero di di gossip targets sono parametri fondamentali per ottenere un livello soddisfacente di consegna dei messaggi di multicast. La sola scelta casuale permette di ottenere una certa resistenza ai guasti e di rendere possibili operazioni decentralizzate ma la questione da affrontare risiede in quanto deve essere grande il sottoinsieme dei gossip targets in ogni nodo per ottenere una propagazione affidabile del messaggio a tutti i membri del gruppo con una elevata probabilit`a. In [1] `e stata utilizzata la teoria matematica sulle epidemie per legare la probabilit`a che un membro del gruppo riceva il messaggio alla dimensione del sottoinsieme dei destinatari del gossip. In [2] gli autori di SCAMP hanno ottenuto un risultato in base al quale se ogni nodo, in media, invia ad

log(n) + k altri nodi messaggi di gossip, la probabilit`a che ogni nodo riceva il messaggio

converge a e−e−k

. In generale bisogna far riferimento al log(n) come ad un threshold scendere sotto il quale fa decadere in maniera verticale le prestazioni di un sistema gossip-based. I requisiti che si sono voluti ottenere da questo protocollo sono:

• Scalabilit`a: la taglia della Partial View di ogni nodo dovrebbe crescere molto lentamente rispetto alla dimensione del gruppo.

3.1. SCAMP 45

• Affidabilit`a: la partial view di ogni nodo dovrebbe essere grande abbastan-za da supportare il gossip con un’affidabilit`a comparabile a quella ottenuta dai tradizionali schemi che richiedono una conoscenza completa della group memebership.

• Operazioni Decentralizzate: la partial view dovrebbe essere aggiornata

quan-do un membro si sottoscrive o si ritira dalla membership mantenenquan-do le propriet`a precendenti. L’aggiornamento dovrebbe essere eseguito utilizzando solo propriet`a locali. La cardinalit`a della partial view dovrebbe poter scalare in funzione della taglia del sistema anche se nessun nodo conosce tale dimensione.

• Recupero dall’isolamento: una propriet`a importante dei sistemi gossip

tradi-zionali risiede nel fatto che, quando un nodo invia un messaggio di multicast per farlo seleziona casualmente i suoi destinatari. In questo modo anche se un nodo pu`o, occasionalmente, mancare un messaggio, accade solo con bassa probabilit`a che tale evento si presenti ripetutamente. In un sistema in cui il nodo seleziona i sui gossip targets da una partial view che pu`o rimanere invariata per molto tempo risulta necessario prevedere un meccanismo di recovery per prevenire fenomeni di isolamento.

Nelle seguenti sottosezioni mostreremo tale protocollo di membership per come `e stato pensato per risolvere le problematiche su esposte, pi`u precisamente in 3.1.1 affronteremo le carateristiche salienti di SCAMP mentre in 3.1.2 presenteremo i meccanismi adottati per ribilanciare le partial view create dal protocollo nel caso di pattern di sottoscrizioni particolarmente sbilanciati.