Hispanopedia Wiki
Articulo de referencia

Tabla hash distribuida

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 una DHT, y ...

Hispanopedia WikiContenido en espanolLectura gratuita

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 una DHT, y cualquier nodo participante puede recuperar eficientemente el valor asociado a una clave determinada. La principal ventaja de una DHT es que se pueden añadir o eliminar nodos con un mínimo esfuerzo en la redistribución de claves. [ 1 ] Las claves son identificadores únicos que se corresponden con valores específicos , que a su vez pueden ser cualquier cosa, desde direcciones hasta documentos o datos arbitrarios . [ 2 ] La responsabilidad de mantener la correspondencia entre claves y valores se distribuye entre los nodos, de forma que un cambio en el conjunto de participantes provoque una mínima interrupción. Esto permite que una DHT escale a un número extremadamente grande de nodos y gestione la llegada, salida y fallos continuos de nodos.

Las DHT conforman una infraestructura que puede utilizarse para construir 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 intercambio de archivos y distribución de contenido entre pares . Entre las redes distribuidas más destacadas que utilizan DHT se encuentran el rastreador distribuido de BitTorrent , la red Kad , la botnet Storm , el mensajero instantáneo Tox , Freenet , el motor de búsqueda YaCy y el Sistema de Archivos Interplanetario .

Tablas hash distribuidas

Historia

La investigación sobre DHT se originó, en parte, motivada por sistemas peer-to-peer (P2P) como Freenet , Gnutella , BitTorrent y Napster , que aprovechaban los recursos distribuidos en Internet para ofrecer una única aplicación útil. En particular, aprovechaban el mayor ancho de banda y la capacidad del disco duro para proporcionar un servicio de intercambio de archivos. [ 3 ]

Estos sistemas diferían en la forma en que localizaban los datos ofrecidos por sus pares. Napster, el primer sistema de distribución 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 realizaba búsquedas y remitía las consultas a los nodos que contenían los resultados. Este componente central dejaba al sistema vulnerable a ataques y demandas.

Gnutella y redes similares adoptaron un modelo de inundación de consultas ; en esencia, cada búsqueda generaba un mensaje que se transmitía a todas las máquinas de la red. Si bien este método evitaba un único punto de fallo , era significativamente menos eficiente que Napster. Las versiones posteriores de los clientes de Gnutella adoptaron un modelo de consulta dinámica que mejoró enormemente la eficiencia. [ 4 ] 

Freenet es totalmente distribuido, pero emplea un enrutamiento heurístico basado en claves en el que cada archivo se asocia 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 hacia dicho clúster sin necesidad de visitar muchos pares. [ 5 ] Sin embargo, Freenet no garantiza que se encuentren 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. Una desventaja es que, al igual que Freenet, las DHT solo admiten directamente la búsqueda de coincidencia exacta, en lugar de la búsqueda por palabra 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. [ 6 ]

En 2001, cuatro sistemas —CAN , [ 7 ] Chord , [ 8 ] Pastry y Tapestry— llamaron la atención sobre las DHT. Un proyecto llamado Infrastructure for Resilient Internet Systems (Iris) fue financiado con una subvención de 12 millones de dólares de la Fundación Nacional de Ciencias de los Estados Unidos en 2002. [ 9 ] Entre los investigadores se encontraban Sylvia Ratnasamy , Ion Stoica , Hari Balakrishnan y Scott Shenker . [ 10 ] Fuera del ámbito académico, la tecnología DHT se ha adoptado como un componente de BitTorrent y en proyectos de PlanetLab como la Coral Content Distribution Network. [ 11 ]

Propiedades

Las DHT se caracterizan por enfatizar las siguientes propiedades:

  • Autonomía y descentralización : Los nodos forman el sistema de forma colectiva, sin ninguna coordinación central.
  • Tolerancia a fallos : El sistema debe ser fiable (en cierto sentido) incluso con nodos que se unen, se van y fallan continuamente. [ 12 ]
  • Escalabilidad : El sistema debe funcionar de manera eficiente incluso con miles o millones de nodos.

