Acorde (de igual a igual)

En informática , Chord es un protocolo y algoritmo para una tabla hash distribuida punto a punto . Una tabla hash distribuida almacena pares clave-valor asignando claves a diferentes ordenadores (conocidos como "nodos"); cada nodo almacena los valores de todas las claves de las que es responsable. Chord especifica cómo se asignan las claves a los nodos y cómo un nodo puede descubrir el valor de una clave determinada localizando primero el nodo responsable de dicha clave.

Chord es uno de los cuatro protocolos originales de tabla hash distribuida , junto con CAN , Tapestry y Pastry . Fue presentado en 2001 por Ion Stoica , Robert Morris , David Karger , Frans Kaashoek y Hari Balakrishnan , y fue desarrollado en el MIT . ^{[ 1 ]} El artículo de Chord de 2001 ^{[ 1 ]} ganó un premio ACM SIGCOMM Test of Time en 2011. ^{[ 2 ]}

Investigaciones posteriores de Pamela Zave han demostrado que el protocolo Chord original (tal como se especifica en el documento SIGCOMM de 2001, ^{[ 1 ]} el informe técnico de 2001, ^{[ 3 ]} el documento PODC de 2002, ^{[ 4 ]} y el documento TON de 2003 ^{[ 5 ]} ) puede desordenar el anillo, producir varios anillos y romper el anillo. ^{[ 6 ]} Una versión corregida del protocolo evita estos errores, sin imponer una sobrecarga adicional. ^{[ 7 ]}

A los nodos y claves se les asigna un${\displaystyle m}$Identificador de bits mediante hash consistente . El algoritmo SHA-1 es la función de hash base para el hash consistente. El hash consistente es fundamental para la robustez y el rendimiento de Chord porque tanto las claves como los nodos (de hecho, sus direcciones IP ) se distribuyen uniformemente en el mismo espacio de identificadores con una posibilidad insignificante de colisión . Por lo tanto, también permite que los nodos se unan y abandonen la red sin interrupciones. En el protocolo, el término nodo se utiliza para referirse tanto al nodo en sí como a su identificador (ID) sin ambigüedad. Lo mismo ocurre con el término clave .

