Caratteristiche base di SCAMP

Alla base di SCAMP abbiamo tre meccanismi di subscription, unsubscription e di recupero dall’isolamento. Come gi`a detto la vista parziale dei singoli nodi evolve in modo completamente decentralizzato.

SCAMP utilizza due strutture di dati ed una serie di messaggi per eseguire tutte le operazioni previste. Ogni nodo mantiene, quindi, le seguenti strutture dati:

• PartialView, contenente tutti i nodi a cui pu`o inviare messaggi di gossip; • InView, contenente tutti i nodi da cui pu`o ricevere messaggi di gossip.

Vengono inoltre utilizzati alcuni tipi di messaggi che indicheremo nel modo seguente e il cui scopo sar`a chiarito con il procedere del testo:

• New Suscription • Forwarded Subscription • Update • Unsubscription • Heartbeat Subscription

L’algoritmo di sottoscrizione `e il seguente

1. Contatto: Un nodo, che voglia entrare nel gruppo, esegue il join inviando una richiesta di sottoscrizione, New Subscription, ad un membro arbitrario chiamato

contatto. Il nodo inizia con la sua Partial View popolata soltanto dal contatto.

2. Nuova sottoscrizione: Quando un nodo riceve una richiesta per una nuova sottoscrizione, tramite il messaggio di New Subscription, invia la richiesta stessa a tutti gli elementi della sua vista locale, tramite dei messaggi di Forwarded

Subscription. Inoltre crea c copie addizionali della sottoscrizione e le invia a

nodi scelti casualmente fra i membri della sua PartialView, c `e un parametro che determina il numero di guasti tollerati dall’algoritmo.

3. Rinviare una sottoscrizione: Quando un nodo i riceve una Forwarded

Sub-scription, verifica che il sottoscrittore non sia gi`a contenuto nella sua vista locale:

se non `e presente allora lo integra con una probabilit`a che dipende dalla dimensio-ne della P artialV iew_i, pi`u precisamente la probabilit`a `e p = ¹

1 + |P artialV iew_i|^;

se non accetta la nuova sottoscrizione allora questa verr`a rinviata ad un nodo scelto casualmente nella sua vista locale.

4. Accettare una sottoscrizione: Se il nodo i decide di accettare una sottoscri-zione da parte del nodo j, lo aggiunge alla P artialV iew_i e invia a quest’ultimo un messaggio di Update, indicandogli di aggiungere i alla InV iew_j.

3.1. SCAMP 47

New Subscription

1 {La sottoscrizione di s `e inviata a tutti i nodi della vista} 2 for each n ∈ PartialViewcontact

3 Send(n, s,forwardedSubscription);

4 {c copie addizionali della sottoscrizione s sono inviate a nodi casuali della vista} 5 for (j = 0; j < c; j + +)

6 Scegli casualmente n ∈ PartialVievcontact 7 Send(n, s,forwardedSubscription);

Figura 3.1: Management dei messaggi di New Subscription

Forwarded Subscription