Una técnica clave utilizada para lograr estos objetivos es que cada nodo necesita coordinarse con solo unos pocos otros nodos en el sistema —generalmente , O (log n ) de los n participantes (ver más abajo) — de modo que solo se necesita realizar una cantidad limitada de trabajo para cada cambio en la membresía.

Algunos diseños de DHT buscan ser seguros contra participantes maliciosos [ 13 ] y permitir que los participantes permanezcan anónimos , aunque esto es menos común que en muchos otros sistemas peer-to-peer (especialmente de intercambio de archivos ); véase P2P anónimo .

Estructura

La estructura de una DHT se puede descomponer en varios componentes principales. [ 14 ] [ 15 ] La base es un espacio de claves abstracto , como el conjunto de cadenas de 160 bits . Un esquema de particionamiento del espacio de claves divide la propiedad de este espacio de claves entre los nodos participantes. Una red superpuesta conecta los nodos, permitiéndoles encontrar al propietario de cualquier clave dada en el espacio de claves.

Una vez que estos componentes estén en su lugar, un uso típico de la DHT para almacenamiento y recuperación podría proceder de la siguiente manera. Supongamos 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 la DHT, se genera el hash SHA-1 del nombre de archivo , produciendo una clave k de 160 bits , y se envía un mensaje put ( k, datos ) a cualquier nodo que participe en la DHT. El mensaje se reenvía de nodo en nodo 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 entonces almacena la clave y los datos. Cualquier otro cliente puede entonces recuperar el contenido del archivo nuevamente aplicando el hash del nombre de archivo para producir k y solicitando a cualquier nodo de la 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 .

A continuación se describen los componentes de la partición del espacio de claves y de la red superpuesta, con el objetivo de plasmar las ideas principales comunes a la mayoría de las DHT; muchos diseños difieren en los detalles.

Particionamiento del espacio de claves

La mayoría de las DHT utilizan alguna variante de hash consistente o hash de encuentro para asignar claves a nodos. Ambos 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 comparten la propiedad esencial de que la eliminación o adición de un nodo solo modifica el conjunto de claves propiedad de los nodos con identificadores adyacentes, sin afectar a los demás nodos. Esto contrasta con una tabla hash tradicional , donde la adición o eliminación de un cubo provoca la reasignación de casi todo el espacio de claves. Dado que cualquier cambio de propiedad suele implicar un movimiento intensivo de ancho de banda de los objetos almacenados en la DHT de un nodo a otro, es necesario minimizar dicha reorganización para soportar de forma eficiente altas tasas de rotación (lanzamiento y fallo de nodos).

Hashing consistente

El hash consistente emplea una funciónδ(k1,k2){\ Displaystyle \ delta (k_ {1}, k_ {2})}que define una noción abstracta de la distancia entre las teclask1{\displaystyle k_{1}}yk2{\displaystyle k_{2}}, que no está relacionado con la distancia geográfica ni la latencia de la red . A cada nodo se le asigna una única clave llamada identificador (ID). Un nodo con IDiincógnita{\displaystyle i_{x}}posee todas las llaveskmetro{\displaystyle k_{m}}para quéiincógnita{\displaystyle i_{x}}es la identificación más cercana, medida segúnδ(kmetro,iincógnita){\displaystyle \delta (k_{m},i_{x})}.

Por ejemplo, Chord DHT utiliza un hash consistente, que trata a los nodos como puntos en un círculo, yδ(k1,k2){\displaystyle \delta (k_{1},k_{2})}es la distancia viajando en el sentido de las agujas del reloj alrededor del círculo desdek1{\displaystyle k_{1}}ak2{\displaystyle k_{2}}. Por lo tanto, el espacio de claves circular se divide en segmentos contiguos cuyos puntos finales son los identificadores de nodo. Sii1{\displaystyle i_{1}}yi2{\displaystyle i_{2}}son dos identificadores adyacentes, con una distancia más corta en el sentido de las agujas del reloj desdei1{\displaystyle i_{1}}ai2{\displaystyle i_{2}}, entonces el nodo con IDi2{\displaystyle i_{2}}posee todas las llaves que caen entrei1{\displaystyle i_{1}}yi2{\displaystyle i_{2}}.

