UNIVERSITA’ DEGLI STUDI DI BARI

FACOLTÀ DI SCIENZE MM.FF.NN. CORSO DI LAUREA IN INFORMATICA MAGISTRALE

PROGETTO DI SISTEMI DISTRIBUITI MULTIAGENTE

Analisi di algoritmi epidemici

Studente: Nunzio Gianfelice Matricola 585229

ANNO ACCADEMICO 2011/2012

Introduzione

Un elemento importante della comunicazione nei sistemi distribuiti è il supporto per l’invio di

dati a molteplici destinatari, conosciuto anche come comunicazione multicast. La

comunicazione multicast può essere realizzata sia creando “communication path” espliciti, sia

affidandosi a tecniche applicative che simulano i comportamenti epidemici.

Un elemento di progettazione fondamentale è la costruzione della rete “overlay”: una rete

virtuale atta a fornire meccanismi non nativamente supportati dalla rete sottostante, tra cui il

multicast applicativo. Esistono due approcci fondamentali per l’implementazione del

multicast applicativo: il primo è che i nodi si possono organizzare direttamente in un albero, il

che significa che c’è un unico percorso tra una coppia di nodi; l’altro vede i nodi organizzati

in una rete a maglia in cui ogni nodo ha molti vicini, creando cosi molti percorsi diversi per

ogni coppia di nodi. La differenza principale tra i due approcci è che di solito il secondo è più

robusto. Infatti se cadesse una connessione (dovuta ad esempio alla disfunzione di un nodo) ci

sarebbe ancora la possibilità di distribuire le informazioni senza la necessità di riorganizzare

immediatamente l’intera rete.

Algoritmi epidemici (perché e quando si usano)

Si parla di algoritmi epidemici a causa della somiglianza con i processi di diffusione di una

malattia infettiva; proprio grazie a queste analogie possono essere sfruttati i risultati ottenuti

nelle ricerche mediche anche se gli scopi ultimi differiscono. Inoltre in questo caso abbiamo

la libertà di essere noi a determinare la politica di contagio. Le tecniche di comunicazione

epidemica garantiscono la propagazione di tutte le operazioni a tutti i nodi anche quando la

topologia della rete è sconosciuta e variabile. Offrono una maggiore scalabilità del sistema in

presenza di un grande numero di punti proprio perché è molto minore il livello di

sincronizzazione richiesto tra le repliche. Consentono ai diversi siti che compongono il

sistema di rimanere autonomi in quanto permettono l'aggiunta e la rimozione di nuovi

componenti senza la necessità di modifiche della configurazione dei nodi esistenti. Da questo

possiamo dedurre che l’obbiettivo principale di questi protocolli epidemici è la rapida

propagazione delle informazioni in un grande insieme di nodi, usando solo informazioni

locali. In altre parole, non esiste un componente centrale che coordina la distribuzione delle

informazioni.

Volendo usare la terminologia delle epidemie, un nodo che fa parte di un sistema distribuito è

detto “infetto” se possiede dati che si desidera diffondere su altri nodi. Un nodo che non ha

ancora visto questi dati si dice suscettibile. Infine, un nodo aggiornato che non vuole o non

può diffondere i propri dati è detto rimosso. Supponiamo di poter distinguere i dati vecchi da

quelli nuovi, perché sono stati contrassegnati con il timestamp o con un numero di versione.

Più precisamente i protocolli di gossip godono delle seguenti proprietà:

• scalabilità: Le loro performance non degradano rapidamente al crescere del numero dei

processi. Generalmente ogni processo invia un numero di messaggi indipendente dal numero

dei processi e predeterminato. In un protocollo siffatto un processo necessita di conoscere

solo gli identificatori degli altri processi presenti ella rete ed alcune costanti. In queste

condizioni, se la stabilità 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, è

definito un numero f di guasti per il quale il protocollo è in grado di funzionare correttamente.

In presenza di f + 1 guasti il protocollo non sarà in grado di funzionare. L’affidabilità del

protocollo sarà uguale alla probabilità che non occorrano contemporaneamente più di f guasti.

D’altra parte i protocolli epidemici hanno un comportamento poco sensibile ai guasti e la

probabilità di funzionare correttamente non decresce in modo netto al superamento di un

valore di soglia f, ma decresce in modo graduale (gracefully appunto).

• adattabilità: Non è 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ò portare, in questi casi, ad una degradazione delle

prestazioni.

Dissemination Parameteres

In un algoritmo epidemico, tutti i processi di sistema sono potenzialmente coinvolti

