Chord

Chord es un protocolo y algoritmo para la implementación de tablas de hash distribuidas. A la tablas de hash construidas según esta forma se las llama tablas hash distribuidas de Chord o DHT Chord. El sistema es sencillo, escalable y está diseñado para funcionar en redes descentralizadas P2P (sin nodos privilegiados).

Un problema fundamental al que se enfrentan las aplicaciones P2P es el de localizar de manera eficiente el nodo que almacena un elemento de datos en particular. Para ello existen diferentes mecanismos como Chord, un protocolo de búsqueda distribuida que aborda este problema. Chord proporciona soporte para una sola operación: dado una clave, asigna la clave a un nodo. La ubicación de los datos puede ser fácilmente implementada sobre Chord asociando una clave para cada elemento, y almacenar el par de clave / elemento en cada nodo. Chord se adapta de manera eficiente a medida que los nodos se unen y dejan el sistema, y ​​puede responder consultas incluso si el sistema está continuamente cambiando.

Introducción

Esquema red Chord

Este protocolo permite tener un conjunto de nodos identificados con un conjunto de bits. Por ejemplo, si usamos un conjunto de 6 bits como identificador, pues podemos identificar hasta 64 nodos en nuestra red P2P, porque 2^6 es 64. Los identificadores irían desde 000000 (0) hasta 111111 (63). Para identificar al nodo 49 por ejemplo sería: 110001 (49)

Cada nodo, además, puede tener asociado a una o varias claves o llaves. Estas claves, se representan con el mismo número de bits que el identificador de los nodos. En nuestro caso, las llaves se identificarían también con un conjunto de 6 bits. Un nodo no puede tener asociado claves cuya representación o id sea mayor que la del propio nodo. Por ejemplo, el nodo con identificador 34 no puede tener asociada una clave con id 35, pero si una con id 34. La regla general es que cada nodo tiene asignadas las claves con id menor o igual que su identificador de nodo, de forma que no haya otro nodo cuyo identificador esté más cerca del id de la clave. Por ejemplo, si tenemos los nodos 20 y 34, la clave con id 15 iría asociada al nodo 20, porque 15 está más cerca de 20 que de 34, pero la clave con id 21, iría asociada al nodo 34, porque 21 es mayor que 20 y no puede ir asociada a él.

El nodo con menor id del conjunto de nodos, puede tener claves asociadas con id mayor que él. Para explicarlo, lo haremos con un ejemplo. Imaginemos que tenemos un conjunto de nodos y que el nodo con mayor id es 54 de los 63 posibles identificadores. La clave 56, no puede ir asociada al nodo 54, por lo que pasa al siguiente nodo empezando por el principio de nuevo, que sería el nodo con id más bajo. Es decir, las claves que no puede recoger un nodo, se las pasa a su sucesor, que es el que tiene el siguiente id más alto que él. Si esta clave llega al nodo con id más bajo, se la asigna a él.

Other Languages
Deutsch: Chord
français: Chord
italiano: Progetto Chord
日本語: Chord
한국어: Chord
norsk: Chord
svenska: Chord