1 {n riceve s e lo aggiunge con probabilit`a p = 1/(1+size of PartialViewn)} 2 if (s ∈ PartialViewn)

3 then PartialViewn= PartialViewn+ {s};

4 else

5 Scelta casuale di ni∈ PartialViewn

6 Send(ni, s,forwardedSubscription);

Figura 3.2: Management dei messaggi Forwarded Subscription

Di seguito viene presentato per maggiore semplicit`a lo pseudo-codice per la gestione delle New Subscription (Figura 3.1) e delle Forwarded Suscription (Figura 3.2).

Una sottoscrizione cos`ı eseguita permette agli autori di dichiarare che, nel caso in cui una nuova sottoscrizione venga inviata ad un nodo scelto casualmente fra i membri esistenti, allora il sistema configura s´e stesso per avere local view di dimensioni medie pari a (c + 1) log(n). Dove n `e il numero di nodi nel sistema e c un parametro di design. ´

E stato gi`a notato come la probabilit`a che un messaggio sia ricevuto da ogni membro del gruppo esibisca un threshold molto rapido intorno a log(n): risulta essere molto bassa per PartialView in media pi`u piccole di log(n), mentre diviene prossima ad 1 per PartialView maggiori di log(n). Questi risultati possono essere applicati anche a sistemi in cui sia prevista la presenza di guasti di nodi e link: in questo caso, se un link pu`o fallire con probabilit`a ε, in modo statisticamente indipendente dagli altri, allora il threshold diviene di (log(n)/(1 - ε)). Un’altra ragione alla base della decisione di mantenere una vista locale di dimensione (c + 1) log(n) per alcuni c > 0 `e la possibilit`a di scegliere differenti sottoinsiemi di dimensione log(n) + k come destinatari del gossip.

Tale possibilit`a porta gli autori ad affermare che guasti di nodi e link non possano causare un partizionamento persistente del sistema, grazie ai meccanismi di recovery propri dei tradizionali protocolli di gossip. Si pu`o, cio´e, usufruire in parte delle propriet`a di reliability di una vista globale pur mantendo una P artialV iew di dimensioni limitate. Per ultimo la probabilit`a di accettazione di una Forwarded Subscription pari a

p = 1/(1 + |PartialView_n|) trova duplice giustificazione in due considerazioni: per

prima cosa la necessita di avere una probabilit`a decrescente con la dimensione corrente della PartialView per ottenere viste locali il pi`u possibile bilanciate nei diversi nodi e, di conseguenza, concentrate il pi`u possible intorno alla media della cardinalit`a della vista; in seconda ed ultima, assumendo che le |P artialV iew| siano tutte prossime a (c + 1) log(n), allora il numero di passi prima che una sottoscrizione venga accettata sar`a mediamente pari a (c + 1)log(n). Quest’ultimo assunto nasce dai risultati in [26] in cui viene mostrato come il grafo casuale che si sta considerando abbia diametro proporzionale al log(n) e, di conseguenza, gli autori si aspettano che il valore scelto per p sia sufficientemente ampio da permettere alla sottoscrizione di attraversare una buona parte del sistema, prima di essere accettata da qualche nodo.

Modellando il sistema come un grafo direzionale, in cui i nodi corrispondono a un membri del gruppo e esiste un arco diretto (x, y) quando y `e nella PartialView di x, quando un nodo si sottoscrive l’algoritmo creer`a un numero di archi casuali dipendenti dal nodo scelto come contatto. Supponendo che il nodo scelto abbia un out-degree di

d il numero di archi creato sar`a di d + c + 1. Consideriamo allora un sistema di n

nodi e indichiamo con E[M_n] il numero di archi quando il numero di nodi `e n allora l’out-degree medio di ogni nodo sar`a pari a E[M_n]/n. Assumendo che un nuovo nodo si sottoscrive ad un nodo scelto casualmente otteniamo

E[M_n] = E[M_n−1] +^E[Mn−1]

n − 1 ^{+ c + 1}

dal quale si ottiene E[M_n] ≈ (c + 1)n log(n). Quest’ultimo risultato `e molto importante ai fini della scalabilit`a, uno dei requisiti e dei pregi pi`u forti di un gossip-based. Questo risultato mostrato in [4] costituisce il nucleo fondante di SCAMP: la sua capacit`a di adattare la vista locale alle dimensioni complessive del gruppo in modo totalmente autonomo e senza il bisogno di interventi esterni. Come vedremo nelle simulazioni eseguite, tale capacit`a di adattamento viene preservata da SCAMP anche in condizioni di forte dinamismo pur se i risultati sul lato della reliability non sono stati soddisfacenti cos`ı come gli autori affermavano.

3.1. SCAMP 49

Unsubscription

La Unsubscription deve conservare la proporzione fra le size delle view dei singoli nodi e la dimensione complessiva del sistema. Dato un nodo n₀, che vuole abbandonare il gruppo, con P artialV iew_n0 = {i(1), . . . , i(l)} ed InV iew_n0 = {j(i), . . . , j(l⁰)}, questi comunicher`a ai membri della InV iew_n0, di aggiornare la propria P artialV iew_j nel seguente modo:

• I nodi j(1), j(2), . . . , j(l⁰ − c − 1) rimpiazzano n₀ con, rispettivamente,

i(1), i(2), . . . , i(l0− c − 1)1.

• I nodi j(l0− c), . . . , j(l0) rimuoveranno semplicemente n₀ dalla loro P artialV iew Nel caso in cui un nodo si trovi nella situazione in cui `e costretto dalla Unsubscrip-tion di un vicino a possedere pi`u copie dello stesso nodo nella sua PartialView, o a mantenere il proprio id in tale lista, si rimuove semplicemente l’id in questione. Questo meccanismo rimane limitato al nodo che intende lasciare il gruppo e coinvolge sola-mente i suoi diretti vicini nel grafo della overlay network. Questo procedimento viene eseguito per motivazioni di tipo euristico e di mantenimento di una size (c + 1) log(n) infatti in un sistema con n nodi e M_n archi, il numero degli archi decresce con la di-mensione della PartialView cio`e, in media, di M_n/n. Inoltre anche i c + 1 nodi che sono

stati contaminati con il messaggio di Forwarded Subscription sostituiranno il nodo in questione con un elemento della PartialView di quest’ultimo e quindi il numero degli archi decrementer`a di un ulteriore c + 1. Assumendo che E[M_n] ≈ (c + 1)n log(n) si ottiene

E[M_n−1] = E[M_n] −^E[Mn]

n ^{− (c + 1)} ≈ (c + 1)(n − 1) µ log(n) − ¹ n − 1 ¶ ≈ (c + 1)(n − 1) log(n − 1)

La Unsubscription quindi `e in grado di preservare il valor medio del degree.

Unsubscription e Correttezza delle viste Abbiamo appena detto che la pro-cedura di Unsubscription permette di conservare il valor medio del degree di ogni nodo

ma non si `e detto nulla sulle conseguenze riguardo la correttezza delle viste dopo un aggiornamento come quello appena descritto. Il punto su cui focalizzare l’attenzione `e la mancanza di un aggiornamento, o almeno di un tentativo di aggiornamento, del-le InView. Infatti, quando un nodo p_i vuole lasciare il gruppo comunica ai nodi, i cui identificatori sono contenuti nella InV iew_i di aggiornare la propria P artialV iew, sostituendo p_i con un nuovo Id o cancellandolo solamente. In caso di aggiornamento non viene inviata alcuna comunicazione ai nodi contenuti nella P artialV iew_i, molti dei quali conterrano p_i nella propria InV iew, riguardo l’uscita di p_i dal gruppo e il loro possibile nuovo padre. In tal modo quando i nodi contenuti nella P artialV iew_i vorran-no lasciare il sistema potrebbero vorran-non comunicare ai loro nuovi padri di aver invocato la procedura di Unsubscription e questi ultimi si ritroverebbero con dei nodi nelle loro

P artialV iew non pi`u validi.

La presenza di nodi non validi porta ad avere viste dimensionate in modo erroneo, perch´e contenenti nodi ormai non pi`u presenti nel sistema, e quindi a rifiutare nuove sottoscrizioni ma non solo: crea problemi anche nei meccanismi di lease e heartbeat, in cui potrebbe essere scelto un nodo non attivo per la risottoscrizione, rendendo di fatto inutile, per quell’intervallo di tempo, la procedura stessa.

Chiaramente problematiche legate ai nodi non validi sarebbero comunque presenti in conseguenza di guasti, di nodi o di link, o di leave concorrenti ma quanto detto fino ad ora risulta valido anche in assenza di suddette condizioni.

Recupero dall’isolamento

Il meccanismo di sottoscrizione permette la creazione di un grafo connesso ma d’altra parte i nodi possono guastarsi ed uscire dal sistema e questo pu`o causare la disconnes-sione del sistema e l’isolamento di alcune sue parti. Un nodo si isola nel grafo quando non sussistono pi`u membri attivi della membership che contengono l’id del grafo nella propria PartialView, quando tutti i nodi che contengono l’identificatore del nodo nella loro PartialView si sono guastati. Per risolvere questo grave problema gli autori hanno proposto il meccanismo degli heartbeat che consiste nel semplice rinvio periodico di un messaggio, il messaggio di Heartbeat appunto, da parte di ogni nodo i a tutti i membri della sua P artialV iew_i. Un nodo che non riceve un messaggio di Heartbeat per un de-terminato intervallo di tempo T_H, rileva il suo stato isolato e provvede a risottoscriversi ad un nodo arbitrario appartenente alla sua vista locale. Anche il meccanismo della

3.1. SCAMP 51

Isolamento e Consegna Occorre in questa sede specificare che il recupero di un nodo da una situazione di isolamento non implica che il nodo stesso sia in grado di consegnare un messaggio a tutti i membri del gruppo, cos`ı come un nodo non isolato, secondo quanto appena detto e cio`e in grado di ricevere almeno un messaggio da un elemento del gruppo, non `e detto che sia in grado di ricevere messaggi da tutti gli elementi del gruppo stesso.

Per chiarire la situazione, la cui causa `e da ricercarsi nella struttura direzionale del grafo generato dal protocollo SCAMP, si pu`o far riferimento alla situazione di partenza evidenziata dal grafo in Figura 3.3, dove viene mostrata una sezione del grafo risultante da una esecuzione della simulazione in base ai criteri che verranno enunciati pi`u accuratamente nel Capitolo 4.

In tale grafo il nodo i-esimo rappresenta un processo membro del gruppo nell’istante di osservazione, mentre ogni arco (i, j) il fatto che il processo p_i contenga l’Id del nodo

p_j all’interno della P artialV iew_i. Bisogna notare inoltre che l’esistenza di un arco (i, j) non implica automaticamente che il nodo p_j contenga il nodo p_ji all’interno della

InV iew_j: ad esempio un nodo che inizia la procedura di Subscription manterr`a nella sua PartialView il solo contatto, ma questo fatto non implica che il contatto debba avere il nodo in ingresso nella sua InView.

Vedremo come questo risulti essere rilevante ai fini del funzionamento della rivelazione dall’isolamento.

Senza mettersi ad elencare i contenuti di ogni vista locale, `e sufficiente qui mostrare le viste dei nodi 1 e 5, che rappresentano rispettivamente i processi p₁ e p₅.

P artialV iew₁ = {0, 2}

InV iew₁ = {0}

P artialV iew₅ = {4}

Inview₅ = {0}

A questo punto se i nodi p₁ e p₅ lasciano il sistema, secondo quanto detto in 3.1.1, avvertiranno entrambi il solo processo p₀, comunicandogli di rimuovere i rispettivi Id dalla sua P artialV iew₀. Rimossi i rispettivi nodi e gli archi conseguenti il sistema passa nella configurazione rappresentata dal grafo della Figura 3.4. Facendo riferimento a tale grafo possiamo analizzare il comportamento del meccanismo di heartbeat.

Figura 3.3: Sottografo ottenuto in una simulazione

Ogni nodo presente nella Figura 3.4 `e in grado di ricevere un messaggio di heartbeat da almeno un nodo, pertanto in queste condizioni la procedura di heartbeat non rilever`a alcuno stato di isolamento e non verr`a avviata alcuna risottoscrizione. Il problema di questa struttura risiede per`o nel fatto che, nonostante non sia sconnessa, `e comunque incapace di permettere ad ogni nodo di inviare, e ricevere, messaggi da qualunque altro membro del gruppo.

Se, ad esempio, il mittente del messaggio risultasse essere il processo p₄allora l’unico membro del gruppo in grado di riceverlo sar`a p<sub>6</sub>, cos`ı come p₆ `e in grado di ricevere messaggi ma non pu`o inviarne alcuno poich´e la sua PartialView non contiene pi`u nodi validi. Otteniamo quindi dei nodi che, di fatto, risultano essere isolati dal gruppo ma di cui non abbiamo alcuna possibilit`a di rilevarne lo stato d’isolamento.

In conclusione il meccanismo di heartbeat `e in grado di rilevare solamente stati di completo isolamento, mentre nulla pu`o contro situazioni pi`u complesse come quelle appena viste. In tali scenari risulta di fatto impossibile rilevare, e dunque correggere, stati d’isolamento parziale del sistema, per cui l’unica possibile risposta potrebbe venire dal meccanismo di lease descritto in 3.1.2.

3.1. SCAMP 53

Figura 3.4: Sottografo ottenuto in una simulazione