Si basa su un overlay ad anello con N=2m GUID.
Il nodo responsabile di una determinata chiave K è quello con il primo identificativo W tale che W succede K in senso orario.
Ogni nodo x in Chord mantiene informazioni su:
gli m successori più il predecessore
La correttezza di Chord si basa sul presupposto che ogni peer conosca esattamente i successori e i finger.
Tale requisito può essere compromesso dalla dinamicità dei peer.
Per mantenere la correttezza dei dati di routing sono eseguiti periodicamente appositi algoritmi di stabilizzazione.
Ogni nodo conserva informazioni su (m+1) nodi (→ O(log N)).
L’operazione di lookup richiede m messaggi (→ O(log N)).
In caso di connessione alla rete o abbandono della rete il numero di messaggi è Ω(log2N).
Anche Pastry usa un overlay ad anello.
Ad ogni nodo è assegnato un GUID a 128-bit, ottenuto applicando una funzione hash alla chiave pubblica.
Ad ogni file è assegnato un GUID a 128-bit, ottenuto applicando una funzione hash al nome del file stesso.
I GUID sono distribuiti in maniera random tra 0 e 2128-1.
Per determinare i nodi vicini, Pastry utilizza delle metriche di località (hop count o round-trip latency).
Sfrutta la vicinanza numerica dei nodi.
Ogni query di un dato con chiave k viene istradata verso il nodo vicino il cui GUID è numericamente più vicino a k.
Ogni nodo dispone delle seguenti strutture.
Pastry utilizza un meccanismo di heartbeat per rilevare i fallimenti e, quindi, riparare i leaf set.
Periodicamente i peer scambiano messaggi di PING, il peer che non risponde entro un certo timeout è considerato fallito.
Il nodo che ha scoperto il fallimento, contatta il peer numericamente successivo a quello fallito, chiedendo una copia del suo leaf set.
Il leaf set ricevuto avrà delle sovrapposizioni con quello in possesso dal peer che ha iniziato la procedura, ma anche validi peer per sostituire quello fallito.
I peer vicini sono informati del fallimento e eseguono la stessa procedura.
Mediamente, la tabella di routing di ciascun nodo ha log16N righe; inoltre c’è il leaf set (16•log16N+L → O(log N)).
L’operazione di lookup richiede O(log N) messaggi.
In caso di connessione alla rete o abbandono della rete il numero di messaggi è O(log N).
Freenet migliora le prestazioni del flooding strutturando scarsamente l’overlay network:
Ogni nodo presenta due liste di chiavi:
Il peer A avvia il flooding di richieste per un dato detenuto da D.
Quando D riceve la richiesta, non contatta direttamente A, ma ripercorre al contrario il percorso di lookup.
Ogni nodo contattato memorizza nella seconda lista la chiave e il next_hop così da definire una scorciatoia (routing short-cut) per successive query dello stesso dato.
1. Caratterizzazione dei sistemi distribuiti
2. Modelli di sistemi distribuiti
3. Tempo e sincronizzazione nei Sistemi Distribuiti
4. Stato globale nei Sistemi Distribuiti
5. Problemi di consenso nei sistemi distribuiti
7. Algoritmi di mutua esclusione nei sistemi distribuiti
8. Algoritmi di elezione nei sistemi distribuiti
10. Il Network File System di SUN Microsystems
11. AFS (Andrew File System) e GFS (Google File System)
12. Transazioni e controllo di concorrenza
13. Transazioni
15. Affidabilità (dependability) dei sistemi software distribuiti
16. Affidabilità dei sistemi software distribuiti
17. Software Faults
18. Classificazione e analisi dei difetti software
S. Ratnasamy, S. Shenker, and I. Stoica. “Routing algorithms for DHTs: Some open questions”. In In 1st International Peer To Peer Systems Workshop (IPTPS02).
I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, H. Balakrishnan, “Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications”. In IEEE/ACM Trans. on Networking, 2003.
www.napster.com
www.gnutella.com
www.gnutella2.com
www.openp2p.com
www.overnet.com