nella diffusione delle informazioni. In pratica, ogni processo bufferizza ogni messaggio che

riceve fino ad una certa capacità b del buffer e inoltra questo messaggio un numero limitato

di volte t. Il processo inoltra il messaggio ogni volta ad un insieme (di dimensioni limitate f)

di processi selezionato a caso, il fan-out della diffusione.

Molte varianti di algoritmi epidemici esistono e sono tipicamente caratterizzati

da valori diversi da b, t, e f. Questi parametri possono essere fissati indipendentemente dal

numero n di processi nel sistema, in cui il carico imposto su ogni processo rimane

delimitato. L'affidabilità di consegna delle informazioni dipende sia da questi valori sia dalla

dimensione del sistema dato che i parametri di diffusione possono evolversi con il variare di

n. L'affidabilità intrinseca di algoritmi epidemici si trova in un meccanismo proattivo che

aggira potenziali fallimenti di processo e guasti nel collegamento di rete. In questo caso ogni

processo che riceve un messaggio, lo deve diffondere di default ad un sottoinsieme scelto a

caso di altri processi. Ognuno di questi processi infetti girerà l’informazione ad un altro

sottoinsieme casuale. Così, a differenza degli algoritmi reattivi, in cui i processi per reagire a

guasti ritrasmettono le informazioni mancanti, gli algoritmi epidemici non hanno bisogno di

un meccanismo per rilevare e riconfigurare i fallimenti.

Dalla messa a punto in modo appropriato dei parametri di disseminazione b, t, ed f, gli

algoritmi di epidemici sono in grado di fornire le stesse garanzie degli algoritmi

deterministici. L'implementazione di un algoritmo epidemico richiede di affrontare vincoli di

progettazione specifica che le risorse di sistema dei processi richiedono rispetto a:

• membership: come i processi vengono a conoscenza degli altri e quanti bisogna conoscerne;

• conoscenza di rete: come la connessione tra i diversi processi riflette la topologia reale di

rete garantendo prestazioni accettabili;

• gestione del buffer: quale informazione eliminare quando la capienza del buffer è esaurita;

• filtraggio dei messaggi: come prendere in considerazione l'interesse reale dei processi e

diminuire la probabilità che essi ricevano e memorizzino informazioni di nessun interesse per

loro.

Modello di diffusione : Anti – entropia

In questo modello un nodo P sceglie, sempre a caso, un nodo Q e scambia il proprio

contenuto informativo per appianare ogni divergenza. Questo meccanismo è sicuramente

molto affidabile e garantisce che partendo da una situazione iniziale di un solo nodo infetto, si

raggiunge una situazione finale in cui l’intera popolazione è stata infettata. Il tempo che viene

impiegato è proporzionale al logaritmo della dimensione dell’intera popolazione.

Questo modello può propagare gli aggiornamenti con tre diversi approcci: Push, Pull, Push –

Pull .

Push

Nell’approccio Push il nodo P manda soltanto i suoi aggiornamenti al nodo Q. Questo metodo

non risulta essere una buona scelta quando è necessario diffondere rapidamente gli

aggiornamenti. Si deve notare che in questo caso gli aggiornamenti possono essere propagati

solo dai nodi infetti. Tuttavia, se molti nodi sono infetti, la probabilità che ciascuno di loro

scelga un nodo suscettibile è molto bassa e quindi questo resterà suscettibile a lungo,

rallentando la diffusione.

• All'inizio, solo pochi nodi sono infetti e la probabilità di scegliere un nodo non infetto è alta

• Successivamente la probabilità di trovare un nodo non infetto diminuisce

Pull

Nell’approccio Pull il nodo P si prende soltanto i nuovi aggiornamenti dal nodo Q. Questo

metodo lavora meglio quando ci sono molti nodi infetti. In questo caso, la diffusione degli

aggiornamenti è essenzialmente scatenata dai nodi suscettibili che richiedono i nuovi

aggiornamenti. Tuttavia trova un rallentamento iniziale in quanto se sono pochi nodi ad essere

infettati, la probabilità di trovare un nodo infetto da cui prendere gli aggiornamenti è

relativamente bassa.

• all'inizio la probabilità di essere infettati è bassa

• non esiste garanzia che la diffusione dell'informazione inizi al primo ciclo

Push – Pull

L’approccio Push-Pull unisce praticamente le caratteristiche dei due approcci

precedentemente mostrati. I nodi P e Q si mandano reciprocamente gli aggiornamenti. La

modalità Push-Pull, in cui entrambi i nodi comunicano all’altro attore il proprio contenuto

