Un algoritmo per gestire la ricerca in un sistema peer to peer è l’algoritmo Chord.
Il sistema Chord è composto da n utenti ognuno dei quali condivide delle risorse e conserva una porzione dell’indice.
Ogni nodo ha un indirizzo IP e un identificatore numerico di 160 bit ricavato dall’indirizzo IP applicando una funzione di hash (SHA-1).
Tutti i 2160 possibili identificatori vengono considerati come se fossero disposti in un cerchio in ordine crescente; alcuni identificatori corrispondono effettivamente a partecipanti al sistema, altri no.
Viene definita una funzione successor(k) che identifica il primo nodo successore di k in senso orario che corrisponde effettivamente a un partecipante.
Anche ai nomi delle risorse viene applicato l’algoritmo di hash (SHA-1) per ottenere una chiave di 160 bit.
Un utente che mette a disposizione una risorsa costruisce il record (nome della risorsa, proprio indirizzo IP) e chiede a successor(hash(nome della risorsa)) di conservare il record nel suo indice.
In questo modo riferimenti a nodi diversi che condividono la stessa risorsa verranno conservati nell’indice di uno stesso nodo.
L’indice è distribuito in modo casuale attraverso i nodi.
Quando un utente deve cercare una risorsa calcola facilmente la chiave (hash(nome della risorsa)). Poi calcola successor(chiave) per trovare l’indirizzo IP del nodo che conserva l’indice relativo a quella risorsa. Il problema è raggiungere il nodo che ha quell’indirizzo IP.
Ogni nodo deve conoscere l’indirizzo IP del suo successore; il richiedente invia al suo successore un pacchetto contenente la chiave cercata e il proprio indirizzo IP; il pacchetto si propaga lungo l’anello fino a quando individua il nodo con indirizzo IP corrispondente a successor(chiave); quel nodo verifica se nell’indice ha dei riferimenti che corrispondono alla chiave e in caso affermativo restituisce i dati direttamente al richiedente.
Una ricerca lineare di questo tipo è molto inefficiente. In realtà ogni nodo mantiene una tabella di puntamento di m voci che permette di aumentare notevolmente l’efficienza della ricerca.
I nodi si uniscono e staccano continuamente dal sistema.
Si può pensare che inizialmente il sistema sia composto da pochi nodi; tutti i nodi si scambiano direttamente le informazioni necessarie per costruire il primo cerchio.
Ogni nodo conserva anche l’indirizzo IP del suo predecessore.
Quando un nuovo nodo vuole unirsi al sistema applica la funzione di hash al proprio indirizzo IP per calcolare il proprio identificatore r nel cerchio; poi contatta un nodo già esistente chiedendogli di cercare l’indirizzo IP di successor(r), chiede a successor(r) l’indirizzo IP del suo predecessore e poi chiede a entrambi di inserirsi tra di loro.
Quando un nodo abbandona il sistema consegna il proprio indice al suo successore e informa il predecessore che sta uscendo, in modo che si colleghi al suo successore.