Hashing de encuentro

En el hash de encuentro, también llamado hash de peso aleatorio más alto (HRW), todos los clientes utilizan la misma función hash.h(){\displaystyle h()}(elegido con antelación) 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 una 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 IDSincógnita{\displaystyle S_{x}}posee todas las llaveskmetro{\displaystyle k_{m}}para el cual el peso hashh(Sincógnita,kmetro){\displaystyle h(S_{x},k_{m})}es mayor que el peso hash de cualquier otro nodo para esa clave.

Hashing que preserva la localidad

El hash que preserva la localidad garantiza que se asignen claves similares a objetos similares. Esto puede permitir una ejecución más eficiente de las consultas de rango; sin embargo, a diferencia del uso de hash consistente, no hay 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 [ 16 ] abordan estos problemas. Self-Chord desacopla las claves de objeto de los ID de los pares y ordena las claves a lo largo del anillo con un enfoque estadístico basado en el paradigma de inteligencia de enjambre . [ 17 ] La ​​ordenació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 de mundo pequeño navegable basada en el muestreo de paseo aleatorio, lo que también garantiza un tiempo de búsqueda logarítmico.

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. [ 18 ] Un nodo elige a sus vecinos de acuerdo con una estructura determinada, 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 un 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 voraz (que no es necesariamente óptimo globalmente): en cada paso, reenviar el mensaje al vecino cuyo ID está más cerca de k . Cuando no hay 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 llama 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 la ruta) sea bajo, para que las solicitudes se completen rápidamente; y que el número máximo de vecinos de cualquier nodo ( grado máximo del nodo ) sea bajo, para que la sobrecarga de mantenimiento no sea excesiva. Por supuesto, tener rutas más cortas requiere un grado máximo mayor . 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 la DHT, utilizando la notación Big O :

La opción más común,O(registro⁡norte){\displaystyle O(\log n)}La relación grado/longitud de ruta no es óptima en términos de compensación entre grado y longitud de ruta, pero estas topologías suelen permitir mayor flexibilidad en la elección de vecinos. Muchas DHT utilizan esa flexibilidad para seleccionar vecinos que estén cerca en términos de latencia en la red física subyacente. En general, todas las DHT construyen topologías de red de mundo pequeño navegables, que compensan la longitud de ruta con el grado de la red. [ 19 ]

La longitud máxima de la ruta está estrechamente relacionada con el diámetro : el número máximo de saltos en cualquier camino más corto entre nodos. Claramente, la longitud de la 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 relación grado/diámetro [ 20 ] que es fundamental en la teoría de grafos . La longitud de la ruta puede ser mayor que el diámetro, ya que el algoritmo de enrutamiento voraz puede no encontrar los caminos más cortos. [ 21 ]

Algoritmos para redes superpuestas

Además del enrutamiento, existen muchos algoritmos que aprovechan la estructura de la red superpuesta para enviar un mensaje a todos los nodos, o a un subconjunto de nodos, en una DHT. [ 22 ] Estos algoritmos son utilizados por aplicaciones para realizar multidifusión superpuesta , consultas de rango o para recopilar estadísticas. Dos sistemas que se basan en este enfoque son Structella, [ 23 ] que implementa inundación y recorridos aleatorios en una superposición Pastry, y DQ-DHT, que implementa un algoritmo de búsqueda de consulta dinámica sobre una red Chord. [ 24 ]

Seguridad

Debido a la descentralización, la tolerancia a fallos y la escalabilidad de las DHT, estas son inherentemente más resistentes frente a un atacante hostil que un sistema centralizado.

Es factible desarrollar sistemas abiertos para el almacenamiento distribuido de datos que sean robustos frente a ataques masivos hostiles. [ 25 ]

