Tabla de hash distribuida
Esto permite que las DHTs puedan escalar a cantidades de nodos extremadamente grandes, y que puedan manejar constantes errores, llegadas y caídas de nodos.
Las búsquedas por medio de DHTs fueron motivadas originalmente por los sistemas peer-to-peer como Napster, Gnutella, y Freenet, que aprovechaban recursos distribuidos en Internet para proveer una única aplicación.
Una desventaja es que las DHTs así como Freenet, solo soportan búsquedas de coincidencia exacta, no obstante es posible implementar una funcionalidad de búsquedas por palabra clave como una capa superior a las DHTs.
Las primeras cuatro DHTs - CAN, Chord, Pastry y Tapestry- surgieron en la misma época durante el 2001.
Desde entonces esta forma de búsqueda ha sido muy usada, principalmente desde que BitTorrent las incorporó.
Las DHTs destacan las siguientes propiedades: Una técnica clave utilizada para lograr estos objetivos es que cualquier nodo se debe coordinar con solo unos pocos nodos en el sistema - la más común, O (log n) de los n participantes (ver abajo) - de manera que ante un cambio en la composición solamente es necesario una cantidad limitada de trabajo.
Algunos diseños de DHT buscan ser seguros contra los participantes maliciosos [2] y permiten a los participantes permanecer en el anonimato, aunque esto es menos común que en muchos otros sistemas peer-to-peer (sobre todo para compartir archivos), ver peer-to-peer anónimo.
Luego se envía un mensaje put(K, data) a los nodos participantes en la DHT.
Esta técnica implementa una función δ(k1,k2) que define una noción abstracta de la distancia entre la clave k1 y k2, la cual no está relacionada con la distancia geográfica o la latencia de la red.
Así, el espacio de claves circular se divide en segmentos contiguos cuyos extremos son los identificadores del nodo.
La localidad del hashing trata de asegurar que a claves similares se asignen objetos familiares.
Todas las topologías DHT comparten alguna variante de la siguiente propiedad: para cualquier clave “k”, pasa que el nodo tiene un ID que posee “k” o tiene un enlace a un nodo cuyo ID es más cercano a “k”, en términos de la distancia definida en el espacio de claves.
De esta forma es fácil enrutar un mensaje hacia el dueño de cualquier clave “k” usando un algoritmo “greedy” (algoritmo voraz), que no necesariamente es óptimo a nivel global.
El algoritmo consiste en reenviar el mensaje al vecino cuyo ID es más cercano a “k” de forma sucesiva, y cuando no existe ese vecino, es porque se llegó al nodo más cercano el cual posee “k”.
Este estilo de enrutamiento se suele llamar “key based routing”.