Utilizando el protocolo de búsqueda Chord, los nodos y las claves se organizan en un círculo de identificadores que tiene como máximo${\displaystyle 2^{m}}$nodos, que van desde${\displaystyle 0}$a${\displaystyle 2^{m}-1}$. (${\displaystyle m}$(debería ser lo suficientemente grande para evitar colisiones). Algunos de estos nodos se asignarán a máquinas o claves, mientras que otros (la mayoría) estarán vacíos.

Cada nodo tiene un sucesor y un predecesor . El sucesor de un nodo es el siguiente nodo en el círculo de identificadores en sentido horario. El predecesor es en sentido antihorario. Si hay un nodo para cada ID posible, el sucesor del nodo 0 es el nodo 1, y el predecesor del nodo 0 es el nodo 2.${\displaystyle 2^{m}-1}$Sin embargo, normalmente existen "huecos" en la secuencia. Por ejemplo, el sucesor del nodo 153 puede ser el nodo 167 (y los nodos del 154 al 166 no existen); en este caso, el predecesor del nodo 167 será el nodo 153.

El concepto de sucesor también se puede utilizar para las claves. El nodo sucesor de una clave${\displaystyle k}$es el primer nodo cuyo ID es igual a${\displaystyle k}$o sigue${\displaystyle k}$en el círculo identificador, denotado por${\displaystyle sucesor(k)}$Cada clave se asigna a (se almacena en) su nodo sucesor, por lo que buscar una clave${\displaystyle k}$es consultar${\displaystyle sucesor(k)}$.

Dado que el sucesor (o predecesor) de un nodo puede desaparecer de la red (debido a una falla o salida), cada nodo registra un arco de${\displaystyle 2r+1}$nodos en medio de los cuales se encuentra, es decir, la lista de${\displaystyle r}$nodos que lo preceden y${\displaystyle r}$nodos que le siguen. Esta lista da como resultado una alta probabilidad de que un nodo pueda localizar correctamente a su sucesor o predecesor, incluso si la red en cuestión sufre una alta tasa de fallos.

• Replicación cooperativa: Mecanismo de equilibrio de carga mediante una red local que aloja información disponible para ordenadores fuera de la red local. Este sistema podría permitir a los desarrolladores equilibrar la carga entre varios ordenadores en lugar de un servidor central para garantizar la disponibilidad de su producto.
• Almacenamiento compartido en el tiempo: En una red, una vez que un ordenador se conecta, sus datos disponibles se distribuyen por toda la red para su recuperación cuando se desconecta. Asimismo, los datos de otros ordenadores se envían al ordenador en cuestión para su recuperación sin conexión cuando ya no están conectados a la red. Esto se aplica principalmente a nodos que no pueden conectarse a la red de forma permanente.
• Índices distribuidos: Recuperación de archivos a través de la red dentro de una base de datos con capacidad de búsqueda. Por ejemplo, clientes de transferencia de archivos P2P.
• Búsquedas combinatorias a gran escala: Las claves son soluciones candidatas a un problema y cada clave se asigna al nodo, o computadora, responsable de evaluarlas como solución o no. Por ejemplo, descifrado de códigos.
• También se utiliza en redes de sensores inalámbricos para mayor fiabilidad ^{[ 8 ].}

Con alta probabilidad, contactos de cuerda${\displaystyle O(\log N)}$nodos para encontrar un sucesor en un${\displaystyle N}$-red de nodos.

Supongamos que el nodo${\displaystyle n}$desea encontrar al sucesor de la clave${\displaystyle k}$. Dejar${\displaystyle p}$ser el predecesor de${\displaystyle k}$. Deseamos encontrar un límite superior para el número de pasos que se necesitan para que un mensaje sea enrutado desde${\displaystyle n}$a${\displaystyle p}$Nodo${\displaystyle n}$examinará su tabla de dedos y enrutará la solicitud al predecesor más cercano de${\displaystyle k}$que lo tiene. Llama a este nodo${\displaystyle f}$. Si${\displaystyle f}$es el${\displaystyle i^{th}}$entrada en${\displaystyle n}$mesa de dedos, luego ambos${\displaystyle f}$y${\displaystyle p}$están a distancias entre${\displaystyle 2^{i-1}}$y${\displaystyle 2^{i}}$de${\displaystyle n}$a lo largo del círculo identificador. Por lo tanto, la distancia entre${\displaystyle f}$y${\displaystyle p}$a lo largo de este círculo es como máximo${\displaystyle 2^{i-1}}$. Por lo tanto, la distancia desde${\displaystyle f}$a${\displaystyle p}$es menor que la distancia desde${\displaystyle n}$a${\displaystyle f}$: la nueva distancia a${\displaystyle p}$es como máximo la mitad de la distancia inicial.

Este proceso de reducir a la mitad la distancia restante se repite, por lo que después${\displaystyle t}$pasos, la distancia restante hasta${\displaystyle p}$es como máximo${\displaystyle 2^{m}/2^{t}}$; en particular, después${\displaystyle \log N}$pasos, la distancia restante es como máximo${\displaystyle 2^{m}/N}$Debido a que los nodos se distribuyen uniformemente al azar a lo largo del círculo identificador, el número esperado de nodos que caen dentro de un intervalo de esta longitud es 1, y con alta probabilidad, hay menos de${\displaystyle \log N}$tales nodos. Debido a que el mensaje siempre avanza al menos un nodo, tarda como máximo${\displaystyle \log N}$pasos para que un mensaje recorra esta distancia restante. El tiempo total de enrutamiento esperado es, por lo tanto,${\displaystyle O(\log N)}$.

Si Chord realiza un seguimiento de${\displaystyle r=O(\log N)}$predecesores/sucesores, entonces con alta probabilidad, si cada nodo tiene una probabilidad de 1/4 de fallar, find_successor (ver más abajo) y find_predecessor (ver más abajo) devolverán los nodos correctos

Simplemente, la probabilidad de que todos${\displaystyle r}$Los nodos fallan es${\displaystyle \left({{1} \over {4}}\right)^{r}=O\left({{1} \over {N}}\right)}$, lo cual es una probabilidad baja; por lo tanto, con alta probabilidad al menos uno de ellos está vivo y el nodo tendrá el puntero correcto.

Definiciones de pseudocódigo

dedo[k]

primer nodo que tiene éxito${\displaystyle (n+2^{k-1}){\mbox{ mod }}2^{m},1\leq k\leq m}$

sucesor

el siguiente nodo desde el nodo en cuestión en el anillo de identificadores

predecesor

el nodo anterior al nodo en cuestión en el anillo de identificadores

A continuación se muestra el pseudocódigo para encontrar el nodo sucesor de un ID:

// Pedir al nodo n que encuentre el sucesor de id n.find_successor(id) // Sí, debería ser un corchete de cierre para que coincida con el paréntesis de apertura. // Es un intervalo semicerrado. if id ∈ (n, successor] then return successor else // reenviar la consulta alrededor del círculo n0 := nodo_precedente_más_cercano(id) devolver n0.find_successor(id) // busca en la tabla local el predecesor más alto de id n.closest_preceding_node(id) para i = m hasta 1 hacer si (finger[i] ∈ (n, id)) entonces devolver dedo[i] devolver n

El pseudocódigo para estabilizar el anillo/círculo de cuerdas después de las uniones y salidas de nodos es el siguiente:

// crea un nuevo anillo de acordes. n.create() predecesor := nulo sucesor := n // Une un anillo de cuerdas que contiene el nodo n'. n.join(n') predecesor := nulo sucesor := n'.find_successor(n) // Se llama periódicamente. n pregunta al sucesor // sobre su predecesor, verifica si el sucesor inmediato de n // es consistente y le informa al sucesor sobre n. n.stabilize() x = sucesor.predecesor si x ∈ (n, sucesor) entonces sucesor := x sucesor.notificar(n) // n' piensa que podría ser nuestro predecesor. n.notify(n') si el predecesor es nulo o n' ∈ (predecesor, n) entonces predecesor := n' // Se llama periódicamente. Actualiza las entradas de la tabla de dedos. // A continuación, almacena el índice del dedo a corregir. n.fix_fingers() siguiente := siguiente + 1 si siguiente > m entonces siguiente := 1 finger[next] := find_successor(n+2 next-1 ); // Se llama periódicamente. Comprueba si el predecesor ha fallado. n.check_predecessor() Si el predecesor ha fallado, entonces el predecesor es nulo.

• Kademlia
• Koorde
• OverSim : el marco de simulación de superposición
• SimGrid : un conjunto de herramientas para la simulación de aplicaciones distribuidas.

• El Proyecto Chord (redireccionar desde: http://pdos.lcs.mit.edu/chord/ )
• Open Chord – Una implementación Java de código abierto
• Sin cables: otra implementación de Java de código abierto
• jDHTUQ: una implementación Java de código abierto. API para generalizar la implementación de sistemas DHT peer-to-peer. Contiene una interfaz gráfica de usuario en modo estructura de datos.