Un sistema DHT diseñado cuidadosamente para tener tolerancia a fallos bizantinos puede defenderse contra una vulnerabilidad de seguridad conocida como ataque Sybil , que afecta a la mayoría de los diseños DHT actuales. [ 26 ] [ 27 ] Whanau es un DHT diseñado para ser resistente a los ataques Sybil. [ 28 ]

Petar Maymounkov, uno de los autores originales de Kademlia , propuso una forma de sortear la vulnerabilidad al ataque Sybil mediante la incorporación de relaciones de confianza social en el diseño del sistema. [ 29 ] El nuevo sistema, con nombre en clave Tonika o también conocido por su nombre de dominio como 5ttt, se basa en un algoritmo de enrutamiento eléctrico y fue desarrollado en colaboración con el matemático Jonathan Kelner. [ 30 ] Maymounkov ha emprendido un esfuerzo integral de implementación de este nuevo sistema. Sin embargo, la investigación sobre defensas efectivas contra los ataques Sybil se considera generalmente una cuestión abierta, y cada año se proponen diversas defensas potenciales en las principales conferencias de investigación en seguridad. [ 31 ]

Implementaciones

Las diferencias más notables que se encuentran en los casos prácticos de implementaciones de DHT incluyen al menos las siguientes:

  • El espacio de direcciones es un parámetro de la DHT. Varias DHT reales utilizan un espacio de claves de 128 o 160 bits.
  • Algunas DHT del mundo real utilizan funciones hash distintas de SHA-1 .
  • En la práctica, la clave k podría ser un hash del contenido de un archivo en lugar de un hash del nombre del archivo para proporcionar un 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 distintos tipos. Por ejemplo, la clave k podría ser el ID del nodo y los datos asociados podrían describir cómo contactar con este nodo. Esto permite la publicación de información de presencia y se utiliza a menudo en aplicaciones de mensajería instantánea, etc. En el caso más sencillo, el ID es simplemente un número aleatorio que se utiliza directamente como clave k (por lo que en una DHT de 160 bits, el ID será un número de 160 bits, generalmente elegido al azar). En algunas DHT, la publicación de los ID de los nodos también se utiliza para optimizar las operaciones de la DHT.
  • Se puede añadir redundancia para mejorar la fiabilidad. El par clave-valor (k, datos) puede almacenarse en más de un nodo correspondiente a la clave. Normalmente, en lugar de seleccionar un solo nodo, los algoritmos DHT del mundo real seleccionan i nodos adecuados, donde i es un parámetro específico de la implementación de la DHT. En algunos diseños de DHT, los nodos acuerdan gestionar un determinado rango de espacio de claves, cuyo tamaño puede elegirse dinámicamente, en lugar de estar codificado de forma fija.
  • Algunas DHT avanzadas como Kademlia realizan búsquedas iterativas a través de la DHT para seleccionar un conjunto de nodos adecuados y enviar mensajes put(k, data) solo a esos nodos, reduciendo así drásticamente el tráfico innecesario, 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 toda la DHT, lo que reduce el reenvío innecesario. En dichas DHT, el reenvío de mensajes put(k, data) solo puede ocurrir como parte de un algoritmo de autorreparación: si un nodo de destino recibe un mensaje put(k, data) , pero cree que k está fuera de su rango manejado y se conoce un nodo más cercano (en términos del espacio de claves de la DHT), el mensaje se reenvía a ese nodo. De lo contrario, los datos se indexan localmente. Esto conduce a un comportamiento de DHT que se autoequilibra en cierta medida. Por supuesto, dicho algoritmo requiere que los nodos publiquen sus datos de presencia en la DHT para que se puedan realizar las búsquedas iterativas.
  • Dado que en la mayoría de las máquinas enviar mensajes es mucho más costoso que acceder a la tabla hash local, tiene sentido agrupar varios 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 primero ordena su lote local por el identificador del nodo responsable de la operación. Usando el algoritmo de ordenación por cubetas , esto se puede hacer en O(b + n) , donde n es el número de nodos en la DHT. Cuando hay varias operaciones que acceden a la misma clave dentro de un lote, este se condensa antes de enviarse. Por ejemplo, varias búsquedas de la misma clave se pueden reducir a una, o varios incrementos se pueden reducir a una sola operación de suma. Esta reducción se puede implementar con la ayuda de una tabla hash local temporal. Finalmente, las operaciones se envían a los nodos respectivos. [ 32 ]