informativo, permette di sfruttare la maggiore rapidità di convergenza del modello Pull. Infatti

nel caso in cui siano pochi i nodi rimasti suscettibili c’è una grossa differenza di

comportamento fra il modello Push e quello Pull, con il Push-Pull che si comporta circa come

quest’ultimo per l’ultima fase.

• unisce i vantaggi degli approcci precedenti

• all'inizio dominano le operazioni di push, perché il numero di unita non infettate è maggiore

di quelle infettate, nell'ultima parte quelle di pull, perché è più probabile individuare nodi

infettati

• la probabilità che un nodo non infetto contatti un nodo infetto cresce ad ogni ciclo, mentre

quella che un nodo infetto contatti uno non infetto diminuisce ad ogni round

Essendo p(i) la probabilità che un nodo rimanga suscettibile dopo l’i-esimo ciclo anti-entropy,

nel meccanismo pull un server rimane suscettibile dopo l’(i+1)-esimo ciclo se lo era dopo l’i-

esimo e nell’ultimo ha contattato un altro suscettibile, da cui la formula:

p(i)+1 = (p(i)) ^ 2

Per il Push un nodo rimane suscettibile se durante l’ultimo ciclo nessun server infetto lo ha

contattato, da cui la formula:

p(i)+1 = p(i)(1 − 1/n) ^ n(1−p(i))

Come si può intuire la prima converge molto rapidamente a 0 quando p(i) è piccolo, al

contrario della seconda che con p(i) molto piccolo ed n largo si può approssimare a:

p(i)+1 = p(i)( e ^ −1 )

che non ha buone prestazioni nel caso atteso. Questo fa determinare il push-pull come la

migliore strategia di anti-entropia che si può utilizzare, ottenendo scalabilità e velocità di

propagazione.

Modello di diffusione : Gossiping o “Diffusione del rumore”

In questo modello il nodo P appena viene aggiornato con un determinato dato prova a

contattare un casuale nodo Q e prova ad inviargli l’aggiornamento. Tuttavia, è possibile che Q

sia già stato aggiornato da un altro nodo e in questo caso P potrà perdere l’interesse a

diffondere ulteriormente l’aggiornamento entrando a far parte dei nodi “rimossi”. Anche qui

l’analogia con la vita reale è del tutto appropriata. Infatti simula il comportamento umano in

caso di “pettegolezzo”, raggiungendo ottime prestazioni soprattutto nella velocità di

diffusione. Tuttavia non garantisce che tutti i nodi vengano raggiunti dall’aggiornamento.

In questo algoritmo i nodi sono all’inizio ignoranti rispetto ad una informazione; quando la

ricevono questa viene considerata HOT e per questo da condividere. Perciò scelgono

periodicamente a caso un altro nodo e verificano che anche l’altro ne sia a conoscenza.

Quando un server ha contattato troppi altri nodi che già conoscevano l’aggiornamento questo

cambia la connotazione HOT dell’aggiornamento e il nodo lo mantiene senza più cercare di

propagarlo.

Questo meccanismo viene utilizzato ogni qual volta un nodo ottiene un nuovo dato o da un

pari o da un utente; può essere lanciato frequentemente in quanto ha necessità di poche

risorse. Una variante del gossiping classico è il gossiping direzionale.

Gossiping direzionale

Questo tipo di variante diventa utile quando si hanno reti con topologie particolari conosciute

a priori. Infatti la regola base sul quale si fonda questo sistema è che i nodi che sono connessi

a pochi altri nodi devono avere una maggiore probabilità di essere scelti come “attori” da nodi

che stanno diffondendo il “pettegolezzo”. Il ragionamento che è alla base di questa regola è

che questi nodi vengono visti come “ponti” verso punti morti della rete e quindi devono

essere contattati il prima possibile per permettere la diffusione dell’aggiornamento anche in

quella zona della rete.

Chi sono i miei vicini?

Come si è scritto nei paragrafi precedenti, in questi algoritmi si fa sempre riferimento alla

scelta di uno o più nodi in maniera casuale dall’intera rete (e quindi ogni nodo conosce tutti i

nodi facenti parte della rete in un determinato momento). Questo in linea di principio. E’

evidente come tale assunzione, seppur di poco conto nel caso di gruppi di piccole dimensioni,

possa risultare una barriera quasi invalicabile quando si tratta di operare con un numero di

nodi molto elevato. Infatti, le strutture dati necessarie per memorizzare le view di un così

elevato numero di nodi possono consumare molte risorse di memoria, senza calcolare i

processi di comunicazione necessari per mantenere la coerenza delle view fra tutti i nodi

