Una tabla hash distribuida ( DHT ) es un sistema distribuido que proporciona un servicio de búsqueda similar a una tabla hash : los pares clave-valor se almacenan en un DHT y cualquier nodo participante puede recuperar de manera eficiente el valor asociado con una clave determinada . La principal ventaja de un DHT es que los nodos se pueden agregar o eliminar con un trabajo mínimo en torno a la redistribución de claves. Las claves son identificadores únicos que se asignan a valores particulares , que a su vez pueden ser cualquier cosa, desde direcciones hasta documentos y datos arbitrarios . [1]La responsabilidad de mantener el mapeo de claves a valores se distribuye entre los nodos, de tal manera que un cambio en el conjunto de participantes provoca una mínima interrupción. Esto permite que un DHT escale a un número extremadamente grande de nodos y maneje llegadas, salidas y fallas continuas de nodos.
Los DHT forman una infraestructura que se puede utilizar para crear servicios más complejos, como anycast , almacenamiento en caché web cooperativo , sistemas de archivos distribuidos , servicios de nombres de dominio , mensajería instantánea , multidifusión y también sistemas de distribución de contenido y intercambio de archivos de igual a igual . Las redes distribuidas notables que utilizan DHT incluyen el rastreador distribuido de BitTorrent , Coral Content Distribution Network , la red Kad , la botnet Storm , la mensajería instantánea Tox , Freenet , el motor de búsqueda YaCy y el InterPlanetary File System .
Historia
La investigación de DHT fue motivada originalmente, en parte, por sistemas peer-to-peer (P2P) como Freenet , Gnutella , BitTorrent y Napster , que aprovecharon los recursos distribuidos a través de Internet para proporcionar una única aplicación útil. En particular, aprovecharon el aumento del ancho de banda y la capacidad del disco duro para brindar un servicio de intercambio de archivos. [2]
Estos sistemas diferían en cómo ubicaban los datos ofrecidos por sus pares. Napster, el primer sistema de entrega de contenido P2P a gran escala, requería un servidor de índice central: cada nodo, al unirse, enviaba una lista de archivos almacenados localmente al servidor, que realizaría búsquedas y remitiría las consultas a los nodos que contenían el resultados. Este componente central dejó al sistema vulnerable a ataques y juicios.
Gnutella y redes similares pasaron a un modelo de inundación de consultas ; en esencia, cada búsqueda daría como resultado la transmisión de un mensaje a todas las demás máquinas de la red. Si bien evita un solo punto de falla , este método fue significativamente menos eficiente que Napster. Las versiones posteriores de los clientes de Gnutella pasaron a un modelo de consulta dinámica que mejoró enormemente la eficiencia. [3]
Freenet está completamente distribuido, pero emplea un enrutamiento heurístico basado en claves en el que cada archivo está asociado con una clave, y los archivos con claves similares tienden a agruparse en un conjunto similar de nodos. Es probable que las consultas se enruten a través de la red a dicho clúster sin necesidad de visitar muchos pares. [4] Sin embargo, Freenet no garantiza que se encontrarán los datos.
Las tablas hash distribuidas utilizan un enrutamiento basado en claves más estructurado para lograr tanto la descentralización de Freenet y Gnutella como la eficiencia y los resultados garantizados de Napster. Un inconveniente es que, al igual que Freenet, los DHT solo admiten directamente la búsqueda de coincidencia exacta, en lugar de la búsqueda de palabras clave, aunque el algoritmo de enrutamiento de Freenet se puede generalizar a cualquier tipo de clave donde se pueda definir una operación de proximidad. [5]
En 2001, cuatro sistemas — CAN , [6] Acorde , [7] Pastelería y Tapiz — encendieron las DHT como un tema de investigación popular. Un proyecto llamado Infraestructura para sistemas de Internet resilientes (Iris) fue financiado por una subvención de $ 12 millones de la Fundación Nacional de Ciencias de los Estados Unidos en 2002. [8] Los investigadores incluyeron a Sylvia Ratnasamy , Ion Stoica , Hari Balakrishnan y Scott Shenker . [9] Fuera de la academia, la tecnología DHT se ha adoptado como un componente de BitTorrent y en Coral Content Distribution Network .
Propiedades
Los DHT enfatizan característicamente las siguientes propiedades:
- Autonomía y descentralización : los nodos forman colectivamente el sistema sin ninguna coordinación central.
- Tolerancia a fallas : el sistema debe ser confiable (en cierto sentido) incluso con nodos que se unen, abandonan y fallan continuamente. [10]
- Escalabilidad : el sistema debería funcionar de manera eficiente incluso con miles o millones de nodos.
Una técnica clave utilizada para lograr estos objetivos es que cualquier nodo necesita coordinarse con solo unos pocos otros nodos en el sistema, más comúnmente, O (log n ) de los n participantes (ver más abajo), de modo que solo una cantidad limitada de es necesario trabajar para cada cambio de membresía.
Algunos diseños de DHT buscan ser seguros contra participantes malintencionados [11] y permitir que los participantes permanezcan en el anonimato , aunque esto es menos común que en muchos otros sistemas peer-to-peer (especialmente el intercambio de archivos ); ver P2P anónimo .
Finalmente, los DHT deben lidiar con problemas de sistemas distribuidos más tradicionales, como el equilibrio de carga , la integridad de los datos y el rendimiento (en particular, garantizar que las operaciones como el enrutamiento y el almacenamiento o la recuperación de datos se completen rápidamente).
Estructura
La estructura de un DHT se puede descomponer en varios componentes principales. [12] [13] La base es un espacio de claves abstracto , como el conjunto de cadenas de 160 bits . Un esquema de partición de espacio de claves divide la propiedad de este espacio de claves entre los nodos participantes. Una red superpuesta a continuación, conecta los nodos, lo que les permite encontrar al propietario de cualquier llave dada en el espacio de claves.
Una vez que estos componentes están en su lugar, un uso típico del DHT para almacenamiento y recuperación podría proceder de la siguiente manera. Suponga que el espacio de claves es el conjunto de cadenas de 160 bits. Para indexar un archivo con un nombre de archivo y datos dados en el DHT, se genera el hash SHA-1 del nombre del archivo , produciendo una clave k de 160 bits , y se envía un mensaje put ( k, data ) a cualquier nodo que participe en el DHT. El mensaje se reenvía de un nodo a otro a través de la red superpuesta hasta que llega al único nodo responsable de la clave k según lo especificado por la partición del espacio de claves. Ese nodo luego almacena la clave y los datos. Cualquier otro cliente puede recuperar el contenido del archivo volviendo a hacer hash en el nombre del archivo para producir k y pidiendo a cualquier nodo DHT que encuentre los datos asociados con k con un mensaje get ( k ) . El mensaje se enrutará nuevamente a través de la superposición al nodo responsable de k , que responderá con los datos almacenados .
Los componentes de red de superposición y partición del espacio de claves se describen a continuación con el objetivo de capturar las ideas principales comunes a la mayoría de los DHT; muchos diseños difieren en los detalles.
Partición del espacio de claves
La mayoría de los DHT utilizan alguna variante de hash consistente o hash de encuentro para asignar claves a los nodos. Los dos algoritmos parecen haber sido diseñados de forma independiente y simultánea para resolver el problema de la tabla hash distribuida.
Tanto el hash consistente como el hash de encuentro tienen la propiedad esencial de que la eliminación o adición de un nodo cambia solo el conjunto de claves propiedad de los nodos con ID adyacentes y no afecta a todos los demás nodos. Compare esto con una tabla hash tradicional en la que la adición o eliminación de un depósito hace que se reasigne casi todo el espacio de claves. Dado que cualquier cambio en la propiedad normalmente corresponde a un movimiento intensivo del ancho de banda de los objetos almacenados en el DHT de un nodo a otro, se requiere minimizar dicha reorganización para soportar de manera eficiente altas tasas de abandono (llegada y falla de nodos).
Hash consistente
El hash consistente emplea una función que define una noción abstracta de la distancia entre las teclas y , que no está relacionado con la distancia geográfica o la latencia de la red . A cada nodo se le asigna una clave única llamada su identificador (ID). Un nodo con ID posee todas las llaves para cual es el ID más cercano, medido según .
Por ejemplo, Chord DHT usa hash consistente, que trata los nodos como puntos en un círculo, y es la distancia que viaja en el sentido de las agujas del reloj alrededor del círculo desde a . Por lo tanto, el espacio de claves circular se divide en segmentos contiguos cuyos puntos finales son los identificadores de nodo. Si y son dos ID adyacentes, con una distancia más corta en el sentido de las agujas del reloj desde a , luego el nodo con ID posee todas las llaves que caen entre y .
Hash de encuentro
En el hash de encuentro, también llamado hash de peso aleatorio más alto (HRW), todos los clientes usan la misma función de hash (elegido de antemano) para asociar una clave a uno de los n servidores disponibles. Cada cliente tiene la misma lista de identificadores { S 1 , S 2 , ..., S n } , uno para cada servidor. Dada alguna clave k , un cliente calcula n pesos hash w 1 = h ( S 1 , k ), w 2 = h ( S 2 , k ), ..., w n = h ( S n , k ) . El cliente asocia esa clave con el servidor correspondiente al peso hash más alto para esa clave. Un servidor con ID posee todas las llaves para el cual el peso del hash es mayor que el peso hash de cualquier otro nodo para esa clave.
Hash para preservar la localidad
El hash que conserva la localidad garantiza que se asignen claves similares a objetos similares. Esto puede permitir una ejecución más eficiente de consultas de rango; sin embargo, en contraste con el uso de hash consistente, no hay más garantía de que las claves (y por lo tanto la carga) se distribuyan de manera uniforme y aleatoria en el espacio de claves y los pares participantes. Los protocolos DHT como Self-Chord y Oscar [14] abordan estos problemas. Self-Chord desacopla las claves de objeto de las ID de pares y clasifica las claves a lo largo del anillo con un enfoque estadístico basado en el paradigma de inteligencia de enjambre . [15] La clasificación garantiza que los nodos vecinos almacenen claves similares y que los procedimientos de descubrimiento, incluidas las consultas de rango , se puedan realizar en tiempo logarítmico. Oscar construye una red navegable de pequeños mundos basada en un muestreo de caminatas aleatorias que también asegura el tiempo de búsqueda logarítmica.
Red superpuesta
Cada nodo mantiene un conjunto de enlaces a otros nodos (sus vecinos o tabla de enrutamiento ). Juntos, estos enlaces forman la red superpuesta. [16] Un nodo elige a sus vecinos de acuerdo con una determinada estructura, llamada topología de la red .
Todas las topologías DHT comparten alguna variante de la propiedad más esencial: para cualquier clave k , cada nodo tiene una ID de nodo que posee k o tiene un enlace a un nodo cuyo ID de nodo está más cerca de k , en términos de la distancia del espacio de claves definida anteriormente. . Entonces es fácil enrutar un mensaje al propietario de cualquier clave k usando el siguiente algoritmo codicioso (que no es necesariamente óptimo globalmente): en cada paso, reenvíe el mensaje al vecino cuyo ID está más cerca de k . Cuando no existe tal vecino, entonces debemos haber llegado al nodo más cercano, que es el propietario de k como se definió anteriormente. Este estilo de enrutamiento a veces se denomina enrutamiento basado en claves .
Más allá de la corrección básica del enrutamiento, dos restricciones importantes en la topología son garantizar que el número máximo de saltos en cualquier ruta (longitud de ruta) sea bajo, de modo que las solicitudes se completen rápidamente; y que el número máximo de vecinos de cualquier nodo ( grado máximo de nodo ) es bajo, por lo que la sobrecarga de mantenimiento no es excesiva. Por supuesto, tener rutas más cortas requiere un grado máximo más alto . Algunas opciones comunes para el grado máximo y la longitud de la ruta son las siguientes, donde n es el número de nodos en el DHT, utilizando la notación Big O :
Max. la licenciatura | Longitud máxima de la ruta | Utilizado en | Nota |
---|---|---|---|
Peores longitudes de búsqueda, con tiempos de búsqueda probablemente mucho más lentos | |||
Koorde (con grado constante) | Más complejo de implementar, pero se puede encontrar un tiempo de búsqueda aceptable con un número fijo de conexiones | ||
Tapiz de pastelería Chord Kademlia | Más común, pero no óptimo (grado / longitud de ruta). Chord es la versión más básica, y Kademlia parece ser la variante optimizada más popular (debería haber mejorado la búsqueda promedio) | ||
Koorde (con búsqueda óptima) | Más complejo de implementar, pero las búsquedas pueden ser más rápidas (tienen un límite más bajo en el peor de los casos) | ||
Las peores necesidades de almacenamiento local, con mucha comunicación después de que cualquier nodo se conecta o desconecta |
La opción más común, grado / longitud de ruta, no es óptimo en términos de compensación de grado / longitud de ruta, pero tales topologías típicamente permiten más flexibilidad en la elección de vecinos. Muchos DHT utilizan esa flexibilidad para elegir vecinos cercanos en términos de latencia en la red física subyacente. En general, todas las DHT construyen topologías de red navegables de mundo pequeño, que compensan la longitud de la ruta frente al grado de la red. [17]
La longitud máxima de la ruta está estrechamente relacionada con el diámetro : el número máximo de saltos en cualquier ruta más corta entre nodos. Claramente, la longitud de ruta en el peor de los casos de la red es al menos tan grande como su diámetro, por lo que las DHT están limitadas por la compensación de grado / diámetro [18] que es fundamental en la teoría de grafos . La longitud de la ruta puede ser mayor que el diámetro, ya que es posible que el algoritmo de enrutamiento codicioso no encuentre las rutas más cortas. [19]
Algoritmos para redes superpuestas
Aparte del enrutamiento, existen muchos algoritmos que explotan la estructura de la red superpuesta para enviar un mensaje a todos los nodos, o un subconjunto de nodos, en un DHT. [20] Las aplicaciones utilizan estos algoritmos para superponer multidifusión , consultas de rango o recopilar estadísticas. Dos sistemas que se basan en este enfoque son Structella, [21] que implementa inundaciones y caminatas aleatorias en una superposición de pastelería, y DQ-DHT, que implementa un algoritmo de búsqueda de consultas dinámicas sobre una red Chord. [22]
Seguridad
Debido a la descentralización, la tolerancia a fallas y la escalabilidad de los DHT, son intrínsecamente más resistentes contra un atacante hostil que un sistema centralizado. [ vago ]
Los sistemas abiertos para el almacenamiento de datos distribuidos que son robustos contra atacantes hostiles masivos son factibles. [23]
Un sistema DHT que está cuidadosamente diseñado para tener tolerancia a fallas bizantinas puede defenderse de una debilidad de seguridad, conocida como el ataque Sybil , que afecta a todos los diseños DHT actuales. [24] [25]
Petar Maymounkov, uno de los autores originales de Kademlia , ha propuesto una forma de sortear la debilidad del ataque de Sybil incorporando relaciones de confianza social en el diseño del sistema. [26] El nuevo sistema, cuyo nombre en código es Tonika o también conocido por su nombre de dominio como 5ttt, se basa en un diseño de algoritmo conocido como "enrutamiento eléctrico" y es coautor del matemático Jonathan Kelner. [27] Maymounkov ha emprendido ahora un esfuerzo de implementación integral de este nuevo sistema. Sin embargo, la investigación sobre las defensas efectivas contra los ataques de Sybil generalmente se considera una cuestión abierta, y cada año se propone una amplia variedad de defensas potenciales en las principales conferencias de investigación de seguridad. [ cita requerida ]
Implementaciones
Las diferencias más notables encontradas en casos prácticos de implementaciones de DHT incluyen al menos lo siguiente:
- El espacio de direcciones es un parámetro de DHT. Varios DHT del mundo real utilizan un espacio de clave de 128 o 160 bits.
- Algunos DHT del mundo real utilizan funciones hash distintas de SHA-1 .
- En el mundo real la clave k podría ser un hash del contenido de un archivo en lugar de un hash del nombre de un archivo para proporcionar almacenamiento direccionable por contenido , de modo que el cambio de nombre del archivo no impida que los usuarios lo encuentren.
- Algunas DHT también pueden publicar objetos de diferentes tipos. Por ejemplo, clave k podría ser el nodo La identificación y los datos asociados podrían describir cómo ponerse en contacto con este nodo. Esto permite la publicación de información de presencia y se usa a menudo en aplicaciones de mensajería instantánea, etc. En el caso más simple, La identificación es solo un número aleatorio que se usa directamente como clave k (por lo que en un DHT de 160 bits El ID será un número de 160 bits, generalmente elegido al azar). En algunos DHT, la publicación de los ID de los nodos también se utiliza para optimizar las operaciones de DHT.
- Se puede agregar redundancia para mejorar la confiabilidad. La El par de claves (k, datos) se puede almacenar en más de un nodo correspondiente a la clave. Por lo general, en lugar de seleccionar un solo nodo, los algoritmos DHT del mundo real seleccionan i nodos adecuados, con i es un parámetro específico de la implementación de la DHT. En algunos diseños de DHT, los nodos acuerdan manejar un cierto rango de espacio de teclas, cuyo tamaño puede elegirse dinámicamente, en lugar de codificarse.
- Algunos DHT avanzados como Kademlia realizan búsquedas iterativas a través del DHT primero para seleccionar un conjunto de nodos adecuados y enviar enviar mensajes (k, datos) solo a esos nodos, lo que reduce drásticamente el tráfico inútil, ya que los mensajes publicados solo se envían a los nodos que parecen adecuados para almacenar la clave k ; y las búsquedas iterativas cubren solo un pequeño conjunto de nodos en lugar de todo el DHT, lo que reduce el reenvío inútil. En tales DHT, el reenvío de Los mensajes put (k, data) solo pueden ocurrir como parte de un algoritmo de autorreparación: si un nodo de destino recibe un poner (k, datos) mensaje, pero cree que k está fuera de su rango manejado y se conoce un nodo más cercano (en términos de espacio de claves DHT), el mensaje se reenvía a ese nodo. De lo contrario, los datos se indexan localmente. Esto conduce a un comportamiento de DHT algo autoequilibrado. Por supuesto, dicho algoritmo requiere que los nodos publiquen sus datos de presencia en el DHT para que se puedan realizar búsquedas iterativas.
- Dado que en la mayoría de las máquinas el envío de mensajes es mucho más caro que el acceso a la tabla hash local, tiene sentido agrupar muchos mensajes relacionados con un nodo en particular en un solo lote. Suponiendo que cada nodo tiene un lote local que consta de como máximo b operaciones, el procedimiento de agrupación es el siguiente. Cada nodo ordena primero su lote local por el identificador del nodo responsable de la operación. Usando la clasificación de cubos , esto se puede hacer en O (b + n) , donde n es el número de nodos en el DHT. Cuando hay varias operaciones que abordan la misma clave dentro de un lote, el lote se condensa antes de enviarse. Por ejemplo, múltiples búsquedas de la misma clave se pueden reducir a una o múltiples incrementos se pueden reducir a una sola operación de adición. Esta reducción se puede implementar con la ayuda de una tabla hash local temporal. Finalmente, las operaciones se envían a los respectivos nodos. [28]
Ejemplos de
Implementaciones y protocolos DHT
- Apache Cassandra
- Superposición de BATON
- Mainline DHT - DHT estándar utilizado por BitTorrent (basado en Kademlia proporcionado por Khashmir) [29]
- Red direccionable de contenido (CAN)
- Acorde
- Koorde
- Kademlia
- Pastelería
- P-Grid
- Riak
- Tapiz
- TomP2P
- Voldemort
Aplicaciones que utilizan DHT
- BTDigg : motor de búsqueda BitTorrent DHT
- Codeen : almacenamiento en caché web
- Red de distribución de contenido de coral
- Freenet : una red anónima resistente a la censura
- GlusterFS : un sistema de archivos distribuido utilizado para la virtualización del almacenamiento
- GNUnet : red de distribución similar a Freenet que incluye una implementación DHT
- I2P : una red de igual a igual anónima de código abierto
- I2P-Bote : correo electrónico anónimo seguro sin servidor
- IPFS : un protocolo de distribución de hipermedia peer-to-peer con contenido direccionable
- JXTA : plataforma P2P de código abierto
- Oracle Coherence : una cuadrícula de datos en memoria construida sobre una implementación de DHT de Java
- Perfect Dark : una aplicación de intercambio de archivos de igual a igual de Japón
- Retroshare : una red de amigo a amigo [30]
- Jami : una plataforma de comunicación de voz, video y chat que preserva la privacidad, basada en un DHT similar a Kademlia
- Tox : un sistema de mensajería instantánea destinado a funcionar como reemplazo de Skype
- Twister : una plataforma peer-to-peer de microblogueo
- YaCy : un motor de búsqueda distribuido
Ver también
- Couchbase Server : un sistema de almacenamiento de objetos distribuidos en clúster, replicado y persistente compatible con el protocolo memcached.
- Memcached : un sistema de almacenamiento en caché de objetos de memoria distribuida de alto rendimiento.
- Árbol de hash de prefijo : consulta sofisticada sobre DHT.
- Árbol de Merkle : árbol que tiene cada nodo no hoja etiquetado con el hash de las etiquetas de sus nodos hijos.
- La mayoría de los almacenes de datos distribuidos emplean alguna forma de DHT para la búsqueda.
- Los gráficos de omisión son una estructura de datos eficiente para implementar DHT.
Referencias
- ^ Stoica, I .; Morris, R .; Karger, D .; Kaashoek, MF; Balakrishnan, H. (2001). "Chord: un servicio de búsqueda escalable de igual a igual para aplicaciones de Internet" (PDF) . Revisión de comunicación informática ACM SIGCOMM . 31 (4): 149. doi : 10.1145 / 964723.383071 .
Un valor puede ser una dirección, un documento o un dato arbitrario.
- ^ Liz, Crowcroft; et al. (2005). "Una encuesta y una comparación de los esquemas de red de superposición de igual a igual" (PDF) . Encuestas y tutoriales de comunicaciones de IEEE . 7 (2): 72–93. CiteSeerX 10.1.1.109.6124 . doi : 10.1109 / COMST.2005.1610546 . S2CID 7971188 .
- ^ Richter, Stevenson; et al. (2009). "Análisis del impacto de los modelos de consultas dinámicas en las relaciones cliente-servidor". Tendencias en la informática moderna : 682–701.
- ^ Buscando en un mundo pequeño, capítulos 1 y 2 (PDF) , consultado el 10 de enero de 2012
- ^ "Section 5.2.2" (PDF) , A Distributed Descentralized Information Storage and Retrieval System , consultado el 10 de enero de 2012
- ^ Ratnasamy; et al. (2001). "Una red de contenido direccionable escalable" (PDF) . En Actas de ACM SIGCOMM 2001 . Consultado el 20 de mayo de 2013 . Cite journal requiere
|journal=
( ayuda ) - ^ Hari Balakrishnan , M. Frans Kaashoek , David Karger, Robert Morris e Ion Stoica. Búsqueda de datos en sistemas P2P . En Comunicaciones de la ACM , febrero de 2003.
- ^ David Cohen (1 de octubre de 2002). "Nueva red P2P financiada por el gobierno de Estados Unidos" . Nuevo científico . Consultado el 10 de noviembre de 2013 .
- ^ "MIT, Berkeley, ICSI, NYU y Rice lanzan el proyecto IRIS" . Comunicado de prensa . MIT. 25 de septiembre de 2002. Archivado desde el original el 26 de septiembre de 2015 . Consultado el 10 de noviembre de 2013 .
- ^ R Mokadem, A Hameurlain y AM Tjoa. Servicio de descubrimiento de recursos mientras se minimiza la sobrecarga de mantenimiento en sistemas DHT jerárquicos . Proc. iiWas, 2010
- ^ Guido Urdaneta, Guillaume Pierre y Maarten van Steen. Una encuesta sobre técnicas de seguridad DHT . Encuestas de computación de ACM 43 (2), enero de 2011.
- ^ Moni Naor y Udi Wieder. Arquitecturas novedosas para aplicaciones P2P: el enfoque continuo-discreto . Proc. SPAA, 2003.
- ^ Gurmeet Singh Manku. Dipsea: una tabla hash distribuida modular Archivado el 10 de septiembre de 2004 en la Wayback Machine . Tesis de Doctorado (Universidad de Stanford), agosto de 2004.
- ^ Girdzijauskas, Šarūnas; Datta, Anwitaman; Aberer, Karl (1 de febrero de 2010). "Superposición estructurada para entornos heterogéneos" . Transacciones ACM en sistemas autónomos y adaptables . 5 (1): 1–25. doi : 10.1145 / 1671948.1671950 . ISSN 1556-4665 . S2CID 13218263 .
- ^ Forestiero, Agostino; Leonardi, Emilio; Mastroianni, Carlo; Meo, Michela (octubre de 2010). "Self-Chord: un marco P2P bioinspirado para sistemas distribuidos autoorganizados" . Transacciones IEEE / ACM sobre redes . 18 (5): 1651–1664. doi : 10.1109 / TNET.2010.2046745 . S2CID 14797120 .
- ^ Galuba, Wojciech; Girdzijauskas, Sarunas (2009), "Redes superpuestas entre pares: estructura, enrutamiento y mantenimiento", en LIU, LING; ÖZSU, M. TAMER (eds.), Encyclopedia of Database Systems , Springer US, págs. 2056–2061, doi : 10.1007 / 978-0-387-39940-9_1215 , ISBN 9780387399409
- ^ Girdzijauskas, Sarunas (2009). El diseño de superposiciones de igual a igual se superpone a una perspectiva de mundo pequeño . epfl.ch . EPFL.
- ^ El (Grado, diámetro) Problema de gráficos , Maite71.upc.es, archivada desde el original en 2012-02-17 , recuperado 2012-01-10
- ^ Gurmeet Singh Manku, Moni Naor y Udi Wieder. "Conozca al vecino de su vecino: el poder de la anticipación en redes P2P aleatorias" . Proc. STOC, 2004.
- ^ Ali Ghodsi . "Distributed k-ary System: Algorithms for Distributed Hash Tables" , archivado el 22 de mayo de 2007 en Wayback Machine . KTH-Real Instituto de Tecnología, 2006.
- ^ Castro, Miguel; Costa, Manuel; Rowstron, Antony (1 de enero de 2004). "¿Deberíamos construir Gnutella sobre una superposición estructurada?" (PDF) . Revisión de comunicación informática ACM SIGCOMM . 34 (1): 131. CiteSeerX 10.1.1.221.7892 . doi : 10.1145 / 972374.972397 . S2CID 6587291 .
- ^ Talia, Domenico; Trunfio, Paolo (diciembre de 2010). "Habilitación de consultas dinámicas sobre tablas hash distribuidas". Revista de Computación Paralela y Distribuida . 70 (12): 1254-1265. doi : 10.1016 / j.jpdc.2010.08.012 .
- ^ Baruch Awerbuch, Christian Scheideler. "Hacia una DHT escalable y robusta". 2006. doi : 10.1145 / 1148109.1148163
- ^ Maxwell Young; Aniket Kate; Ian Goldberg; Martin Karsten. "Práctica comunicación sólida en DHT que toleran un adversario bizantino" .
- ^ Natalya Fedotova; Giordano Orzetti; Luca Veltri; Alessandro Zaccagnini. "Acuerdo bizantino para la gestión de la reputación en redes peer-to-peer basadas en DHT". doi : 10.1109 / ICTEL.2008.4652638
- ^ Chris Lesniewski-Laas. "Un DHT de un salto a prueba de Sybil" (PDF) : 20. Cite journal requiere
|journal=
( ayuda ) - ^ Jonathan Kelner, Petar Maymounkov (2009). "Enrutamiento eléctrico y corte de flujo concurrente" . arXiv : 0909.2859 . Código Bibliográfico : 2009arXiv0909.2859K . Cite journal requiere
|journal=
( ayuda ) - ^ Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Estructuras de datos y algoritmos secuenciales y paralelos: la caja de herramientas básica . Springer International Publishing. ISBN 978-3-030-25208-3.
- ↑ Tribler wiki Archivado el 4 de diciembre de 2010 en Wayback Machine, recuperado en enero de 2010.
- ^ Preguntas frecuentes de Retroshare recuperadas en diciembre de 2011
enlaces externos
- Tablas hash distribuidas, parte 1 por Brandon Wiley.
- Distributed Hash Tables vincula la página de Carles Pairot sobre la investigación de DHT y P2P
- kademlia.scs.cs.nyu.edu Instantáneas de Archive.org de kademlia.scs.cs.nyu.edu
- Eng-Keong Lua; Crowcroft, Jon; Pias, Marcelo; Sharma, Ravi; Lim, Steve (2005). "Encuesta IEEE sobre esquemas de redes superpuestas". CiteSeerX 10.1.1.111.4197 : Cite journal requiere
|journal=
( ayuda ) cubriendo redes superpuestas descentralizadas no estructuradas y estructuradas, incluidas las DHT (Chord, Pastry, Tapestry y otras). - Medición principal de DHT en el Departamento de Ciencias de la Computación de la Universidad de Helsinki, Finlandia.