Распределенная хэш-таблица

Децентрализованная распределенная система со службой поиска

Распределенная хэш-таблица ( DHT ) — это распределенная система , которая предоставляет услугу поиска, похожую на хэш-таблицу . Пары ключ-значение хранятся в DHT, и любой участвующий узел может эффективно извлекать значение, связанное с данным ключом. Главное преимущество DHT заключается в том, что узлы можно добавлять или удалять с минимальными усилиями по перераспределению ключей. ^[1] Ключи — это уникальные идентификаторы, которые сопоставляются с определенными значениями , которые, в свою очередь, могут быть чем угодно: от адресов до документов и произвольных данных . ^[2] Ответственность за поддержание сопоставления ключей со значениями распределяется между узлами таким образом, что изменение в наборе участников вызывает минимальное количество сбоев. Это позволяет DHT масштабироваться до чрезвычайно большого количества узлов и обрабатывать постоянные прибытия, отправления и сбои узлов.

DHT формируют инфраструктуру, которую можно использовать для создания более сложных сервисов, таких как anycast , кооперативное веб-кэширование , распределенные файловые системы , службы доменных имен , мгновенные сообщения , многоадресная рассылка , а также одноранговые системы обмена файлами и распространения контента . Известные распределенные сети, которые используют DHT, включают распределенный трекер BitTorrent, сеть Kad , ботнет Storm , мгновенный мессенджер Tox , Freenet , поисковую систему YaCy и файловую систему InterPlanetary .

Распределенные хэш-таблицы

История

Исследования DHT изначально были мотивированы, в частности, одноранговыми (P2P) системами, такими как Freenet , Gnutella , BitTorrent и Napster , которые использовали ресурсы, распределенные по Интернету, для предоставления единого полезного приложения. В частности, они использовали преимущества увеличенной пропускной способности и емкости жесткого диска для предоставления службы обмена файлами. ^[3]

Эти системы различались тем, как они находили данные, предлагаемые их коллегами. Napster, первая крупномасштабная система доставки контента P2P, требовала центрального индексного сервера: каждый узел при присоединении отправлял список локально хранящихся файлов на сервер, который выполнял поиск и направлял запросы на узлы, хранящие результаты. Этот центральный компонент делал систему уязвимой для атак и судебных исков.

Gnutella и подобные сети перешли на модель затопления запросов — по сути, каждый поиск приводил к трансляции сообщения на каждую машину в сети. Избегая единой точки отказа , этот метод был значительно менее эффективен, чем Napster. Более поздние версии клиентов Gnutella перешли на динамическую модель запросов, что значительно повысило эффективность. ^[4]

Freenet полностью распределен, но использует эвристическую маршрутизацию на основе ключей , в которой каждый файл связан с ключом, а файлы с похожими ключами имеют тенденцию группироваться на похожем наборе узлов. Запросы, скорее всего, будут направляться через сеть в такой кластер без необходимости посещать множество пиров. ^[5] Однако Freenet не гарантирует, что данные будут найдены.

Распределенные хэш-таблицы используют более структурированную маршрутизацию на основе ключей для достижения как децентрализации Freenet и Gnutella, так и эффективности и гарантированных результатов Napster. Один из недостатков заключается в том, что, как и Freenet, DHT напрямую поддерживают только поиск по точному совпадению, а не поиск по ключевым словам, хотя алгоритм маршрутизации Freenet можно обобщить для любого типа ключа, где можно определить операцию близости. ^[6]

В 2001 году четыре системы — CAN , ^[7] Chord , ^[8] Pastry и Tapestry — зажгли DHT как популярную тему исследований. Проект под названием Infrastructure for Resilient Internet Systems (Iris) был профинансирован грантом в размере 12 миллионов долларов от Национального научного фонда США в 2002 году. ^[9] Среди исследователей были Сильвия Ратнасами , Ион Стоика , Хари Балакришнан и Скотт Шенкер . ^[10] За пределами академических кругов технология DHT была принята в качестве компонента BitTorrent и в проектах PlanetLab, таких как Coral Content Distribution Network. ^[11]

Характеристики

Для DHT характерны следующие свойства:

• Автономность и децентрализация : узлы в совокупности образуют систему без какой-либо центральной координации.
• Отказоустойчивость : система должна быть надежной (в некотором смысле) даже при постоянном присоединении, отсоединении и выходе из строя узлов. ^[12]
• Масштабируемость : система должна эффективно функционировать даже при наличии тысяч или миллионов узлов.