coinvolti. In realtà sappiamo che questa supposizione non può essere implementata molto

facilmente perché una sua risoluzione sarebbe l’uso di un server dedicato a registrare la

presenza dei nodi e dedito a restituire un campione scelto in modo casuale. Questo tipo di

soluzione, a parte la complessità, non è realizzabile perché farebbe cadere una delle

caratteristiche fondamentali su cui si fondano gli algoritmi epidemici: la scalabilità. Per

questo motivo ogni nodo non avrà a disposizione la visione completa della rete ma solamente

una vista parziale di quest’ultima.

D’altra parte la dimensione della membership parziale necessaria per ottenere con successo

un’epidemia è legata alla taglia del sistema: quando la taglia del gruppo cresce anche la taglia

della vista parziale deve crescere di conseguenza. Determinare il fan-out è semplice nel caso

si lavori in un modello centralizzato o distribuito su un numero limitato di server, poiché tali

modelli permettono in maniera sufficientemente 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 è per nulla semplice ottenere il medesimo

risultato, poiché risulta estremamente complesso calcolare la dimensione del sistema

complessivo a partire dalle local view dei singoli nodi.

Nei sistemi P2P (il più famoso esempio di reti che implementano algoritmi epidemici) questo

viene gestito attraverso un “servizio” che prende il nome di “Peer Sampling Service”.

Peer Sampling Service (un esempio di algoritmo epid emico)

Peer sampling service è un meccanismo attraverso cui, dati in input l'insieme P dei peer che

eseguono l'algoritmo epidemico, restituisce in output l’insieme dei peer scelti casualmente in

modo uniforme tra quelli di P. Esso deve garantire: scalabilità, accuratezza in presenza di alta

dinamicità (l'insieme dei peer restituiti dovrebbe essere scelto tra quelli attualmente presenti

sulla rete) e indipendenza con la quale peer diversi dovrebbero ottenere 'campioni'

indipendenti. In un ambiente P2P il servizio di sampling fa in modo che ogni peer possegga

una propria vista della rete e che i peer si scambino frequentemente la propria vista

aggiornando continuamente quindi la propria visione della rete. Il sampling service restituisce

un sottoinsieme dei peer presenti nella vista del nodo che invoca la getPeer( ). Questa

soluzione consente di approssimare accuratamente la situazione in cui il 'campione' restituito

dal servizio è scelto dall'insieme di tutti i peer della rete. Ogni nodo possiede una propria vista

contenente C vicini e per ogni vicino conosce indirizzo IP e informazioni utili per

implementare il servizio di campionamento. Ogni nodo contatta periodicamente un vicino

nella propria vista e scambia con esso informazioni relative alla propria vista (gossip). I nodi

coinvolti nel gossip aggiornano la propria vista in base alle informazioni ricevute ottenendo

cosi una vista altamente dinamica.

Un nuovo modello di diffusione: Fast Gossip

Osservando i modelli di diffusione sopra descritti ho notato che sia il modello anti-entropia

sia il modello gossip non prendono in considerazione due fattori: il primo è l’analisi della

view della rete e il secondo è il numero di risorse occupate in quel momento nel nodo infetto.

Per l’ultima caratteristica volendo continuare a fare un’analogia con le epidemie biologiche si

può osservare che la diffusione di un virus attraverso un individuo è variabile a seconda

dell’individuo selezionato. Questa variazione è data da vari fattori “personali” come per

esempio possono essere le difese immunitarie, lo stato fisico nel momento dell’infezione e lo

stato mentale. Allo stesso modo un nodo di una rete nel momento in cui decide di diffondere

il proprio aggiornamento dovrebbe scegliere il numero di peer da infettare, in base alle proprie

“capacità” in quel determinato momento. Si sfrutta di base il principio del load-balancing,

dove il carico di lavoro in un sistema distribuito viene assegnato semplicemente alla macchina

con meno carico. In questo caso, se un nodo avrà in quel momento maggiori risorse

inutilizzate, le potrà impiegare per diffondere l’informazione. Al contrario, un nodo che viene

infettato in un momento di massimo carico di lavoro e impiego di risorse, diffonderà

l’informazione solo in piccola parte oppure rimanderà la diffusione mettendosi in stato

“rimosso”. Basando la diffusione su questi tipi di accorgimenti secondo me si potrà avere

anche un bilanciamento di carico del processo di epidemia, velocizzandolo e adattandolo.

Nello studio dei sopracitati modelli di diffusione, mi sono accorto che esiste una soluzione

