Le informazioni relative alle viste di un gruppo posson essere presentate come un grafo diretto K = (Π, E). Per ogni coppia di processi P pi, pj esiste un arco (pi,pj) nel grafo se pj ∈ group viewi e un arco (pj,pi) se pi∈ group viewj. Esiste inoltre un arco (pi,pi) per ogni processo pi, cosicch´e pi ∈ group viewi. Il grafo rappresenta l’overlay network su cui avvengono le comunicazioni del protocollo di multicast di livello applicativo in ambiente peer-to-peer.
Specifica
Ogni servizio di notification membership deve manipolare le conoscenze sul grafo dinamicamente costruito in modo da:
1. connettere un nuovo membro che ha eseguito un’operazione di join;
2. disconnettere un nodo in uscita senza creare una partizione; 3. tollerare i guasti dei processi mantenendo il grafo connesso.
La specifica deve garantire che, dopo la stabilizzazione della overlay, ogni peer converga in un tempo finito in una vista che includa tutti i peer. Chiaramente se la rete non si stabilizza non `e possibile dare alcune specifica, poich´e non si `e in grado
di stabilire che `e nel gruppo e chi ne `e fuori. La specifica garantisce, inoltre, che le operazioni di join e leave debbano richiedere un tempo finito per giungere a conclusione.
Safety Dato che le informazioni delle viste sono propagate sugli archi del grafo, ogni arco `e un fair-lossy link, una volta che join e leave cessano, ogni membro stazionario
pi dovrebbe avere, per ogni altro membro stazionario, almeno un cammino formato da membri stazionari. Questo `e necessario perch´e, anche se join e leave non possono pi`u avvenire, sono sempre possibili dei crash in grado di partizionare il sistema. Dunque, se la condizione `e soddisfatta, la view di ogni membro stazionario conterr`a eventualmente tutti i membri stazionari.
Propriet`a 3.2.1. (Safety) Se K = (Π, E) denota il grafo della overlay nell’istante t
e se nessuna arco (pi,pi) verr`a aggiunto o rimosso per ogni t0 > t(cio´e join e leave cessano all’istante t). Se Consideriamo il sottografo Ks= (S, Es) tale che:
1. pi∈ Π e pi `e stazionario ⇔ pi ∈ S; 2. ∀pi, pj ∈ S, (pi, pj) ∈ E ⇔ (pi, pj) ∈ Es;
Allora, ∀pi, pj ∈ S esister`a un arco (pi, pj) nella chiusura transitiva di Es per ogni t0 > t.
Liveness Un’implementazione banale di un servizio di group membership potrebbe soddisfare la safety appena vista semplicemente bloccando l’esecuzione, e il completa-mento, di operazioni di join e leave e scegliendo, nel caso in cui il gruppo non sia vuoto, una topologia del grafo in grado di tollerare un certo numero di guasti.
Per prevenire implementazioni statiche occorre aggiungere la seguente propriet`a: Propriet`a 3.2.2. (Liveness) L’esecuzione delle operazioni di join(G) e di leave(G)
devono richiedere un tempo finito.
Risultati di impossibilit`a
Un processo pi ottiene da M N Si una lista di membri di G. Idealmente non ci sono as-sunzioni sulla composizione della contact list access virewi, infatti la specifica di MNS pone l’accento solo sulla composizione della group viewi. Possiamo, pertanto, partire solamente dall’assunzione che l’access viewi `e costituita da un insieme casuale di pro-cessi appartenti a Π, senza alcuna relazione con la membership corrente. In altre parole
3.2. DET 59
access viewi pu`o non essere n`e accurata, pu`o includere processi che non sono ancora membri, n`e completa, pu`o non includere alcuni processi membri. Sfortunatamente per garantire la specifica di MNS anche access viewi dovr`a soddisfare alcune propriet`a.
[section]
Risultato di Impossibilit`a 3.2.3. Se esiste un istante t ∈ T tale che G(t) ≡ ∅, allora
la specifica di MNS non pu`o essere garantita.
Risultato di Impossibilit`a 3.2.4. Se esiste un’istante t ∈ T tale che G(t) non
contenga membri stazionari, allora la specifica di MNS non pu`o essere garantita.
Si deve quindi far ricorso alla presenza di processi stazionari all’interno del gruppo per poter aggirare questi risultati, per la cui dimostrazione rimandiamo a [5].
La presenza di processi stazionari non `e necessaria soltanto per garantire la liveness dell’operazione di join() ma anche di quella della leave(). Un processo in leave deve comunicare la sua vista ai vicini prima di uscire e, se non vi sono processi stazionari nel gruppo, il processo in leaving non sarebbe sempre in grado di effettuare questa comunicazione in un tempo finito.
Il problema di circolarit`a
Dal risultato di Impossibilit`a 3.2.4 otteniamo il seguente Corollario: [section]
Corollario 3.2.5. Se access viewi non contiene eventualmente almeno un membro stazionario allora la specifica di MNS non pu`o essere garantita.
In particolare se access viewi non contiene un membro stazionario la propriet`a di liveness per l’operazione di join pu`o essere violata. Questo risultato pone un problema di circolarit`a qualora l’implementazione dell’MNS venga operata in un sistema p2p puro. Idealmente il gruppo di peer che devono far parte di access viewi dovrebbero essere definiti a run-time fra i peer che fanno parte del gruppo; questo implica che non sia possibile includere alcuni particolari peer nelle access view. La lista di accesso non pu`o essere ottenuta in modalit`a push-based, da un membro corrente del gruppo al nuovo entrante, poich´e nessun membro del gruppo ancora conosce il nuovo entrante, e non `e pensabile, poich´e il numero di processi `e illimitato, fornire una vista con tutti i processi. Da quanto detto ne consegue che per scoprire un peer attualmente appartenente al gruppo, il nuovo processo debba contattare un processo speciale che conosca alcuni
peer. Ma in un approccio puramente peer-to-peer solo un peer pu`o conoscere altri peer, di conseguenza per avere la conoscenza di un peer il processo entrante dovrebbe conoscerne gi`a altri. Per ovviare a questo problema di circolarit`a `e necessaria l’esistenza di un insieme di processi speciali conosciuti da ogni membro del gruppo, al prezzo della perdita dell’approccio peer-to-peer puro.