Ключевой метод, используемый для достижения этих целей, заключается в том, что любому узлу необходимо координировать работу только с несколькими другими узлами в системе — чаще всего с O (log n ) из n участников (см. ниже) — так что для каждого изменения в составе необходимо выполнить лишь ограниченный объем работы.

Некоторые проекты DHT стремятся обеспечить защиту от злонамеренных участников ^[13] и позволить участникам оставаться анонимными , хотя это встречается реже, чем во многих других одноранговых системах (особенно для обмена файлами ); см. анонимный P2P .

Структура

Структуру DHT можно разложить на несколько основных компонентов. ^{[14] [15]} Основой является абстрактное пространство ключей , например, набор 160-битных строк . Схема разбиения пространства ключей разделяет владение этим пространством ключей между участвующими узлами. Затем оверлейная сеть соединяет узлы, позволяя им находить владельца любого заданного ключа в пространстве ключей.

После того, как эти компоненты будут установлены, типичное использование DHT для хранения и извлечения может происходить следующим образом. Предположим, что пространство ключей представляет собой набор 160-битных строк. Чтобы индексировать файл с заданным именем файла и данными в DHT, генерируется хэш SHA-1 имени файла , что создает 160-битный ключ k , и сообщение put ( k, data ) отправляется любому узлу, участвующему в DHT. Сообщение пересылается от узла к узлу через оверлейную сеть, пока не достигнет единственного узла, ответственного за ключ k , как указано в разбиении пространства ключей. Затем этот узел сохраняет ключ и данные. Затем любой другой клиент может извлечь содержимое файла, снова хэшируя имя файла для получения k и запрашивая любой узел DHT найти данные, связанные с k , с помощью сообщения get ( k ) . Сообщение снова будет направлено через оверлей к узлу, ответственному за k , который ответит сохраненными данными .

Ниже описаны компоненты разделения пространства ключей и оверлейной сети с целью отражения основных идей, общих для большинства DHT; многие конструкции различаются в деталях.

Разделение пространства ключей

Большинство DHT используют некоторые варианты согласованного хеширования или хеширования рандеву для сопоставления ключей с узлами. Оба алгоритма, по-видимому, были разработаны независимо и одновременно для решения проблемы распределенной хеш-таблицы.

Как согласованное хеширование, так и рандеву-хеширование имеют существенное свойство: удаление или добавление одного узла изменяет только набор ключей, принадлежащих узлам со смежными идентификаторами, и оставляет все остальные узлы нетронутыми. Сравните это с традиционной хеш-таблицей, в которой добавление или удаление одного контейнера приводит к перераспределению почти всего пространства ключей. Поскольку любое изменение владельца обычно соответствует интенсивному перемещению объектов, хранящихся в DHT, с одного узла на другой, требуется минимизация такой реорганизации для эффективной поддержки высоких показателей оттока (прихода и отказа узла).

Последовательное хеширование

Последовательное хеширование использует функцию , которая определяет абстрактное понятие расстояния между ключами и , которое не связано с географическим расстоянием или задержкой сети . Каждому узлу назначается один ключ, называемый его идентификатором (ID). Узел с ID владеет всеми ключами, для которых является ближайший ID, измеренный в соответствии с . ${\displaystyle \delta (k_{1},k_{2})}$ ${\displaystyle k_{1}}$ ${\displaystyle k_{2}}$ ${\displaystyle i_{x}}$ ${\displaystyle k_{m}}$ ${\displaystyle i_{x}}$ ${\displaystyle \delta (k_{m},i_{x})}$

Например, Chord DHT использует согласованное хеширование, которое рассматривает узлы как точки на окружности, и является расстоянием, пройденным по часовой стрелке по окружности от до . Таким образом, круговое пространство ключей разделено на смежные сегменты, конечные точки которых являются идентификаторами узлов. Если и являются двумя соседними идентификаторами с более коротким расстоянием по часовой стрелке от до , то узел с идентификатором владеет всеми ключами, которые попадают между и . ${\displaystyle \delta (k_{1},k_{2})}$ ${\displaystyle k_{1}}$ ${\displaystyle k_{2}}$ ${\displaystyle i_{1}}$ ${\displaystyle i_{2}}$ ${\displaystyle i_{1}}$ ${\displaystyle i_{2}}$ ${\displaystyle i_{2}}$ ${\displaystyle i_{1}}$ ${\displaystyle i_{2}}$