che potrebbe mediare tra i due algoritmi cercando di prendere i vantaggi di ognuno di essi.

Partiamo dal modello di Gossip. La sua caratteristica principale è quella che se la diffusione

di un’ informazione avviene troppe volte verso un nodo che già l’ha acquisita a priori, il nodo

“infetto” perde interesse ad infettare quel nodo. In realtà questo “rifiuto di diffusione”

potrebbe essere usato in un’ altra maniera, come vedremo più avanti.

Se invece analizziamo il modello Anti-entropia, possiamo notare che la sua caratteristica

rilevante per la nostra analisi di vicinato è che un nodo oltre a diffondere un’informazione può

ricevere una richiesta di pull da parte di un suo “vicino”.

A questo punto la domanda che mi nasce spontanea è: perché non sfruttare la caratteristica del

Gossip descritta in questo paragrafo per migliorare il modello di Anti-entropia (Push-Pull)?

L’idea è quella di sfruttare il nodo Q che ha già ricevuto l’informazione prima che il nodo P

gliela “spettegolasse”, come fonte da cui trarre informazioni nelle successive fasi e non in

maniera discriminatoria come avviene nel protocollo Gossip. In questo modo si potrebbe

velocizzare anche l’acquisizione da parte del nodo P dell’informazione HOT.

Come possiamo vedere nell’immagine il nodo P riceve le informazioni da A. Poi le diffonde

attraverso un’azione di push al nodo B,C e Q. Ma il nodo Q, sistematicamente, ha già

l’informazione che il nodo P cerca di passarli perché l’acquisisce dal nodo H. A questo punto

il nodo P effettuerà da quel momento in poi un’ azione di richiesta (pull) su Q per cercare di

avere il gossip in anticipo, rispetto alla distribuzione dello stesso da parte di A. In questa

maniera si potrebbe velocizzare la rete di distribuzione che parte quando il nodo P è “infetto”.

Per rendere questo possibile c’è bisogno dell’inserimento di una variabile LIV(livello) che

permette di monitorare in quanti passi l’aggiornamento è arrivato in un determinato nodo.

LIV verrà incrementata di +1 ogni volta che l’informazione passerà da un nodo ad un altro.

Attraverso questa informazione sarà più facile valutare se considerare un proprio “vicino”

come una fonte più rapida di quella attuale da cui trarre informazione oppure no.

Riconsiderando la figura precedente, con l’inserimento della variabile LIV si potrebbe avere

una situazione del genere:

Il nodo P notando che Q rifiuta l’informazione inviatagli perché già ne possiede una copia, si

accorge che il LIVello è parecchio inferiore al suo. Valutando se ne vale la pena attraverso la

comparazione delle variabili LIV, decide di effettuare periodicamente delle sessioni di pull sul

nodo Q cosi da ottenere in anticipo l’informazione.

Schematizzando il modello Fast Gossip riscontriamo le seguenti caratteristiche:

• Ogni nodo contiene due viste dell’intera rete. Una contiene i nodi “vicini” su cui

effettuare l’azione di pull e l’altra i nodi su cui diffondere l’informazione appena si

viene infettati da un nuovo aggiornamento (lista push)

• Nell’informazione diffusa ci sarà anche una variabile LIV che conterà da quanti nodi è

passata l’informazione (profondità di livello)

• Attraverso questo contatore un nodo P potrà far variare la propria “lista pull”; in caso

ci sia un nodo su Q su cui P cerca di inviare l’informazione, il quale la riceve con un

livello inferiore ( <2 ) a quello di P, il nodo Q verrà messo nella lista pull

• Il numero n di peer a cui verrà diffusa l’informazione, varierà in base alle risorse

disponibili in un determinato momento del nodo “infetto”.

Simulazione del modello di Fast Gossip

Per simulare il funzionamento dell’ algoritmo in questione, mi sono servito di un sistema

inferenziale. Il software utilizzato è CLIPS, uno strumento per la crezione di sistemi esperti.

CLIPS è l'acronimo per C Language Integrated Production System. La sintassi ed il nome del

linguaggio sono ispirati dal linguaggio OPS5 (Official Production System) e

l'algoritmo di riconoscimento di pattern alla base usato è “l'algoritmo rete”. Come gli altri

linguaggi per sistemi esperti, CLIPS è basato su regole e fatti. I fatti descrivono il “mondo”

esistente, cioè l’ambiente; le regole descrivono le dinamiche che governano questo mondo.

Alla base c’è un motore inferenziale che attiva regole in base hai fatti che sono presenti o che

si vengono a creare.

Per il nostro caso si è voluto simulare la diffusione d’ informazione attraverso una rete di 21

