Saltar al contenido
Carrusel educativo sobre las tablas hash distribuidas y el algoritmo Chord: el anillo, la regla del sucesor, la finger table y la búsqueda en O(log N).
Diapositiva 2 de 7
Diapositiva 3 de 7
Diapositiva 4 de 7
Diapositiva 5 de 7
Diapositiva 6 de 7
Diapositiva 7 de 7
1 / 7

// Sistemas distribuidos

DHT y Chord

Encontrar un dato entre un millón de computadoras sin servidor central, en unos 20 saltos. Así funciona Chord

Chord ubica nodos y datos en un anillo usando la misma función hash. Cada dato se guarda en el primer nodo cuyo ID es mayor o igual a su clave (la regla del sucesor), y cada nodo tiene una finger table con atajos a distancias que se duplican. Por eso la búsqueda toma O(log N) saltos.

Dato: el mismo truco de duplicar las distancias es el de la búsqueda binaria. Cada paso descarta la mitad del espacio restante, por eso crece tan poco aunque la red sea enorme.

Publicamos un post nuevo cada semana en Instagram y TikTok.

Más de Sistemas distribuidos