Рандеву хеширование

При рандеву-хешировании, также называемом хешированием с наивысшим случайным весом (HRW), все клиенты используют одну и ту же хеш-функцию (выбранную заранее) для привязки ключа к одному из n доступных серверов. У каждого клиента есть один и тот же список идентификаторов { S ₁ , S ₂ , ..., S _n } , по одному для каждого сервера. При наличии некоторого ключа k клиент вычисляет n хеш-весов w ₁ = h ( S ₁ , k ), w ₂ = h ( S ₂ , k ), ..., w _n = h ( S _n , k ) . Клиент связывает этот ключ с сервером, соответствующим наивысшему хеш-весу для этого ключа. Сервер с идентификатором владеет всеми ключами , для которых хеш-вес выше, чем хеш-вес любого другого узла для этого ключа. ${\displaystyle h()}$ ${\displaystyle S_{x}}$ ${\displaystyle k_{m}}$ ${\displaystyle h(S_{x},k_{m})}$

Хеширование, сохраняющее локальность

Хеширование с сохранением локальности гарантирует, что схожие ключи назначаются схожим объектам. Это может обеспечить более эффективное выполнение запросов диапазона, однако, в отличие от использования последовательного хеширования, нет больше гарантий того, что ключи (и, следовательно, нагрузка) равномерно случайным образом распределены по пространству ключей и участвующим одноранговым узлам. Протоколы DHT, такие как Self-Chord и Oscar ^[16], решают такие проблемы. Self-Chord отделяет ключи объектов от идентификаторов одноранговых узлов и сортирует ключи по кольцу с помощью статистического подхода, основанного на парадигме роевого интеллекта . ^[17] Сортировка гарантирует, что схожие ключи хранятся соседними узлами и что процедуры обнаружения, включая запросы диапазона , могут быть выполнены за логарифмическое время. Oscar создает навигируемую сеть малого мира на основе случайной выборки, также гарантируя логарифмическое время поиска.

Наложенная сеть

Каждый узел поддерживает набор ссылок на другие узлы (свои соседи или таблицу маршрутизации ). Вместе эти ссылки образуют оверлейную сеть. ^[18] Узел выбирает своих соседей в соответствии с определенной структурой, называемой топологией сети .

Все топологии DHT разделяют некоторый вариант наиболее существенного свойства: для любого ключа k каждый узел либо имеет идентификатор узла, которому принадлежит k , либо имеет ссылку на узел, идентификатор узла которого ближе к k , с точки зрения расстояния пространства ключей, определенного выше. Затем легко направить сообщение владельцу любого ключа k, используя следующий жадный алгоритм (который не обязательно является глобально оптимальным): на каждом шаге пересылать сообщение соседу, идентификатор которого ближе всего к k . Если такого соседа нет, то мы должны были прийти к ближайшему узлу, который является владельцем k , как определено выше. Этот стиль маршрутизации иногда называют маршрутизацией на основе ключей .

Помимо базовой корректности маршрутизации, два важных ограничения на топологию — гарантировать, что максимальное количество переходов в любом маршруте (длина маршрута) будет низким, чтобы запросы выполнялись быстро; и что максимальное количество соседей любого узла (максимальная степень узла ) будет низким, чтобы накладные расходы на обслуживание не были чрезмерными. Конечно, наличие более коротких маршрутов требует более высокой максимальной степени . Некоторые общие варианты максимальной степени и длины маршрута приведены ниже, где n — количество узлов в DHT, с использованием нотации Big O :

Наиболее распространенный выбор, степень/длина маршрута, не является оптимальным с точки зрения компромисса степени/длины маршрута, но такие топологии обычно обеспечивают большую гибкость в выборе соседей. Многие DHT используют эту гибкость для выбора соседей, которые близки с точки зрения задержки в физической базовой сети. В целом, все DHT создают управляемые топологии сетей малого мира, которые компромисс между длиной маршрута и степенью сети. ^[19] ${\displaystyle O(\log n)}$

Максимальная длина маршрута тесно связана с диаметром : максимальным числом переходов в любом кратчайшем пути между узлами. Очевидно, что длина маршрута в худшем случае сети по крайней мере равна ее диаметру, поэтому DHT ограничены компромиссом степени/диаметра ^[20], который является фундаментальным в теории графов . Длина маршрута может быть больше диаметра, поскольку жадный алгоритм маршрутизации может не найти кратчайшие пути. ^[21]