nodi connessi come mostrato nella figura seguente.

Si è iniziato con il definire le strutture dei fatti attraverso i “template”.

; Definizione dei Template

;======================================

; Template per definire le relazioni di PUSH. Composto da due slot, in cui ‘nodo_infetto’ rappresenta il nodo da cui può partire la ;diffusione in caso si contiene l’informazione e ‘nodo_suscettibile’ il nodo a cui verrà inviata l’informazione.

(deftemplate push

(slot nodo_infetto (type SYMBOL))

(slot nodo_suscettibile (type SYMBOL))

)

; Template per definire le relazioni di PULL. I due slot qui rappresentano il nodo richiedente dell’informazione e il nodo a cui si ;richiederà l’informazione (nodo_probinf)

(deftemplate pull

(slot nodo_richiedente (type SYMBOL))

(slot nodo_probinf (type SYMBOL) )

)

; Template che descrive il nodo con un ID, uno slot ‘inf’ che indica se il nodo contiene o no l’informazione ( S o N) e lo slot ‘liv’ ; che indica il livello in cui si è ricevuta l’informazione (numero di passi dal nodo di partenza)

(deftemplate nodo

(slot id (type SYMBOL))

(slot inf (type SYMBOL) (default N))

(slot liv (type INTEGER) (default 0))

)

In base hai template appena definiti vengono descritti i fatti, che andranno a descrivere lo

stato iniziale del sistema.

; Definizione dei Fatti Iniziali

;======================================

;Peer/server facenti parte della rete. Inizialmente 21 : di cui solo il nodo Z contiene l’informazione ed ha il livello inizializzato ad

;1. Tutti gli altri nodi sono sprovvisti dell’ informazione.

(deffacts peer

(nodo (id Z) (inf S) (liv 1))

(nodo (id A) (inf N) (liv 0)) (nodo (id B) (inf N) (liv 0)) (nodo (id C) (inf N) (liv 0)) (nodo (id D) (inf N) (liv 0))

(nodo (id E) (inf N) (liv 0)) (nodo (id F) (inf N) (liv 0)) (nodo (id G) (inf N) (liv 0)) (nodo (id H) (inf N) (liv 0))

(nodo (id L) (inf N) (liv 0)) (nodo (id K) (inf N) (liv 0)) (nodo (id X) (inf N) (liv 0)) (nodo (id O) (inf N) (liv 0))

(nodo (id M) (inf N) (liv 0)) (nodo (id V) (inf N) (liv 0)) (nodo (id J) (inf N) (liv 0)) (nodo (id N) (inf N) (liv 0))

(nodo (id W) (inf N) (liv 0)) (nodo (id R) (inf N) (liv 0)) (nodo (id T) (inf N) (liv 0)) (nodo (id Y) (inf N) (liv 0))

)

; Liste di distribuzione push dei nodi. Il nodo di partenza Z non viene raggiunto da nessun nodo ed invia l’informazione solo al

;nodo A

(deffacts col_push

(push (nodo_infetto Z) (nodo_suscettibile A)) (push (nodo_infetto A) (nodo_suscettibile K))

(push (nodo_infetto A) (nodo_suscettibile G)) (push (nodo_infetto A) (nodo_suscettibile E))

(push (nodo_infetto B) (nodo_suscettibile C)) (push (nodo_infetto B) (nodo_suscettibile D))

(push (nodo_infetto F) (nodo_suscettibile A)) (push (nodo_infetto F) (nodo_suscettibile E))

(push (nodo_infetto E) (nodo_suscettibile G)) (push (nodo_infetto E) (nodo_suscettibile H))

(push (nodo_infetto G) (nodo_suscettibile B)) (push (nodo_infetto G) (nodo_suscettibile C))

(push (nodo_infetto G) (nodo_suscettibile D)) (push (nodo_infetto H) (nodo_suscettibile G))

(push (nodo_infetto H) (nodo_suscettibile F)) (push (nodo_infetto K) (nodo_suscettibile L))

(push (nodo_infetto K) (nodo_suscettibile B)) (push (nodo_infetto C) (nodo_suscettibile H))

(push (nodo_infetto C) (nodo_suscettibile D)) (push (nodo_infetto D) (nodo_suscettibile E))

(push (nodo_infetto D) (nodo_suscettibile H)) (push (nodo_infetto L) (nodo_suscettibile A))

(push (nodo_infetto H) (nodo_suscettibile X)) (push (nodo_infetto X) (nodo_suscettibile O))

(push (nodo_infetto X) (nodo_suscettibile V)) (push (nodo_infetto O) (nodo_suscettibile M))

(push (nodo_infetto M) (nodo_suscettibile V)) (push (nodo_infetto J) (nodo_suscettibile V))

(push (nodo_infetto J) (nodo_suscettibile N)) (push (nodo_infetto J) (nodo_suscettibile R))

(push (nodo_infetto J) (nodo_suscettibile W)) (push (nodo_infetto N) (nodo_suscettibile X))

(push (nodo_infetto W) (nodo_suscettibile R)) (push (nodo_infetto R) (nodo_suscettibile Y))

(push (nodo_infetto R) (nodo_suscettibile T)) (push (nodo_infetto T) (nodo_suscettibile X))

(push (nodo_infetto T) (nodo_suscettibile D)) (push (nodo_infetto Y) (nodo_suscettibile Y))

(push (nodo_infetto X) (nodo_suscettibile J)) )

