Коорде

В одноранговых сетях Koorde — это система распределенной хэш-таблицы (DHT), основанная на Chord DHT и графе Де Брейна ( последовательность Де Брейна ). Унаследовав простоту Chord, Koorde соответствует O (log n ) переходов на узел (где n — количество узлов в DHT) и ⁠ ⁠${\displaystyle O\left({\frac {\log n}{\log(\log n)}}\right)}$ переходов на запрос поиска с O (log n ) соседями на узел.

Концепция Chord основана на широком диапазоне идентификаторов (например, 2 ¹⁶⁰ ) в структуре кольца , где идентификатор может обозначать как узел, так и данные. Узел-преемник отвечает за весь диапазон идентификаторов между собой и своим предшественником.

Koorde основан на Chord, но также и на графе Де Брейна ( последовательности Де Брейна ). В d -мерном графе Де Брейна есть 2 ^d узлов , каждый из которых имеет уникальный идентификатор с d битами . Узел с идентификатором i соединен с узлами 2 i mod 2 ^d и 2 i + 1 mod 2 ^d . Благодаря этому свойству алгоритм маршрутизации может направлять к любому месту назначения за d переходов, последовательно «сдвигая» биты идентификатора места назначения, но только если размеры расстояния между mod 1 d и 3 d равны.

Маршрутизация сообщения от узла m к узлу k выполняется путем взятия числа m и сдвига битов k по одному за раз, пока число не будет заменено на k . Каждый сдвиг соответствует маршрутному переходу к следующему промежуточному адресу; переход допустим, поскольку соседи каждого узла являются двумя возможными результатами сдвига 0 или 1 на его собственный адрес. Из-за структуры графов де Брейна, когда последний бит k был сдвинут, запрос будет на узле k . Узел k отвечает, существует ли ключ k .

Например, когда сообщение необходимо направить из узла 2 (который является 010) в узел 6 (который является 110), шаги следующие:

1. Узел 2 направляет сообщение узлу 5 (используя его соединение с 2 i + 1 mod 8 ), сдвигает биты влево и помещает 1в качестве самого младшего бита (справа).
2. Узел 5 направляет сообщение узлу 3 (используя его соединение с 2i + 1 mod 8 ), сдвигает биты влево и помещает в1 качестве самого младшего бита (справа).
3. Узел 3 направляет сообщение узлу 6 (используя его соединение с 2i mod 8 ), сдвигает биты влево и помещает 0в качестве самого младшего бита (справа).

D - мерный де Брейн может быть обобщен до базы k , в этом случае узел i соединен с узлами k • i + j mod kd , 0 ≤ j < k . Диаметр уменьшается до Θ (log _k n ) . Узел Koorde i поддерживает указатели на k последовательных узлов, начиная с предшественника k • i mod kd . Каждый шаг маршрутизации де Брейна можно эмулировать с ожидаемым постоянным числом сообщений, поэтому маршрутизация использует O (log _k n ) ожидаемых переходов. Для k = Θ(log n ) мы получаем степень Θ(log n ) и диаметр${\displaystyle \Theta \left({\frac {\log n}{\log(\log n)}}\right)}$ .

функция n.lookup ( k , shift , i ) { если k ∈ ( n , s ] вернуть ( s ) ; иначе если i ∈ ( n , s ] вернуть p.lookup ( k , shift << 1 , i ∘ topBit ( shift ) ) ; иначе вернуть s.lookup ( k , shift , i ) ; }​​                             

Псевдокод для алгоритма поиска Koorde в узле n:

• kэто ключ
• I— воображаемый узел Де Брейна
• pэто ссылка на предшественника2n
• sэто ссылка на преемникаn

• «Интернет-алгоритмы» Грега Плэкстона, осень 2003 г.: [1]
• «Koorde: Простая оптимальная по степени распределенная хэш-таблица» М. Франса Каашука и Дэвида Р. Каргера: [2]
• Описания аккордов и коорда: [3]