Алгоритмы для наложенных сетей

Помимо маршрутизации, существует множество алгоритмов, которые используют структуру оверлейной сети для отправки сообщения всем узлам или подмножеству узлов в DHT. ^[22] Эти алгоритмы используются приложениями для выполнения оверлейной многоадресной рассылки , запросов диапазона или сбора статистики. Две системы, основанные на этом подходе, — это Structella, ^[23] которая реализует лавинную рассылку и случайные блуждания на оверлее Pastry, и DQ-DHT, которая реализует динамический алгоритм поиска запросов по сети Chord. ^[24]

Безопасность

Благодаря децентрализации, отказоустойчивости и масштабируемости DHT по своей сути более устойчивы к атакам злоумышленников, чем централизованная система. ^{[ неопределенно ]}

Открытые системы для распределенного хранения данных , устойчивые к массированным атакам, вполне возможны. ^[25]

Система DHT, тщательно спроектированная с учетом византийской отказоустойчивости , может защитить от уязвимости безопасности, известной как атака Сивиллы , которая затрагивает большинство современных конструкций DHT. ^{[26] [27]} Whanau — это DHT, разработанная с учетом устойчивости к атакам Сивиллы. ^[28]

Петар Маймунков, один из первоначальных авторов Kademlia , предложил способ обойти уязвимость атаки Сивиллы, включив в конструкцию системы отношения социального доверия. ^[29] Новая система под кодовым названием Tonika или также известная по доменному имени как 5ttt, основана на алгоритме, известном как «электрическая маршрутизация» и созданном в соавторстве с математиком Джонатаном Кельнером. ^[30] Маймунков в настоящее время предпринял всеобъемлющие усилия по внедрению этой новой системы. Однако исследования эффективной защиты от атак Сивиллы обычно считаются открытым вопросом, и каждый год на ведущих конференциях по исследованию безопасности предлагается широкий спектр потенциальных защит. ^{[ необходима ссылка ]}

Реализации

Наиболее заметные различия, встречающиеся на практике при реализации DHT, включают в себя, по крайней мере, следующее:

• Адресное пространство является параметром DHT. Несколько реальных DHT используют 128-битное или 160-битное ключевое пространство.
• Некоторые реальные DHT используют хеш-функции, отличные от SHA-1 .
• В реальном мире ключ k может быть хешем содержимого файла, а не хешем имени файла , чтобы обеспечить хранилище с адресацией по содержимому , так чтобы переименование файла не мешало пользователям находить его.
• Некоторые DHT также могут публиковать объекты разных типов. Например, ключ k может быть идентификатором узла , а связанные данные могут описывать, как связаться с этим узлом. Это позволяет публиковать информацию о присутствии и часто используется в приложениях обмена мгновенными сообщениями и т. д. В простейшем случае идентификатор — это просто случайное число, которое напрямую используется как ключ k (поэтому в 160-битном DHT идентификатор будет 160-битным числом, обычно выбираемым случайным образом). В некоторых DHT публикация идентификаторов узлов также используется для оптимизации операций DHT.
• Для повышения надежности можно добавить избыточность. Пара ключей (k, data) может храниться в более чем одном узле, соответствующем ключу. Обычно, вместо выбора только одного узла, алгоритмы DHT в реальном мире выбирают i подходящих узлов, причем i является параметром реализации DHT. В некоторых конструкциях DHT узлы соглашаются обрабатывать определенный диапазон пространства ключей, размер которого может выбираться динамически, а не жестко закодирован.
• Некоторые продвинутые DHT, такие как Kademlia, сначала выполняют итеративный поиск по DHT, чтобы выбрать набор подходящих узлов и отправлять сообщения put(k, data) только этим узлам, тем самым радикально сокращая бесполезный трафик, поскольку опубликованные сообщения отправляются только тем узлам, которые кажутся подходящими для хранения ключа k ; и итеративный поиск охватывает только небольшой набор узлов, а не весь DHT, сокращая бесполезную пересылку. В таких DHT пересылка сообщений put(k, data) может происходить только как часть алгоритма самовосстановления: если целевой узел получает сообщение put(k, data) , но считает, что k находится вне его диапазона обработки, и известен более близкий узел (с точки зрения пространства ключей DHT), сообщение пересылается на этот узел. В противном случае данные индексируются локально. Это приводит к несколько самобалансирующемуся поведению DHT. Конечно, такой алгоритм требует, чтобы узлы публиковали свои данные о присутствии в DHT, чтобы можно было выполнять итеративный поиск.
• Поскольку на большинстве машин отправка сообщений обходится намного дороже, чем доступ к локальной хэш-таблице, имеет смысл объединять много сообщений, касающихся конкретного узла, в один пакет. Предполагая, что каждый узел имеет локальный пакет, состоящий не более чем из b операций, процедура объединения выглядит следующим образом. Каждый узел сначала сортирует свой локальный пакет по идентификатору узла, ответственного за операцию. Используя сортировку по сегментам , это можно сделать за O(b + n) , где n — количество узлов в DHT. Когда в одном пакете есть несколько операций, обращающихся к одному и тому же ключу, пакет уплотняется перед отправкой. Например, несколько поисков одного и того же ключа можно свести к одному или несколько приращений можно свести к одной операции добавления. Это сокращение можно реализовать с помощью временной локальной хэш-таблицы. Наконец, операции отправляются соответствующим узлам. ^[31]

