sione la ricerca di informazioni nel sistema o in qualunque altra situazione in cui mantenere informazioni sullo stato globale del sistema permette di avere migliori prestazioni
Nei paragrafi successivi, il protocollo LEADER viene presentato privo di tale struttura. In tale scenario l’aggiornamento delle informazioni dipende esclusiva- mente dalla natura gossip del sistema costituito dai tre protocolli: Cyclon, Vicinity e Leader.
3.2
L’ambiente di partenza
L’ambiente su cui si basa il protocollo `e formato da una rete semantica epidemica: una rete peer-to-peer in cui ogni peer sfrutta una procedura che gli permette di trovare i suoi vicini migliori, cio`e quei peer a lui pi`u simili sparsi nel sistema. Per avere tali caratteristiche vengono utilizzati in maniera combinata i protocolli Cyclon e Vicinity [30]. Questo permette di lavorare su una base solida gi`a sperimentata e studiata. Naturalmente ci`o non vieta di sostituire i due protocolli con protocolli equivalenti purch´e garantiscano la connettivit`a tra tutti i nodi nella rete, la ricerca dei vicini pi`u simili e un costante aggiornamento delle informazioni presenti nella rete. Viene infatti sfruttata la natura Gossip dei suddetti protocolli che permettono di avere per ogni nodo informazioni sempre aggiornate dello stato dei propri vici- ni. Il protocollo Cyclon implementa l’aspetto epidemico della rete permettendo lo scambio di informazioni tra i peer della rete. Cyclon mantiene le informazioni di un insieme casuale di peer. Durante la sua esecuzione il protocollo ne sceglie uno in modo random al quale invia un sottoinsieme scelto in modo casuale delle proprie in- formazioni. Il peer ricevente scambia le proprie informazioni con quelle presenti nel messaggio ed invia come riposta le informazioni che ha sostituito. Le informazioni in possesso di Cyclon sono passate al protocollo del livello superiore, Vicinity, vedi fig. 3.2.
Tale protocollo implementa l’aspetto semantico della rete. Sia Sim(pi, pj) la fun-
zione di similarit`a utilizzata per misurare quanto il peer pi sia vicino semanticamente
al peer pji, Vicinity, in esecuzione sul peer pi cerca di massimizzare n
X
j=1
Figura 3.2: il doppio livello creato dai protocolli Cyclon e Vicinity che implementano l’ambiente di partenza su cui si basa LEADER (da [30])
dove n `e la dimensione della lista dei peer vicini. A tale fine, Vicinity utilizza le informazioni ricavate da Cyclon peer individuare quei peer pi`u simili al proprio peer presenti nel sistema.
In tale modo viene creata una doppia overlay network, Quella sottostante in con- tinua evoluzione in ricerca sempre di nuovi dati sparsi nella rete, e quella superiore ha lo scopo di convergere ad una situazione ottimale dove un link fra due peer indica una somiglianza tra di essi.
Sopra a questo doppio strato lavora il protocollo LEADER con il fine di raggrup- pare intorno a dei peer, i Leader, dei nodi simili tra di loro. Ogni insieme creato forma una comunit`a identificata dal profilo del proprio leader. La strutta risultante, fig. 3.3, `e un sistema a 3 livelli che cooperano ad aggiornare le informazioni presenti in ogni peer. Da evidenziare come ogni protocollo, in maniera indipendente dagli altri, implementa e mantiene la propria overlay network.
Il profilo di un utente, che caratterizza un peer, `e formato da k termini, con k variabile per ogni utente [26].
La similarit`a tra due peer `e data dal rapporto tra il numero dei termini in comune e il totale dei termini unici dei due peer. Il calcolo di tale indice pu`o essere ponderato rispetto al peso associato ad ogni termine.
La pi`u intuitiva funzione di similarit`a utilizzabile `e coefficiente di Jaccard [50] che calcola il rapporto tra i termini i comune e quelli unici totali. Consideriamo due peer, pi e pj. Sia Cij l’insieme dei termini in comune tra i due peer, e T Uij l’insieme
dei termini unici contenuti nei profili di pi e pj, la similarit`a `e data da
Sim(pi, pj) = |Cij|
3.2. L’AMBIENTE DI PARTENZA 41
Figura 3.3: il tre livelli livelli formati dalle overlay network implementate dai protocolli Cyclon, Vicinity e LEADER
Il codominio della funzione di similarit`a `e dato dall’insieme di numeri reali compresi tra 0 e 1, dove 0 indica la totale dissimilarit`a dei due peer, e 1 la loro equivalenza.
Prendendo in esempio la lista di termini dei due profili presenti in figura 3.4 si ottiene
Sim(pi, pj) = 29 = 0, 222
Per dare maggiore accuratezza al calcolo della similarit`a i termini vengono pesati. In tal caso, come mostrato in figura 3.5, ad ogni termine del profilo viene associato un valore, il suo peso. Tale valore pu`o per esempio essere calcolato in base al numero di volte che un termine compare fra i tag che descrivono i dati in possesso del peer. Sia indicato con wli il peso associato all’ l-esimo termine della lista Li del profilo
Figura 3.4: le liste di termini che formano i profili dei peer Pi e Pj Sim(pi, pj) = P th∈C(w i h+ w j h) P th∈Liw i h+ P th∈Ljw j h
Figura 3.5: i termini dei profili di Pi e Pj con associato il loro peso
Considerando l’esempio in figura 3.5(a) si ottiene
Sim(pi, pj) = 4+3+3+213+15 = 12/28= 0, 0, 428
Raddoppiando i pesi dei termini del peer i, 3.5(a) e ricalcolando la funzione di similarit`a si ottiene
3.2. L’AMBIENTE DI PARTENZA 43 si pu`o notare come pur rimanendo invariata la rispettiva percentuale di termini in comune, la similarit`a cambia.
Si pu`o intuire come avere un numero elevato di termini, oppure avere dei pesi con dei valori elevati rispetto agli altri peer, possa portare ad ottenere dei valori di similarit`a maggiori. Nel caso in cui si voglia ovviare a tale aspetto, si normalizzano i valori dei pesi associati ai termini. Siano wik i pesi associati ai k termini di pi,
occorre che
X
h=1..k
w1h = 1
Consideriamo i due peer, pi e pj. e sia Cij l’insieme dei termini in comune tra i
due peer, la funzione di similarit`a diventa
Sim(pi, pj) = P ti∈Cijwi+ P tj∈Cijwj 2
Figura 3.6: i termini dei profili di Pi e Pj con i valori del peso normalizzati
L’esempio in figura 3.6 mostra i termini dell’esempio precedente con i pesi nor- malizzati. In questo caso si ottiene
Sim(pi, pj) = 0,308+0,231+0,200+0,1332 = 0, 436
Seppur la terza soluzione possa sembrare migliore, nei test presenti nei capitoli successivi `e stata utilizzata la seconda. La scelta effettuata `e stata guidata dal modo in cui `e stato calcolato il peso associato ai termini nel database utilizzato nei test. Come spiegato dopo, il peso del termine `e stato determinato in base al numero di occorrenze nelle keywords che descrivono i documenti. In tale ambito, infatti, avere
dei termini con dei pesi elevati significa possedere una conoscenza pi`u approfondita dell’argomento relativo a tale termine.
Si pu`o desumere come la scelta della funzione di similarit`a sia strettamente legata alla tipologia dello spazio in cui essa opera e quindi a come il profilo sia stato implemento.
La scelta di avere come profilo una lista di termini, vista la sua essenzialit`a, si presta ad essere implementata in molteplici modalit`a dal peer. Per esempio possi- amo utilizzare i tag presenti nei file multimediali; oppure sfruttare un rivelatore di parole chiave per analizzare il testo dei propri documenti o, in alternativa, utilizzare una lista di parole creata direttamente dall’utente. A prescindere dalla soluzione scelta, vi `e un’assoluta indipendenza di ogni peer nel determinare la propria rapp- resentazione. Per questo motivo non vengono utilizzate soluzioni pi`u complesse che comportano il supporto di una struttura esterna oppure una propagazione a pioggia dei messaggi nell’overlay network in presenza di cambiamenti nel profilo dei peer.