Acorde (de igual a igual)
En informática , Chord es un protocolo y algoritmo para una tabla hash distribuida de igual a igual . Una tabla hash distribuida almacena pares clave-valor asignando claves a diferentes computadoras (conocidas como "nodos"); un nodo almacenará 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 esa clave.
Chord es uno de los cuatro protocolos de tabla hash distribuidos originales , junto con CAN , Tapestry y Pastry . Fue introducido en 2001 por Ion Stoica , Robert Morris , David Karger , Frans Kaashoek y Hari Balakrishnan , y fue desarrollado en el MIT . [1]
A los nodos y las claves se les asigna un identificador de bits mediante un hash coherente . El algoritmo SHA-1 es la función de hash base para un hash consistente. El hash consistente es integral 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 identificador con una posibilidad insignificante de colisión . Por lo tanto, también permite que los nodos se unan y salgan de la red sin interrupciones. En el protocolo, el término nodo se utiliza para referirse tanto a un nodo en sí como a su identificador (ID) sin ambigüedad. También lo es el término clave .
Con el protocolo de búsqueda de acordes, los nodos y las claves se organizan en un círculo identificador que tiene en la mayoría de los nodos, que van desde hasta . ( debe 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 identificador en el sentido de las agujas del reloj. El predecesor es en sentido antihorario. Si hay un nodo para cada posible ID, el sucesor del nodo 0 es el nodo 1 y el predecesor del nodo 0 es el nodo ; sin embargo, normalmente hay "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 claves. El nodo sucesor de una clave es el primer nodo cuyo ID es igual o sigue en el círculo identificador, indicado por . Cada clave está asignada a (almacenada en) su nodo sucesor, por lo que buscar una clave es realizar una consulta .