N.B. Non vengono definiti fatti di tipo pull solamente perché al primo ciclo viene simulato una diffusione con il modello Anti-

entropia strategia Push. Durante il primo ciclo del programma verranno creati dei ‘fatti pull’.

; Definizione delle Regole

;=========================================

;Regola che attiva/disattiva il ciclo di diffusione dell’informazione nel sistema. Si attiva solamente quando tutti i nodi della rete

;hanno l’informazione e inizializza l'informazione di tutti i nodi a N e i vari livelli a 0, cosi da poter riattivare un’ altro ciclo di

;simulazione della diffusione!

;Ad ogni ciclo stampa a video i vari nodi con i relativi livelli.

(defrule partenza

?n <- (nodo (id Z) (inf S) (liv 1)) ?a <- (nodo (id A) (inf S) (liv ?liva)) ?b <- (nodo (id B) (inf S) (liv ?livb))

?c <- (nodo (id D) (inf S) (liv ?livd)) ?d <- (nodo (id C) (inf S) (liv ?livc)) ?e <- (nodo (id E) (inf S) (liv ?live))

?f <- (nodo (id F) (inf S) (liv ?livf)) ?g <- (nodo (id G) (inf S) (liv ?livg)) ?h <- (nodo (id H) (inf S) (liv ?livh))

?i <- (nodo (id L) (inf S) (liv ?livl)) ?l <- (nodo (id K) (inf S) (liv ?livk)) ?a1 <- (nodo (id X) (inf S) (liv ?livx))

?b1 <- (nodo (id O) (inf S) (liv ?livo)) ?c1 <- (nodo (id M) (inf S) (liv ?livm)) ?d1 <- (nodo (id V) (inf S) (liv ?livv))

?e1 <- (nodo (id J) (inf S) (liv ?livj)) ?f1 <- (nodo (id N) (inf S) (liv ?livn)) ?g1 <- (nodo (id W) (inf S) (liv ?livw))

?h1 <- (nodo (id R) (inf S) (liv ?livr)) ?i1 <- (nodo (id T) (inf S) (liv ?livt)) ?l1 <- (nodo (id Y) (inf S) (liv ?livy))

=>

(printout t "Lista nodi dopo il ciclo con i relativi livelli" crlf)

(printout t "A=" ?liva " B=" ?livb " C=" ?livc " D=" ?livd " E=" ?live " F=" ?livf " G=" ?livg " H=" ?livh " L=" ?livl " K=" ?livk " X="

?livx " O=" ?livo " M=" ?livm " V=" ?livv " J=" ?livj " N=" ?livn " W=" ?livw " R=" ?livr " T=" ?livt " Y=" ?livy crlf)

(modify ?n (inf N))

(modify ?a (inf N) (liv 0)) (modify ?b (inf N) (liv 0)) (modify ?c (inf N) (liv 0)) (modify ?d (inf N) (liv 0))

(modify ?e (inf N) (liv 0)) (modify ?f (inf N) (liv 0)) (modify ?g (inf N) (liv 0)) (modify ?h (inf N) (liv 0))

(modify ?i (inf N) (liv 0)) (modify ?l (inf N) (liv 0)) (modify ?a1 (inf N)(liv 0)) (modify ?b1 (inf N)(liv 0))

(modify ?c1 (inf N)(liv 0)) (modify ?d1 (inf N)(liv 0)) (modify ?e1 (inf N)(liv 0)) (modify ?f1 (inf N)(liv 0))

(modify ?g1 (inf N)(liv 0)) (modify ?h1 (inf N)(liv 0)) (modify ?i1 (inf N)(liv 0)) (modify ?l1 (inf N)(liv 0))

)