Ejemplos

Protocolos e implementaciones de DHT

Aplicaciones que utilizan DHT

Véase también

Referencias

  1. ^ Hota, Chittaranjan; Srimani, Pradip K. (11 de enero de 2013). Computación distribuida y tecnología de Internet: Novena Conferencia Internacional, ICDCIT 2013, Bhubaneswar, India, 5 al 8 de febrero de 2013, Actas . Saltador. ISBN 978-3-642-36071-8.
  2. ↑ Stoica, I. ; Morris, R.; Karger, D. ; Kaashoek, MF; Balakrishnan, H. (2001). "Chord: Un servicio de búsqueda peer-to-peer escalable para aplicaciones de Internet" (PDF) . ACM SIGCOMM Computer Communication Review . 31 (4): 149. doi : 10.1145/964723.383071 . Archivado (PDF) del original el 07-07-2023 . Recuperado el 18-09-2018 . Un valor puede ser una dirección, un documento o un elemento de datos arbitrario.
  3. ↑ Liz, Crowcroft; et al. (2005). "Un estudio y comparación de esquemas de redes superpuestas peer-to-peer" ( PDF) . IEEE Communications Surveys & Tutorials . 7 (2): 72– 93. CiteSeerX 10.1.1.109.6124 . doi : 10.1109/COMST.2005.1610546 . S2CID 7971188. Archivado (PDF) del original el 05-10-2023 . Recuperado el 24-09-2019 .   
  4. ↑ Richter, Stevenson; et al. (2009). "Análisis del impacto de los modelos de consulta dinámica en las relaciones cliente-servidor". Tendencias en la computación moderna : 682–701 . 
  5. ↑ Buscando en un mundo pequeño, capítulos 1 y 2 (PDF) , archivado del original (PDF) el 16 de marzo de 2012 , consultado el 10 de enero de 2012.
  6. ↑ "Sección 5.2.2" (PDF) , Un sistema distribuido y descentralizado de almacenamiento y recuperación de información , archivado del original (PDF) el 16 de marzo de 2012 , recuperado el 10 de enero de 2012.
  7. ↑ Ratnasamy, Sylvia; Francis, Paul; Handley, Mark; Karp, Richard; Shenker, Scott (27 de agosto de 2001). "Una red escalable direccionable por contenido" . SIGCOMM Comput. Commun. Rev. 31 ( 4): 161– 172. doi : 10.1145/964723.383072 . ISSN 0146-4833 . 
  8. ↑ Hari Balakrishnan , M. Frans Kaashoek , David Karger, Robert Morris e Ion Stoica. Búsqueda de datos en sistemas P2P. Archivado el 19 de mayo de 2016 en Wayback Machine . En Communications of the ACM , febrero de 2003.
  9. ↑ David Cohen (1 de octubre de 2002). "Nueva red P2P financiada por el gobierno de EE. UU." . New Scientist . Archivado del original el 6 de abril de 2008 . Consultado el 10 de noviembre de 2013 .
  10. ↑ "MIT, Berkeley, ICSI, NYU y Rice lanzan el proyecto IRIS" . Comunicado de prensa . MIT. 25 de septiembre de 2002. Archivado del original el 26 de septiembre de 2015. Consultado el 10 de noviembre de 2013 .
  11. ↑ "Democratizando la publicación de contenido con Coral" (PDF) . NSDI . 4. 2004. Consultado el 1 de mayo de 2024 .
  12. ↑ R Mokadem, A Hameurlain y AM Tjoa. Servicio de descubrimiento de recursos minimizando la sobrecarga de mantenimiento en sistemas DHT jerárquicos. Archivado el 9 de agosto de 2022 en Wayback Machine . Proc. iiWas, 2010.
  13. ↑ Guido Urdaneta, Guillaume Pierre y Maarten van Steen. Un estudio de las técnicas de seguridad de DHT. Archivado el 1 de junio de 2023 en Wayback Machine . ACM Computing Surveys 43(2), enero de 2011.
  14. ↑ Moni Naor y Udi Wieder. Nuevas arquitecturas para aplicaciones P2P: el enfoque continuo-discreto. Archivado el 9 de diciembre de 2019 en Wayback Machine . Actas de la SPAA, 2003.
  15. ↑ Gurmeet Singh Manku. Dipsea: Una tabla hash distribuida modular. Archivado el 10 de septiembre de 2004 en Wayback Machine . Tesis doctoral (Universidad de Stanford), agosto de 2004.
  16. ↑ Girdzijauskas, Šarūnas; Datta, Anwitaman; Aberer, Karl (2010-02-01). "Superposición estructurada para entornos heterogéneos" . ACM Transactions on Autonomous and Adaptive Systems . 5 (1): 1– 25. doi : 10.1145/1671948.1671950 . ISSN 1556-4665 . S2CID 13218263. Archivado del original el 12 de julio de 2020. Recuperado el 12 de marzo de 2020 .  
  17. ↑ Forestiero, Agostino; Leonardi, Emilio; Mastroianni, Carlo; Meo, Michela (octubre de 2010). "Self-Chord: un marco P2P bioinspirado para sistemas distribuidos autoorganizados" . IEEE/ACM Transactions on Networking . 18 (5): 1651– 1664. Bibcode : 2010ITNet..18.1651F . doi : 10.1109/TNET.2010.2046745 . S2CID 14797120. Archivado del original el 1 de julio de 2012. Recuperado el 28 de julio de 2019 . 
  18. ↑ Galuba, Wojciech; Girdzijauskas, Sarunas (2009), "Peer to Peer Overlay Networks: Structure, Routing and Maintenance", en LIU, LING ; ÖZSU, M. TAMER (eds.), Encyclopedia of Database Systems , Springer US, pp. 2056–2061 , doi : 10.1007/978-0-387-39940-9_1215 , ISBN  9780387399409
  19. ↑ Girdzijauskas, Sarunas (2009). Diseño de superposiciones peer-to-peer: una perspectiva de mundo pequeño . epfl.ch (Tesis). EPFL. doi : 10.5075/epfl-thesis-4327 . Archivado del original el 3 de marzo de 2020. Consultado el 11 de noviembre de 2019 .
  20. ↑ El problema (grado, diámetro) para grafos , Maite71.upc.es, archivado del original el 17-02-2012 , recuperado el 10-01-2012
  21. ↑ Gurmeet Singh Manku, Moni Naor y Udi Wieder. "Conoce al vecino de tu vecino: el poder de la anticipación en redes P2P aleatorias". Archivado el 20 de abril de 2008 en Wayback Machine . Actas de STOC, 2004.
  22. ↑ Ali Ghodsi (22 de mayo de 2007). "Sistema k-ario distribuido: algoritmos para tablas hash distribuidas" . Archivado del original el 22 de mayo de 2007.KTH-Instituto Real de Tecnología, 2006.
  23. ↑ Castro, Miguel; Costa, Manuel; Rowstron, Antony (1 de enero de 2004). "¿Deberíamos construir Gnutella sobre una superposición estructurada?" ( PDF) . ACM SIGCOMM Computer Communication Review . 34 (1): 131. CiteSeerX 10.1.1.221.7892 . doi : 10.1145/972374.972397 . S2CID 6587291. Archivado (PDF) del original el 14 de febrero de 2021. Recuperado el 25 de septiembre de 2019 .  
  24. ↑ Talia, Domenico; Trunfio, Paolo (diciembre de 2010). "Habilitación de consultas dinámicas sobre tablas hash distribuidas". Journal of Parallel and Distributed Computing . 70 (12): 1254– 1265. doi : 10.1016/j.jpdc.2010.08.012 .
  25. ↑ Baruch Awerbuch, Christian Scheideler. "Hacia una DHT escalable y robusta". 2006. doi : 10.1145/1148109.1148163
  26. ↑ Maxwell Young; Aniket Kate; Ian Goldberg; Martin Karsten. "Comunicación práctica y robusta en DHT que toleran un adversario bizantino" Archivado el 22 de julio de 2016 en Wayback Machine .
  27. ↑ Natalia Fedotova; Giordano Orzetti; Luca Veltri; Alejandro 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
  28. ↑ Whanau: Una tabla hash distribuida a prueba de ataques Sybil https://pdos.csail.mit.edu/papers/whanau-nsdi10.pdf Archivado el 25/01/2022 en Wayback Machine
  29. ↑ Lesniewski-Laas, Chris (1 de abril de 2008). "Una DHT de un salto a prueba de Sybil" . Actas del 1er Taller sobre Sistemas de Redes Sociales . SocialNets '08. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 19–24 . doi : 10.1145/1435497.1435501 . ISBN  978-1-60558-124-8.
  30. ↑ Kelner, Jonathan; Maymounkov, Petar (22 de julio de 2011). "Enrutamiento eléctrico y corte de flujo concurrente" . Theoretical Computer Science . Algorithms and Computation. 412 (32): 4123– 4135. doi : 10.1016/j.tcs.2010.06.013 . hdl : 1721.1/71604 . ISSN 0304-3975 . 
  31. ↑ "Los ataques y defensas de Sybil: un estudio" . 22 de diciembre de 2013.
  32. ↑ Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Algoritmos y estructuras de datos secuenciales y paralelos: la caja de herramientas básica . Springer International Publishing. ISBN 978-3-030-25208-3Archivado del original el 17 de agosto de 2021. Consultado el 22 de enero de 2020 .
  33. ↑ Wiki de Tribler Archivada el 4 de diciembre de 2010 en Wayback Machine , recuperada en enero de 2010.
  34. ↑ Preguntas frecuentes de Retroshare Archivadas el 17/07/2013 en Wayback Machine (recuperadas en diciembre de 2011)
  • Tablas hash distribuidas, Parte 1, por Brandon Wiley.
  • Tablas hash distribuidas enlaza con la página de Carles Pairot sobre investigación en 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 : que abarca redes superpuestas descentralizadas, tanto estructuradas como no estructuradas, incluidas las DHT (Chord, Pastry, Tapestry y otras).
  • Medición DHT principal en el Departamento de Ciencias de la Computación de la Universidad de Helsinki, Finlandia.
Obtenido de " https://en.wikipedia.org/w/index.php?title=Distributed_hash_table&oldid=1357890929 "
Lecturas relacionadas
6 articulos
Computación distribuidaComputación distribuidaLa computación distribuida es un campo de la informática que estudia los sistemas distribuidos , definidos como sistemas informáticos cuyos compone...Tabla hashTabla hashEn informática , una tabla hash es una estructura de datos que implementa una matriz asociativa , también llamada diccionario o simplemente mapa; u...Par nombre-valorPar nombre-valorUn par nombre-valor , también conocido como par atributo-valor , par clave-valor o par campo-valor , es una representación de datos fundamental en ...Nodo (redes)Nodo (redes)En las redes de telecomunicaciones , un nodo ( del latín nodus , 'nudo') es un punto de redistribución o un punto final de comunicación .Documento electrónicoDocumento electrónicoUn documento electrónico es un documento que puede enviarse por medios no físicos, como télex , correo electrónico e Internet . [1] Originalmente, ...Datos (informática)Datos (informática)En informática , los datos (tratados como singular, plural o como sustantivo colectivo ) son cualquier secuencia de uno o más símbolos ; dato es un...