Примеры

Протоколы и реализации DHT

• Апач Кассандра
• Накладка BATON
• Основной DHT – стандартный DHT, используемый BitTorrent (основанный на Kademlia , предоставленном Khashmir) ^[32]
• Адресная сеть контента (CAN)
• Аккорд
• Коорде
• Кадемлия
• Выпечка
• P-сетка
• Риак
• ScyllaDB
• Гобелен
• ТомP2P
• Волдеморт

Приложения, использующие DHT

• BTDigg : поисковая система BitTorrent DHT
• Codeen : веб-кэширование
• Freenet : анонимная сеть, устойчивая к цензуре
• GlusterFS : распределенная файловая система, используемая для виртуализации хранения данных.
• GNUnet : распределительная сеть типа Freenet, включающая реализацию DHT
• I2P : Анонимная одноранговая сеть с открытым исходным кодом
• I2P-Bote : безсерверная безопасная анонимная электронная почта
• IPFS : адресованный по содержимому, одноранговый протокол распространения гипермедиа
• JXTA : P2P-платформа с открытым исходным кодом
• LBRY : протокол обмена контентом на основе блокчейна, который использует систему DHT под влиянием Kademlia для распространения контента.
• Oracle Coherence : сетка данных в памяти, созданная на основе реализации Java DHT
• Perfect Dark : приложение для обмена файлами по пиринговой сети из Японии
• Retroshare : сеть «друг другу» ^[33]
• Jami : платформа для голосовой, видео и чат-коммуникации, сохраняющая конфиденциальность, основанная на DHT, подобном Kademlia
• Tox : система мгновенного обмена сообщениями, призванная заменить Skype .
• Twister : одноранговая платформа микроблогов
• YaCy : распределенная поисковая система

Смотрите также

• Couchbase Server : постоянная, реплицированная, кластеризованная распределенная система хранения объектов, совместимая с протоколом Memcached.
• Memcached : высокопроизводительная распределенная система кэширования объектов памяти.
• Префиксное хэш-дерево : сложные запросы по DHT.
• Дерево Меркла : дерево, в котором каждый нелистовой узел помечен хешем меток его дочерних узлов.
• Большинство распределенных хранилищ данных используют для поиска ту или иную форму DHT.
• Графы пропуска представляют собой эффективную структуру данных для реализации DHT.

Ссылки

