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:
2.2. LIGHTWEIGHT PROBABILISTIC BROADCAST 31
tutti gli eventi ricevuti per la prima volta dall’ultimo messaggio inviato. Ogni processo conserva le notifiche degli eventi ricevuti in un buffer di di memoria chiamato events. Ogni evento viene inviato in gossip almeno una volta ed inoltre le informazioni relative ad eventi pi`u vecchi vengono conservate in un buffer separato poich´e verranno rinviate solo in caso di richieste di ritrasmissione.
• Event notification identifiers. Ogni messaggio trasporta inoltre un digests, una
storia, di tutte le notifiche di eventi che il processo sorgente ha ricevuto. Alla fine ogni processo immagazzina e conserva gli identificatori di tutte le notifiche cha ha gi`a consegnato in un buffer chiamato eventIds. Gli autori suppongono che quest’identificatore sia unico e che contenga, inoltre, l’Id del processo originario. In questo modo `e possibile ottimizzare il buffer facendogli contenere, per ogni nodo, solo gli identificatori delle notifiche consegnate successivamente all’ultimo identificatore trasmesso in sequenza.
• Subscription. Ogni messaggio contiene un insieme di informazioni legate ai nodi
che hanno effettuato sottoscrizioni, vedere 2.2.2 per maggiori dettagli. Queste informazioni, memorizzate in un buffer chiamato subs, vengono utilizzate per aggiornare le propria vista, conservata in un altro buffer view.
• Unsubscription. I messaggi di gossip trasportano inoltre un insieme di
informazio-ni sui processi che hanno abbandonato il sistema, tali informazioinformazio-ni (rimandiamo anche qui a 2.2.3) vengono utilizzate per la rimozione graduale di tali nodi dalle viste. Le informazioni di Unsubscription che possono essere inviate con il prossimo messaggio di gossip sono contenute in un buffer chiamato unSubs.
Abbiamo ottenuto quindi le seguenti strutture dati utilizzate dall’algoritmo per propagare eventi, ingressi ed uscite dal sistema:
• events • eventIds
• unSubs
• subs
Dove events,eventIds,unSubs e subs vengono inserite nel messaggio di gossip inviato dal processo, e quindi conosciute anche dai suoi destinatari mentre view rimane una variabile locale al processo stesso.
Nessuna di queste strutture contiene duplicati e il tentativo di aggiungere elementi gi`a presenti le lascia inalterate. Ogni lista ha inoltre una lunghezza massima fissata, indicata con |L|m per una data lista L (∀L, |L| ≤ |L|m). La lunghezza massima della lista view `e, come gi`a detto, indicata con l.
2.2.2 Procedure
L’algoritmo `e composto essenzialmente di tre procedure: la prima `e eseguita alla rice-zione di un messaggio di gossip; la seconda `e ripetuta periodicamente nel tentativo di propagare informazioni agli altri processi coinvolti nel sistema; la terza `e utilizzata per la richiesta di event notifications che sono andate perdute o non sono state ricevute da lungo tempo. Il nostro interesse, in questa tesi `e rivolto soprattutto alle parti del protocollo che trattano di management della membership, per tali parti riporteremo per intero lo pseudo-codice e si forniranno informazioni dettagliate rimandando a [25] per una trattazione pi`u esauriente.
Ricezione del messaggio di Gossip Enunciate tutte le liste contenute in un messaggio di gossip, vi sono alcune fasi che devono essere affrontate per trattare i dati che vi sono contenuti.
1. La prima fase consiste nel trattare i dati relativi alle Unsubscription Ogni nodo presente in tale lista viene tolto dalla vista individuale e aggiunto ad unSubs. Il buffer generato viene infine ridimensionato, per rispettare il limite |unSubs|m ad esso associato, tramite la rimozione di alcuni elementi casualmente scelti, si faccia riferimento allo psudo-codice presentato in 2.1(a).
2. La seconda fase consiste nel tentare di aggiungere alla vista locale le sottoscrizioni non ancora contenute in essa. Queste sottoscrizioni sono, inoltre, eligibili per poter essere inviate con il prossimo messaggio di gossip. Vengono aggiornati, in questa fase, i due buffer subs e view con il contenuto della lista gossip.subs contenuta nel messaggio appena ricevuto. Bisogna inoltre dire che un processo attivo che invia in gossip, diffonde informazioni nel gruppo anche riguardo s´e stesso, semplicemente aggiungendo il suo Id alla lista subs che invier`a con il
2.2. LIGHTWEIGHT PROBABILISTIC BROADCAST 33
Ricezione del Gossip: Fase 1
1 {Fase 1: aggiornamento di view ed unsubs 2 con le unsubscription}
3 for each unsubs ∈ gossip.unSubs
4 view ← view \ {unSubs}
5 subs ← subs \ {unSubs}
6 unSubs ← unSubs ∪ {unSubs}
7 while |unSubs| > |unSubs|m do
8 rimuovi un elemento casuale da unSubs
(a)
Ricezione del Gossip: Fase 2
1 {Fase 2: aggiornamento di view con 2 le nuove subscription}
3 for each (newSubs ∈ gossip.subs)∧
4 ∧(newSubs 6= pi)
5 if (newSubs /∈ view)
6 then view ← view ∪ {newSubs}
7 subs ← subs ∪ {newSubs}
8 while |view| > l do
9 target ← elemento casuale in view
10 view ← view \ {target}
11 subs ← subs ∪ {target}
12 while |subs| > |subs|m do
13 rimuovi un elemento casuale da subs
(b)
Figura 2.1: Ricezione dei messaggi
messaggio. Infine subs e view sono troncati per rispettare il loro limite prefissato. Si faccia riferimento allo pseudo-codice in 2.1(b).
3. La terza fase consiste nel consegnare all’applicazione gli event notifications che sono stati ricevuti per la prima volta con l’ultimo messaggio di gossip. Sono im-pedite consegne multiple dello stesso evento dalla memorizzazione in eventIds di tutti gli identificatori delle notifiche finora consegnate. Una notifica consegna-ta all’applicazione `e comunque elegibile per poter essere contenuconsegna-ta nel prossimo messaggio di gossip. Se esiste un Id di un evento che non `e stato ricevuto dopo lungo tempo, allora un elemento contenente quell’Id, il round corrente e il sender del gossip viene inserito in un ulteriore buffer chiamato retrieveBuf con lo scopo di ottenere pi`u tardi l’evento andato perduto.
Invio del messaggio di Gossip Ogni processo periodicamente, ogni T ms, ge-nera un messaggio di gossip, come descritto in 2.2.1, che invia a F altri processi scelti casualmente all’interno della sua vista locale view. Se il processo non ha ricevuto nes-suna nuova notifica dall’ultimo messaggio inviato, generer`a comunque il nuovo gossip
che verr`a utilizzato soltanto per scambiarsi digest e mantenere le viste uniformemente distribuite.
Recupero di event notification Il retrieveBuf `e processato per recuperare in-formazioni andate perdute. Come gi`a detto alla ricezione di un messaggio di gossip, contenente un Id di un evento non consegnato, un elemento composto dall’Id dell’e-vento, insieme con il numero del round e con l’identificatore del nodo che ha generato l’evento stesso vengono inseriti in retrieveBuf. A questo punto per ogni elemento in
retrieveBuf viene eseguito un test per determinare se il processo pi ha atteso abbastan-za (k rounds) prima di inziare la procedura per recuperare l’evento non consegnato. Viene eseguito un ulteriore test tramite eventIds per determinare se l’evento non sia stato consegnato con un messaggio di gossip successivo e ricevuto durante l’attesa. Se entrambi i test falliscono allora il processo pi inizier`a il recupero attraverso la richiesta al processo tramite il quale pi ha avuto notizia dell’evento stesso. Se non si ottiene l’event notification in tal modo allora si sceglier`a un processo in view e si invier`a la richiesta a quest’ultimo. In caso di ulteriore fallimento si invier`a la richiesta dell’evento direttamente alla sorgente che lo ha generato. La fase di recupero si basa evidentemen-te sull’assunzione che alla ricezione di un messaggio di dati conevidentemen-tenuti in esso vengano mantenuti, dal processo che lo ha ricevuto, per un tempo limitato ma sufficientemente lungo da poter attivare con successo tutta la procedura.
2.2.3 Dinamismo di Π
Ultima parte da affrontare riguarda uno degli aspetti pi`u rilevanti di un sistema p2p: la dinamica, l’insieme cio`e delle procedure necessarie per entrare od uscire da un gruppo di processi.
Un processo pi che voglia entrare sottoscriversi al gruppo Π deve conoscere un processo pj che gi`a fa parte del gruppo. Il processo pi semplicemente invier`a la sot-toscrizione al processo pj che la rinvier`a attraverso il gruppo. Se la sottoscrizione `e stata correttamente ricevuta e rinviata da pj allora pi verr`a gradualmente inserito nel sistema e pi ne avr`a esperienza tramite la ricezione di messaggi di gossip. Nel caso di mancata ricezione di messaggi di gossip viene fatto scadere un timer che porter`a alla riemissione di una richiesta di sottoscrizione.
Allo stesso modo un processo che vuole uscire dal gruppo non deve far altro che inviare la sua richiesta di Unsubscription e verr`a gradualmente rimosso dal sistema.
2.2. LIGHTWEIGHT PROBABILISTIC BROADCAST 35
L’unico problema da risolvere risiede nel fatto che unSubs non viene pulito delle sot-toscrizioni pi`u vecchie e quindi un messaggio potrebbe rimanere all’infinito all’interno di qualche nodo; il problema viene risolto inserendo nelle unsubscription un timestamp che le fa scadere dopo un certo periodo di tempo. Scaduto il timestamp, la sottoscrizio-ne viesottoscrizio-ne rimossa. Il discorso legato al timestamp non viesottoscrizio-ne applicato alla subscription che continuano ad essere inviate per garantire viste locali uniformemente distribuite.
Inoltre, secondo gli autori, poich´e un processo corretto invia fra i nodi della lista
subs del messaggio di gossip anche il suo identificatore, operazione che non viene
evi-dentemente eseguita da un processo guasto, esiste un’alta probabilit`a che il processo guasto in questione venga rimosso da tutte le viste del sistema dopo un periodo di tempo sufficientemente lungo.
Una rimozione degli eventi eseguita in questo modo espone l’algoritmo ad un pro-blema legato alla possibile non completa rimozione di un processo da tutte le viste dei membri del gruppo. In tal caso si potrebbe avere una nuova diffusione dell’informazione legata al nodo in questione, una volta che il timestamp associato alle Unsubscription abbia fatto scadere tali messaggi.
2.2.4 Ottimizzazioni
In lpbcast ogni processo mantiene localmente informazioni sui messaggi pubblicati e sulla membership ma, naturalmente, per preservare la membership `e necessario mante-nere le dimensioni di questi buffer limitate e rimuovere periodicamente elementi. Fino ad ora si `e considerato il caso semplice in cui le informazioni vengano rimosse tramite una scelta completamente casuale ma `e evidente che un comportamento migliore si ot-terrebbe mantenendo le informazioni meno diffuse ed eliminando quelle che sono state gi`a disseminate in maniera consistente.
In lpbcast vi sono due tipi di buffer: il buffer events che mantiene i messaggi (event
notification) e il buffer subs che conserva informazioni di membership. Nelle due sezioni
successive descriveremo per sommi capi, rimandando a [25] per maggiori informazioni, due tecniche di ottimizzazione applicabili ad ognuno di questi buffer.
Rimozione dei messaggi con modalit`a Age-Based
Questa tecnica viene applicata per fare un buon uso del buffer event mantenuto da ogni processo e per migliorare la reperibilit`a dei messaggi in esso contenuti.
L’idea fondamentale `e quella di associare ad ogni messaggio in event un intero che rappresenta il numero di round che il messaggio ha trascorso nel sistema, rappresenta cio`e la sua et`a. L’et`a, aggiornata ad ogni round, riflette il livello di disseminazione del messaggio all’interno del sistema. Ogni decisione sui messaggi da eliminare viene presa all’interno del singolo processo e non coinvolge alcun processo locale.
Abbiamo il seguente comportamento:
• Nuovo messaggio quando un messaggio `e inviato in broadcast viene aggiunto alla
lista degli eventi con age pari a zero. L’event notification pi`u vecchia contenuta nella lista viene rimossa nel caso in cui il buffer abbia superato la sua size.
• Invio del gossip quando viene inviato un nuovo gossip, l’et`a del mesaggio viene
incremementata di 1.
• Ricezione del gossip Alla ricezione di un messaggio di gossip gli eventi che non
erano ancora stati ricevuti vengono consegnati all’applicazione e memorizzati nel relativo buffer: quelli che non erano ancora stati consegnati verrano aggiornati, modificando l’et`a corrispondente con il valore pi`u alto fra quello contenuto nel buffer e il corrispettivo ricevuto con il messaggio. Membri pi`u vecchi del buffer verrano rimossi se questo supera il limite previsto.
La scelta di quali elementi vadano rimossi viene fatta in base a due criteri sequen-ziali: prima si analizza se il messaggio in questione ´e stato ricevuto molto tempo prima rispetto ai messaggi successivamente consegnati dalla stessa sorgente, poi se il messaggio ha il valore pi`u alto del paramentro age fra gli eventi contenuti nel buffer.
I risultati ottenuti con questa tecnica, permettono agli autori di mostrare dei miglioramenti sia nell’ambito del delivery ratio che del livello di ridondanza1.
Rimozione dei membri con modalit`a Frequency-Based
La gestione della membership con modalit`a frequency-based `e un’ottimizzazione che si applica ai buffer subs contenuti in ogni nodo. Il principio permane quello di eliminare dal buffer l’Id dei nodi che sono maggiormente conosciuti nel sistema, conservando quelli meno diffusi e cercando di prevenire in tal modo l’isolamento a cui posso pervenire
1intesa come il numero delle volte che un medesimo messaggio viene inviato in gossip e non come il numero di messaggi inviati in un round