;Regola che definisce l’azione di Push.

;Se un nodo contiene l'informazione la prova a passare a tutti i nodi in che ha nella sua lista push. In caso il nodo ricevente del

;push non ha gia acquisito l’informazione, gliela passa e gli passa il livello incrementato di 1. In caso la contiene già, si

;confrontano i livelli. Se il livello del nodo ricevente è minore di 2 unità del nodo “infetto”, allora si aggiunge il nodo ricevente

;alla lista push del nodo mittente.

;La “salience” indica il grado di priorità di attivazione delle regole in caso ce ne sia più di una attivabile. In questo sistema si

;darà priorità alle regole di PULL (che hanno meno possibilità di attivarsi), cosi da poter creare un misto di richieste tra push e

;pull in maniera disordinata (come avviene nella realtà).

(defrule regola_push

(declare (salience 10))

(nodo (id ?nome) (inf S) (liv ?livinf))

(push (nodo_infetto ?nome) (nodo_suscettibile ?altro))

?n <- (nodo (id ?altro) (inf ?inf) (liv ?livsus))

=>

(if (eq ?inf N)

then (modify ?n (inf S) (liv (+ ?livinf 1)))

else (if (> ?livinf (+ ?livsus 1))

then (assert (pull (nodo_richiedente ?nome) (nodo_probinf ?altro))) ) ) )

;Regola che definisce l’azione di Pull.

;Se un nodo non contiene l'informazione la potrà chiedere ad un altro nodo con cui ha “rapporti” di PULL che ha già ricevuto

;l’informazione. Una volta acquisita l’informazione potrà avviare la sua fase Push diffondendola.

(defrule regola_pull

(declare (salience 100))

?n <- (nodo (id ?nome) (inf N) (liv ?))

(nodo (id ?altro) (inf S) (liv ?liv))

(pull (nodo_richiedente ?nome) (nodo_probinf ?altro))

=>

(modify ?n (inf S) (liv (+ ?liv 1))) )

Guida alla simulazione attraverso l’ambiente CLIPS

Aprendo l’ambiente andremo in primo luogo a caricare il file fast_gossip.clp. Questo file

contiene le strutture (template) ed i fatti iniziali del sistema, come gli abbiamo definiti nel

paragrafo precedente. Il comando per caricare il file e la schermata che si ottiene sono

rappresentati nella figura seguente.

Per inizializzare la base dei fatti bisogna eseguire il comando ‘(reset)’. Una volta inizializzata

la base possiamo mandare in esecuzione il sistema con il tasto (run). Alla fine del primo ciclo

si vedranno stampati a video i vari nodi con i relativi livelli. Questo primo ciclo simula una

diffusione Anti-entropia con metodologia push. Per riattivare il ciclo bisognerà inserire una

nuova informazione nel nodo ‘focolaio’: (assert (nodo (id Z) (inf S) (liv 1))). Con queste due

azioni (run e assert) potremo riattivare il ciclo e valutare le varie modifiche che avvengono.

Uno screenshot commentato di 5 cicli per il grafo disegnato su è il seguente. Rammentiamo

che in questa simulazione valutiamo una rete da 21 nodi, dove l’inserimento d’ informazione

avviene sempre nello stesso punto (nodo Z).

La schermata in alto

rappresenta, la Dialog

Window di CLIPS.

L’immagine qui a sinistra

invece rappresenta la

base dei fatti che

descrivono la rete dei

nodi. In quest’ ultima

possiamo notare che oltre

le descrizioni caricati da

noi inizialmente, vengono

creati dei fatti di tipo

pull. Guardando

l’immagine in alto invece

ci possiamo rendere

conto come il modello

Fast-Gossip fa in modo

che il nodo D(al secondo

ciclo) e il nodo T(al terzo

ciclo) velocizzino il recupero d’informazione, grazie alle relazioni di pull create nei cicli

precedenti.

Bibliografia A. Tanenbaum e M. van Steen, Sistemi Distribuiti ed. Pearson-Prentice Hall,

seconda edizione 2007.

P.Eugster. Epidemic Information Dissemination in Distributed Systems.

IEEE Comuputer Society, Maggio 2004.

S.Scipioni.Tesi di laurea in Ingegneria Informatica 2005.Valutazione delle prestazioni di algoritmi

peer-to-peer per la manutenzione della connettivit`a in sistemi dinamici. Università degli Studi di

Roma “La sapienza”

Sorgenti e aggiornamenti dell’ ambiente CLIPS. Gestito da Gary Riley.

http://clipsrules.sourceforge.net/