1. Хота, Читтаранджан; Шримани, Прадип К. (11 января 2013 г.). Распределенные вычисления и интернет-технологии: 9-я Международная конференция ICDCIT 2013, Бхубанешвар, Индия, 5-8 февраля 2013 г., Материалы. Спрингер. ISBN 978-3-642-36071-8.
2. Stoica, I. ; Morris, R.; Karger, D. ; Kaashoek, MF; Balakrishnan, H. (2001). "Chord: масштабируемая одноранговая служба поиска для интернет-приложений" (PDF) . ACM SIGCOMM Computer Communication Review . 31 (4): 149. doi :10.1145/964723.383071. Архивировано (PDF) из оригинала 2023-07-07 . Получено 2018-09-18 . Значение может быть адресом, документом или произвольным элементом данных.
3. Лиз, Кроукрофт и др. (2005). «Обзор и сравнение схем одноранговых оверлейных сетей» (PDF) . IEEE Communications Surveys & Tutorials . 7 (2): 72–93. CiteSeerX 10.1.1.109.6124 . doi :10.1109/COMST.2005.1610546. S2CID  7971188. Архивировано (PDF) из оригинала 2023-10-05 . Получено 2019-09-24 . 
4. Рихтер, Стивенсон и др. (2009). «Анализ влияния моделей динамических запросов на клиент-серверные отношения». Тенденции в современных вычислениях : 682–701.
5. Поиск в маленьком мире. Главы 1 и 2 (PDF) , заархивировано из оригинала (PDF) 2012-03-16 , извлечено 2012-01-10
6. "Раздел 5.2.2" (PDF) , Распределенная децентрализованная система хранения и поиска информации , заархивировано из оригинала (PDF) 2012-03-16 , извлечено 2012-01-10
7. Ратнасами, Сильвия; Фрэнсис, Пол; Хэндли, Марк; Карп, Ричард; Шенкер, Скотт (27.08.2001). «Масштабируемая контентно-адресуемая сеть». SIGCOMM Comput. Commun. Rev. 31 ( 4): 161–172. doi :10.1145/964723.383072. ISSN  0146-4833.
8. Хари Балакришнан , М. Франс Каашук , Дэвид Каргер, Роберт Моррис и Ион Стоика. Поиск данных в системах P2P. Архивировано 19 мая 2016 г. в Wayback Machine . В Communications of the ACM , февраль 2003 г.
9. Дэвид Коэн (1 октября 2002 г.). «Новая P2P-сеть, финансируемая правительством США». New Scientist . Архивировано из оригинала 6 апреля 2008 г. Получено 10 ноября 2013 г.
10. "MIT, Berkeley, ICSI, NYU и Rice запускают проект IRIS". Пресс-релиз . MIT. 25 сентября 2002 г. Архивировано из оригинала 26 сентября 2015 г. Получено 10 ноября 2013 г.
11. "Демократизация публикации контента с помощью Coral" (PDF) . NSDI . 4 . 2004 . Получено 2024-05-01 .
12. R Mokadem, A Hameurlain и AM Tjoa. Служба обнаружения ресурсов при минимизации накладных расходов на обслуживание в иерархических системах DHT Архивировано 09.08.2022 в Wayback Machine . Proc. iiWas, 2010
13. Гвидо Урданета, Гийом Пьер и Маартен ван Стен. Обзор методов безопасности DHT. Архивировано 01.06.2023 на Wayback Machine . ACM Computing Surveys 43(2), январь 2011 г.
14. Мони Наор и Уди Видер. Новые архитектуры для приложений P2P: непрерывно-дискретный подход. Архивировано 09.12.2019 в Wayback Machine . Proc. SPAA, 2003.
15. Гурмит Сингх Манку. Dipsea: Модульная распределенная хэш-таблица. Архивировано 10 сентября 2004 г. на Wayback Machine . Докторская диссертация (Стэнфордский университет), август 2004 г.
16. Гирдзиаускас, Шарунас; Датта, Анвитаман; Аберер, Карл (2010-02-01). «Структурированное наложение для гетерогенных сред». ACM Transactions on Autonomous and Adaptive Systems . 5 (1): 1–25. doi :10.1145/1671948.1671950. ISSN  1556-4665. S2CID  13218263. Архивировано из оригинала 2020-07-12 . Получено 2020-03-12 .
17. Форестьеро, Агостино; Леонарди, Эмилио; Мастроянни, Карло; Мео, Микела (октябрь 2010 г.). «Self-Chord: вдохновленная биотехнологиями P2P-инфраструктура для самоорганизующихся распределенных систем». IEEE/ACM Transactions on Networking . 18 (5): 1651–1664. doi :10.1109/TNET.2010.2046745. S2CID  14797120. Архивировано из оригинала 01.07.2012 . Получено 28.07.2019 .
18. Галуба, Войцех; Гирджияускас, Шарунас (2009), «Оверлейные сети с равноправным доступом: структура, маршрутизация и обслуживание», в LIU, LING ; ÖZSU, M. TAMER (ред.), Энциклопедия систем баз данных , Springer US, стр. 2056–2061, doi :10.1007/978-0-387-39940-9_1215, ISBN 9780387399409
19. Гирджияускас, Шарунас (2009). Проектирование одноранговых наложений с точки зрения маленького мира. epfl.ch (Диссертация). EPFL. doi :10.5075/epfl-thesis-4327. Архивировано из оригинала 2020-03-03 . Получено 2019-11-11 .
20. Проблема (степени, диаметра) для графов, Maite71.upc.es, заархивировано из оригинала 2012-02-17 , извлечено 2012-01-10
21. Гурмит Сингх Манку, Мони Наор и Уди Видер. «Знай соседа своего соседа: сила упреждающего просмотра в рандомизированных сетях P2P». Архивировано 20 апреля 2008 г. в Wayback Machine . Proc. STOC, 2004.
22. Али Годси (22 мая 2007 г.). "Распределенная k-ичная система: алгоритмы для распределенных хэш-таблиц". Архивировано из оригинала 22 мая 2007 г.. KTH-Королевский технологический институт, 2006.
23. Кастро, Мигель; Коста, Мануэль; Роустрон, Энтони (1 января 2004 г.). «Стоит ли нам строить Gnutella на структурированном оверлее?» (PDF) . Обзор компьютерной связи ACM SIGCOMM . 34 (1): 131. CiteSeerX 10.1.1.221.7892 . doi :10.1145/972374.972397. S2CID  6587291. Архивировано (PDF) из оригинала 14 февраля 2021 г. . Получено 25 сентября 2019 г. . 
24. Талия, Доменико; Трунфио, Паоло (декабрь 2010 г.). «Включение динамических запросов к распределенным хэш-таблицам». Журнал параллельных и распределенных вычислений . 70 (12): 1254–1265. doi :10.1016/j.jpdc.2010.08.012.
25. Барух Авербух, Кристиан Шайделер. «На пути к масштабируемому и надежному DHT». 2006. doi :10.1145/1148109.1148163
26. Максвелл Янг; Аникет Кейт; Ян Голдберг; Мартин Карстен. «Практическая надежная связь в DHT, выдерживающая византийского противника». Архивировано 22 июля 2016 г. на Wayback Machine .
27. Наталья Федотова; Джордано Орцетти; Лука Велтри; Алессандро Закканьини. «Византийское соглашение об управлении репутацией в одноранговых сетях на основе DHT». дои : 10.1109/ICTEL.2008.4652638
28. Whanau: Распределенная хэш-таблица, защищенная от атак Сивиллы https://pdos.csail.mit.edu/papers/whanau-nsdi10.pdf Архивировано 25 января 2022 г. на Wayback Machine
29. Lesniewski-Laas, Chris (2008-04-01). "A Sybil-proof one-hop DHT". Труды 1-го семинара по системам социальных сетей . SocialNets '08. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 19–24. doi :10.1145/1435497.1435501. ISBN 978-1-60558-124-8.
30. Кельнер, Джонатан; Маймунков, Петар (2011-07-22). «Электрическая маршрутизация и резка параллельных потоков». Теоретическая информатика . Алгоритмы и вычисления. 412 (32): 4123–4135. doi :10.1016/j.tcs.2010.06.013. ISSN  0304-3975.
31. Сандерс, Питер; Мельхорн, Курт; Дицфельбингер, Мартин; Дементьев, Роман (2019). Последовательные и параллельные алгоритмы и структуры данных: базовый набор инструментов. Springer International Publishing. ISBN 978-3-030-25208-3. Архивировано из оригинала 2021-08-17 . Получено 2020-01-22 .
32. Tribler wiki Архивировано 4 декабря 2010 г., на Wayback Machine получено в январе 2010 г.
33. Retroshare FAQ Архивировано 17 июля 2013 г. на Wayback Machine , получено в декабре 2011 г.

Внешние ссылки

• Распределенные хэш-таблицы, часть 1, Брэндон Уайли.
• Распределенные хэш-таблицы ссылаются на страницу Карлеса Пайро по исследованию DHT и P2P
• kademlia.scs.cs.nyu.edu Archive.org снимки kademlia.scs.cs.nyu.edu
• Eng-Keong Lua; Crowcroft, Jon; Pias, Marcelo; Sharma, Ravi; Lim, Steve (2005). "IEEE Survey on overlay network schemes". CiteSeerX  10.1.1.111.4197 :охватывающий неструктурированные и структурированные децентрализованные наложенные сети, включая DHT (Chord, Pastry, Tapestry и другие).
• Основное измерение DHT на кафедре компьютерных наук Хельсинкского университета, Финляндия.