In questa tipologia di protocolli ogni membro, per inviare in broadcast un messaggio, recapita il messaggio ad un sottoinsieme, scelto casualmente, dei membri del gruppo. Ogni processo che lo riceve ne rinvier`a una copia ad un altro sottoinsieme, anch’esso scelto casualmente, e cos´ı via.
La scalabilit`a `e determinata dal fatto che ogni processo invia soltanto un nume-ro limitato di messaggi, indipendentemente dalla dimensione complessiva del sistema. Inoltre il processo non deve attendere messaggi di acknowledgment ed eseguire delle procedure di recovery nel caso di mancata ricezione di tali messaggi. L’uso di messaggi ridondanti fornisce un meccanismo per assicurare una buona affidabilit`a anche nel caso di alto tasso di perdita di pacchetti nella rete e di guasti nei nodi: uno stesso nodo pu`o infatti ricevere copie del medesimo messaggio da parte di pi`u processi. Nessun processo ha un ruolo particolare da svolgere, in questo modo un processo guasto non inficia la possibilit`a di inviare messaggi da parte dei processi corretti.
Pi`u precisamente i protocolli di gossip godono delle seguenti propriet`a:
• scalabilit`a Le loro performance non degradano rapidamente al crescere del
nu-mero dei processi. Generalmente ogni processo invia un nunu-mero di messaggi indipendente dal numero dei processi e predeterminato. In un protocollo siffato un processo necessita di conoscere solo gli identificatori degli altri processi pre-senti nella rete ed alcune costanti. In queste condizioni, se la stabilit`a della rete fisica non degrada con il numero dei processi, il protocollo di gossip `e scalabile.
• graceful degradation Per molti protocolli di broadcast, deterministici ed affidabili,
`e definito un numero f di guasti per il quale il protocollo `e in grado di funzionare correttamente. In presenza di f + 1 guasti il protocollo non sar`a in grado di funzionare. L’affidabilit`a del protocollo sar`a uguale alla probabilit`a che non oc-corrano contemporaneamente pi`u di f guasti. D’altra parte i protocolli di gossip hanno un comportamento meno sensibile ai guasti e la probabilit`a di funzionare correttamente non decresce in modo netto al superamento di un valore di soglia
f , ma decresce in modo graduale gracefully appunto..
• adattabilit`a Non `e difficile aggiungere o rimuovere processi nella rete. Il problema
risiede nella configurazione dei parametri utilizzati dai protocolli che spesso sono configurati in modo statico in base alle dimensioni previste della rete. Un aumento imprevisto, e consistente, del numero di processi di un gruppo pu`o portare, in questi casi, ad una degradazione delle prestazioni.
Dato che i destinatari dei messaggi inviati da ogni processo sono scelti in modo casuale, esiste la probabilit`a che un messaggio non venga consegnato a tutti i processi appartenenti ad un gruppo anche in assenza di guasti. In una clique questa probabilit`a `e bassa [27], ma questo non `e vero nel caso in cui la connettivit`a della rete non sia uniforme.
Risulta essere, inoltre, molto difficile ottenere un’espressione analitica che descriva il comportamento di un protocollo di gossip; spesso il miglior risultato possibile `e ottenere un’equazione in grado di descrivere il comportamento asintotico per semplici topologie di rete. Nel caso di reti pi`u complesse le analisi non possono trascendere dai dati ottenuti in via sperimentale tramite delle simulazioni.
2.1.1 I gossip-based e la Membership
Si `e detto che i protocolli di tipo gossip, o epidemici, risultino essere scalabili in termini di messaggi inviati dai singoli processi e di bilanciamento del carico. Diverso il discorso
2.1. CARATTERISTICHE GENERALI DEI PROTOCOLLI GOSSIP-BASED 29
per quanto riguarda la scalabilit`a in termini di management della membership dove, spesso, si parte dall’assunzione che ogni processo sia in grado di conoscere ogni altro. ´
E evidente come tale assunzione, seppur di poco conto nel caso di gruppi di piccole dimensioni, possa risultare una barriera quasi invalicabile quando si trattai di operare con un numero di processi molto elevato. Infatti, le strutture dati necessarie per memo-rizzare le view di un cos´ı elevato numero di processi possono consumare molte risorse
di memoria, anche trascurando le comunicazioni necessarie per mantenere la coerenza
delle view fra tutti i processi coinvolti.
Il problema della membership si pone quindi, con particolare urgenza e rilevanza, non appena si mostra che la scelta casuale ed uniforme, fra i presenti, dei processi a cui inviare un messaggio, non `e un criterio capace di garantire una vera scalabilit`a agli algoritmi gossip-based. Alcune volte si `e delegata la responsabilit`a della membership a server dedicati ma in questo modo si `e solo rimandato il problema, poich`e anche questi hanno risorse limitate, ed inoltre si `e aggirata la vera natura dell’architettura peer-to-peer. Queste considerazioni hanno spinto a lavori [22, 13] in cui si `e cercato di fornire ad ogni nodo una vista parziale del sistema senza che il nodo stesso abbia una conoscen-za globale della membership. D’altra parte la dimensione della membership parziale necessaria per ottenere con successo un gossip `e legata alla taglia del sistema: quando la taglia del gruppo cresce anche la taglia della vista parziale deve crescere di conse-guenza. Determinare il fan-out `e semplice nel caso si lavori in un modello centralizzato o distribuito su un numero limitato di server, poich`e tali modelli permettono in manie-ra sufficientemente manie-rapida la determinazione del numero dei partecipanti alla sessione. In un modello totalmente decentralizzato, dove ogni nodo possiede solo una piccola porzione della vista globale non `e per nulla semplice ottenere il medesimo risultato, poich`e risulta estremamente complesso calcolare la dimensione del sistema complessivo a partire dalle local view dei singoli nodi. Ulteriore attenzione merita il problema della suddivisione della view complessiva del sistema nelle local view dei singoli nodi, che per prevenire problematiche di isolamento e partizionamento della membership dovr`a con-tenere una certa ridondanza, delle informazioni che vengano condivise da pi`u membri della membership stessa.
In molti studi `e stato affrontato questo problema e altrettanti protocolli sono stati presentati per risolverlo. Nel resto del capitolo focalizzeremo la nostra attenzione su alcuni di essi che risultano essere di maggior interesse. Esporremo due dei protocolli pi`u importanti per quanto riguarda questo paradigma di Group Membership Protocols
in ambiente completamente decentralizzato: il Lightweight Probabilistic Broadcast nella Sezione 2.2 e lo Scalable Membership Protocol nella Sezione 2.4. Verranno poi accennati altri due protocolli: CYCLON [32] e scalable gossip-based alghoritm [3], in parte ispirati ai lavori suddetti. SCAMP, che sar`a poi oggetto delle simulazioni affrontate nel Capitolo 4, verr`a affrontato in modo pi`u approfondito e critico nel Capitolo 3.