分散ハッシュテーブル

分散ハッシュテーブル( DHT )は、ハッシュテーブルに似た検索サービスを提供する分散システムです。キーと値のペアが DHT に格納され、参加しているどのノードも、特定のキーに関連付けられた値を効率的に取得できます。DHT の主な利点は、キーの再配布を最小限に抑えてノードを追加または削除できることです。^[1]キーは、特定の値にマップされる一意の識別子であり、その値は、アドレス、ドキュメント、任意のデータなど、何にでもなり得ます。^[2]キーから値へのマッピングを維持する責任は、参加者セットの変更による混乱が最小限になるように、ノード間で分散されています。これにより、DHT は非常に多数のノードに拡張でき、継続的なノードの到着、離脱、および障害を処理できます。

DHT は、エニーキャスト、協調Web キャッシュ、分散ファイルシステム、ドメイン名サービス、インスタントメッセージング、マルチキャスト、ピアツーピアファイル共有およびコンテンツ配信システムなど、より複雑なサービスを構築するために使用できるインフラストラクチャを形成します。DHT を使用する有名な分散ネットワークには、 BitTorrentの分散トラッカー、Kad ネットワーク、Storm ボットネット、Tox インスタントメッセンジャー、Freenet、YaCy検索エンジン、およびInterPlanetary File Systemがあります。

歴史

DHTの研究は、もともと、 Freenet、Gnutella、BitTorrent、Napsterなどのピアツーピア（P2P）システムがきっかけとなって始まりました。これらのシステムは、インターネット上に分散されたリソースを活用して、単一の便利なアプリケーションを提供していました。特に、帯域幅とハードディスク容量の増加を利用して、ファイル共有サービスを提供していました。^[3]

これらのシステムは、ピアが提供するデータを検索する方法が異なっていました。最初の大規模な P2P コンテンツ配信システムである Napster には、中央のインデックスサーバーが必要でした。各ノードは参加すると、ローカルに保存されているファイルのリストをサーバーに送信し、サーバーは検索を実行し、結果を保持しているノードにクエリを参照します。この中央コンポーネントにより、システムは攻撃や訴訟に対して脆弱になりました。

Gnutella や類似のネットワークはクエリフラッディングモデルに移行しました。つまり、検索するたびにメッセージがネットワーク内のすべてのマシンにブロードキャストされることになります。この方法は単一障害点を回避できますが、Napster に比べて効率がかなり悪かったです。Gnutella クライアントの後のバージョンでは、効率が大幅に向上した動的クエリモデルに移行しました。^[4]

Freenet は完全に分散されていますが、各ファイルがキーに関連付けられ、同様のキーを持つファイルは同様のノードセットに集まる傾向があるという、ヒューリスティックなキーベースのルーティングを採用しています。クエリは、多くのピアを訪問する必要なく、ネットワークを介してこのようなクラスターにルーティングされる可能性があります。 ^[5]ただし、Freenet ではデータが見つかる保証はありません。

分散ハッシュテーブルは、Freenet と Gnutella の分散性と Napster の効率性と保証された結果の両方を実現するために、より構造化されたキーベースのルーティングを使用します。1 つの欠点は、Freenet と同様に、DHT はキーワード検索ではなく、完全一致検索のみを直接サポートすることです。ただし、Freenet のルーティングアルゴリズムは、近似操作を定義できる任意のキータイプに一般化できます。^[6]

2001年、CAN、^[7] Chord、^[8] Pastry、Tapestryの4つのシステムが、DHTを人気の研究テーマとして火をつけた。 2002年、米国国立科学財団から1200万ドルの助成金を得て、Iris（Infrastructure for Resilient Internet Systems）と呼ばれるプロジェクトが立ち上げられた。 ^[9] 研究者には、 Sylvia Ratnasamy、Ion Stoica、Hari Balakrishnan、Scott Shenkerなどが含まれていた。^[10] 学術界以外では、DHT技術はBitTorrentのコンポーネントとして、またCoral Content Distribution NetworkなどのPlanetLabプロジェクトで採用されている。^[11]

プロパティ

DHT は、次のような特性を重視します。

自律性と分散化: ノードは中央の調整なしに集合的にシステムを形成します。
フォールトトレランス：ノードが継続的に参加、離脱、障害を起こしても、システムは（ある意味で）信頼できるものでなければならない。^[12]
スケーラビリティ: システムは数千または数百万のノードがあっても効率的に機能する必要があります。

これらの目標を達成するために使用される重要な技術は、1 つのノードがシステム内の他の少数のノードとのみ調整する必要があることです(最も一般的なのは、n人の参加者のうちのO (log n )個(以下を参照)) 。そのため、メンバーシップの変更ごとに実行する必要がある作業量は限られています。

一部のDHT設計では、悪意のある参加者^{[13]に対して}安全であることと、参加者が匿名のままでいられることを目指していますが、これは他の多くのピアツーピア（特にファイル共有）システムほど一般的ではありません。匿名P2Pを参照してください。

構造

DHTの構造は、いくつかの主要なコンポーネントに分解できます。^[14]^[15]基礎となるのは、160ビットの文字列のセットなどの抽象的なキースペースです。キースペースのパーティション分割スキームは、このキースペースの所有権を参加ノード間で分割します。次に、オーバーレイネットワークがノードを接続し、キースペース内の任意のキーの所有者を見つけることができるようにします。

これらのコンポーネントが配置されると、保存と取得のための DHT の一般的な使用は次のように進められます。キースペースが 160 ビットの文字列のセットであると仮定します。指定されたファイル名と $データを$ 持つファイルをDHT でインデックス化するには、 $ファイル名$ のSHA-1ハッシュを生成して 160 ビットのキー $k$ を作成し、メッセージ $put$ $($ $k, data$ $)$ を DHT に参加している任意のノードに送信します。メッセージは、オーバーレイネットワークを介してノードからノードへと転送され、キースペースのパーティション分割で指定されたキー $k$ を担当する単一のノードに到達します。次に、そのノードはキーとデータを保存します。他のクライアントは、再度 $ファイル名をハッシュして$ $k$ を生成し、メッセージ $get$ $($ $k$ $)を使用して任意の DHT ノードに$ $k$ に関連付けられたデータを検索するように依頼することで、ファイルの内容を取得できます。メッセージは再度オーバーレイを介して $k$ を担当するノードにルーティングされ、保存されている $データ$ で応答します。

キースペースパーティショニングとオーバーレイネットワークコンポーネントについては、ほとんどの DHT に共通する基本的な考え方を捉えることを目的として、以下で説明します。多くの設計では詳細が異なります。

キースペースのパーティション分割

ほとんどの DHT は、キーをノードにマッピングするために、コンシステントハッシュまたはランデブーハッシュの何らかのバリエーションを使用します。この 2 つのアルゴリズムは、分散ハッシュテーブル問題を解決するために独立して同時に考案されたようです。

コンシステントハッシュとランデブーハッシュはどちらも、1 つのノードを削除または追加すると、隣接する ID を持つノードが所有するキーセットのみが変更され、他のすべてのノードは影響を受けないという重要な特性を持っています。これを、1 つのバケットを追加または削除するとキー空間のほぼ全体が再マップされる従来のハッシュテーブルと比較してください。所有権の変更は通常、DHT に格納されているオブジェクトを 1 つのノードから別のノードに移動するために帯域幅を集中的に使用するため、高い変更率(ノードの到着と障害) を効率的にサポートするには、このような再編成を最小限に抑える必要があります。

一貫性のあるハッシュ

コンシステントハッシュでは、キーとの間の距離という抽象的な概念を定義する関数を使用します。この距離は、地理的な距離やネットワークの待ち時間とは無関係です。各ノードには、識別子(ID)と呼ばれる単一のキーが割り当てられます。ID を持つノードは、に従って測定された最も近い ID を持つのすべてのキーを所有します。 $\delta (k_{1},k_{2})$ $k_{1}$ $k_{2}$ $i_{x}$ $k_{m}$ $i_{x}$ $\delta (k_{m},i_{x})$

たとえば、Chord DHT は、ノードを円上の点として扱うコンシステントハッシュを使用します。は、からまで円を時計回りに回った距離です。したがって、円形のキー空間は、エンドポイントがノード識別子である連続したセグメントに分割されます。とが2 つの隣接する ID であり、からまでの時計回りの距離が短い場合、ID を持つノードはとの間にあるすべてのキーを所有します。 $\delta (k_{1},k_{2})$ $k_{1}$ $k_{2}$ $i_{1}$ $i_{2}$ $i_{1}$ $i_{2}$ $i_{2}$ $i_{1}$ $i_{2}$

ランデブーハッシュ

ランデブーハッシュ (最高ランダム重み (HRW) ハッシュとも呼ばれる) では、すべてのクライアントが同じハッシュ関数(事前に選択) を使用して、キーをn個の使用可能なサーバーの 1 つに関連付けます。各クライアントには、サーバーごとに 1 つずつ、同じ識別子のリスト ${$ $S$ $1$ $、$ $S$ $2$ $、 ...、$ $S$ $n$ $}$ があります。あるキーkが与えられると、クライアントはn 個のハッシュ重み $w$ $1$ $=$ $h$ $($ $S$ $1$ $、$ $k$ $)、$ $w$ $2$ $=$ $h$ $($ $S$ $2$ $、$ $k$ $)、 ...、$ $w$ $n$ $=$ $h$ $($ $S$ $n$ $、$ $k$ $)$ を計算します。クライアントは、そのキーを、そのキーの最高ハッシュ重みに対応するサーバーに関連付けます。ID を持つサーバーは、そのキーのハッシュ重みが他のどのノードのハッシュ重みよりも高いすべてのキーを所有します。 $h()$ $S_{x}$ $k_{m}$ $h(S_{x},k_{m})$

局所性保存ハッシュ

局所性保存ハッシュは、類似のキーが類似のオブジェクトに割り当てられることを保証します。これにより、範囲クエリをより効率的に実行できますが、コンシステントハッシュを使用する場合とは対照的に、キー (および負荷) がキー空間と参加ピア全体に均一にランダムに分散されているという保証はありません。Self-Chord や Oscar ^{[16]などの DHT プロトコルは、このような問題に対処します。Self-Chord は、オブジェクトキーをピア ID から切り離し、}群知能パラダイムに基づく統計的アプローチを使用して、リングに沿ってキーをソートします。^[17]ソートにより、類似のキーが近隣ノードに格納され、範囲クエリなどの検出手順を対数時間で実行できることが保証されます。Oscar は、ランダムウォークサンプリングに基づいてナビゲート可能なスモールワールドネットワークを構築し、これも対数検索時間を保証します。

オーバーレイネットワーク

各ノードは他のノードへのリンクのセット（隣接ノードまたはルーティングテーブル）を維持します。これらのリンクが一緒になってオーバーレイネットワークを形成します。^{[18]ノードは}ネットワークのトポロジと呼ばれる特定の構造に従って隣接ノードを選択します。

すべての DHT トポロジーは、最も重要な特性のいくつかのバリエーションを共有しています。つまり、任意のキー $k$ について、各ノードは $k を所有するノード ID を持っているか、上記で定義したキー空間距離の観点から$ $k$ に近いノード ID を持つノードへのリンクを持っています。次に、次の貪欲アルゴリズム(必ずしもグローバルに最適というわけではありません)を使用して、任意のキー k の所有者にメッセージを簡単にルーティングできます $。各ステップで、$ $kに最も近い ID を持つ隣接ノードにメッセージを転送します。そのような隣接ノードが存在しない場合は、上記で定義した$ $k$ の所有者である最も近いノードに到達している必要があります。このスタイルのルーティングは、キーベースルーティングと呼ばれることもあります。

基本的なルーティングの正確さ以外に、トポロジに関する 2 つの重要な制約は、リクエストが迅速に完了するように、ルートの最大ホップ数(ルート長) が低くなること、およびメンテナンスのオーバーヘッドが過度にならないように、ノードの最大隣接ノード数 (最大ノード次数) が低くなることを保証することです。もちろん、ルートが短いほど、最大次数が高くなる必要があります。最大次数とルート長の一般的な選択肢は次のとおりです。ここで、 $nは$ Big O 表記法を使用した DHT 内のノード数です。

最も一般的な選択である次数/経路長は、次数/経路長のトレードオフの観点からは最適ではありませんが、このようなトポロジーでは、通常、近隣ノードの選択においてより柔軟性が高まります。多くのDHTは、その柔軟性を利用して、物理的な基盤ネットワークのレイテンシの観点から近い近隣ノードを選択します。一般に、すべてのDHTは、経路長とネットワーク次数のトレードオフを行う、ナビゲート可能なスモールワールドネットワークトポロジーを構築します。^[19] $O(\log n)$

最大経路長は、ノード間の最短経路における最大ホップ数である直径と密接に関係しています。明らかに、ネットワークの最悪の場合の経路長は少なくともその直径と同じ大きさであるため、DHTはグラフ理論の基本である次数/直径のトレードオフ^[20]によって制限されます。貪欲ルーティングアルゴリズムは最短経路を見つけられない可能性があるため、経路長は直径よりも大きくなる可能性があります。^[21]

オーバーレイネットワークのアルゴリズム

ルーティング以外にも、オーバーレイネットワークの構造を利用してDHT内のすべてのノードまたはノードのサブセットにメッセージを送信するアルゴリズムが多数存在します。^[22]これらのアルゴリズムは、アプリケーションがオーバーレイマルチキャスト、範囲クエリ、または統計の収集を行うために使用されます。このアプローチに基づく2つのシステムは、Pastryオーバーレイでフラッディングとランダムウォークを実装するStructella ^[23]と、Chordネットワーク上で動的クエリ検索アルゴリズムを実装するDQ-DHTです。^[24]

安全

DHT は分散化、フォールトトレランス、スケーラビリティを備えているため、集中型システムよりも敵対的な攻撃者に対して本質的に耐性があります。^[曖昧]

大規模な敵対的攻撃者に対して堅牢な分散データストレージのためのオープンシステムは実現可能である。 ^[25]

ビザンチンフォールトトレランスを持つように注意深く設計されたDHTシステムは、現在のほとんどのDHT設計に影響を与えるシビル攻撃と呼ばれるセキュリティ上の弱点から防御することができます。 ^[26]^[27] Whanauはシビル攻撃に耐えられるように設計されたDHTです。^[28]

Kademliaのオリジナル著者の一人である Petar Maymounkov は、システム設計に社会的信頼関係を組み込むことで、シビル攻撃の弱点を回避する方法を提案しました。^[29]コードネーム Tonika またはドメイン名 5ttt としても知られるこの新しいシステムは、「電気ルーティング」と呼ばれるアルゴリズム設計に基づいており、数学者 Jonathan Kelner と共同で作成されました。^[30] Maymounkov は現在、この新しいシステムの包括的な実装に取り組んでいます。しかし、シビル攻撃に対する効果的な防御の研究は一般に未解決の問題と考えられており、毎年、トップクラスのセキュリティ研究会議でさまざまな潜在的な防御が提案されています。^[要出典]

実装

DHT 実装の実際のインスタンスで発生する最も顕著な違いには、少なくとも次のものが含まれます。

アドレス空間は DHT のパラメータです。実際の DHT の多くは 128 ビットまたは 160 ビットのキー空間を使用します。
実際の DHT の中には、SHA-1以外のハッシュ関数を使用するものもあります。
現実の世界では、キーk は、コンテンツアドレス指定可能なストレージを提供するために、ファイル名のハッシュではなくファイルコンテンツのハッシュである可能性があり、そのため、ファイルの名前を変更しても、ユーザーがファイルを見つけられなくなることはありません。
一部の DHT は、異なるタイプのオブジェクトを公開することもあります。たとえば、キーk はノードIDであり、関連データはこのノードへの接続方法を記述できます。これにより、プレゼンス情報の公開が可能になり、IM アプリケーションなどでよく使用されます。最も単純なケースでは、ID はキーkとして直接使用される乱数です(したがって、160 ビットの DHT では、ID は160 ビットの数値で、通常はランダムに選択されます)。一部の DHT では、ノードの ID の公開は、DHT 操作の最適化にも使用されます。
信頼性を向上させるために冗長性を追加できます。(k、データ)キーペアは、キーに対応する複数のノードに格納できます。通常、実際の DHT アルゴリズムでは、1 つのノードを選択するのではなく、i個の適切なノードを選択します。iはDHT の実装固有のパラメータです。一部の DHT 設計では、ノードは特定のキー空間範囲を処理することに同意します。そのサイズは、ハードコードされるのではなく、動的に選択できます。
Kademliaのような高度な DHT の中には、最初に DHT を介して反復検索を実行して適切なノードのセットを選択し、それらのノードにのみput(k, data)メッセージを送信するものがあります。これにより、公開されたメッセージはキーk の格納に適していると思われるノードにのみ送信されるため、無駄なトラフィックが大幅に削減されます。また、反復検索は DHT 全体ではなく少数のノードのみを対象とし、無駄な転送を削減します。このような DHT では、put(k, data)メッセージの転送は、自己修復アルゴリズムの一部としてのみ発生する可能性があります。つまり、ターゲットノードがput(k, data)メッセージを受信したが、kが処理範囲外であり、より近いノード (DHT キー空間の観点から) がわかっていると判断した場合、メッセージはそのノードに転送されます。それ以外の場合、データはローカルにインデックス付けされます。これにより、ある程度自己バランスのとれた DHT 動作が実現されます。もちろん、このようなアルゴリズムでは、反復検索を実行できるように、ノードが DHT にプレゼンスデータを公開する必要があります。
ほとんどのマシンでは、メッセージの送信はローカルハッシュテーブルへのアクセスよりもはるかにコストがかかるため、特定のノードに関する多くのメッセージを 1 つのバッチにまとめることは理にかなっています。各ノードが最大でb 個の操作からなるローカルバッチを持っていると仮定すると、バンドルの手順は次のようになります。各ノードはまず、操作を担当するノードの識別子でローカルバッチをソートします。バケットソートを使用すると、これはO(b + n)で実行できます。ここで、n はDHT 内のノードの数です。1 つのバッチ内に同じキーを対象とする操作が複数ある場合、バッチは送信される前に圧縮されます。たとえば、同じキーの複数の検索を 1 つに減らしたり、複数の増分を 1 つの追加操作に減らしたりできます。この削減は、一時的なローカルハッシュテーブルを使用して実装できます。最後に、操作はそれぞれのノードに送信されます。^[31]

例

DHT プロトコルと実装

アパッチカサンドラ
バトンオーバーレイ
メインラインDHT – BitTorrentが使用する標準DHT（ Khashmirが提供するKademliaに基づく）^[32]
コンテンツアドレスネットワーク(CAN)
コード
コーデ
カデムリア
ペストリー
Pグリッド
リアク
スキュラDB
タペストリー
トムP2P
ヴォルデモート

DHT を使用するアプリケーション

BTDigg : BitTorrent DHT 検索エンジン
Codeen : ウェブキャッシュ
Freenet : 検閲に強い匿名ネットワーク
GlusterFS : ストレージ仮想化に使用される分散ファイルシステム
GNUnet : DHT 実装を含む Freenet のような配布ネットワーク
I2P : オープンソースの匿名ピアツーピアネットワーク
I2P-Bote : サーバーレスで安全な匿名メール
IPFS : コンテンツアドレス可能なピアツーピアのハイパーメディア配信プロトコル
JXTA : オープンソースのP2Pプラットフォーム
LBRY :コンテンツ配信にKademliaの影響を受けたDHTシステムを使用するブロックチェーンベースのコンテンツ共有プロトコル
Oracle Coherence : Java DHT実装上に構築されたインメモリデータグリッド
Perfect Dark :日本のピアツーピアファイル共有アプリケーション
Retroshare：友人同士のネットワーク^[33]
Jami : Kademlia のような DHT に基づく、プライバシー保護音声、ビデオ、チャット通信プラットフォーム
Tox : Skype の代替として機能することを目的としたインスタントメッセージングシステム
Twister :マイクロブログのピアツーピアプラットフォーム
YaCy : 分散検索エンジン

参照

Couchbase Server : memcached プロトコルと互換性のある、永続的で複製されたクラスター化された分散オブジェクトストレージシステム。
Memcached : 高性能な分散メモリオブジェクトキャッシュシステム。
プレフィックスハッシュツリー: DHT を介した高度なクエリ。
マークルツリー: すべての非リーフノードに、その子ノードのラベルのハッシュがラベル付けされたツリー。
ほとんどの分散データストアでは、検索に何らかの形式の DHT が採用されています。
スキップグラフは、 DHT を実装するための効率的なデータ構造です。

参考文献

^ ホタ、チッタランジャン;スリマニ、プラディップ K. (2013-01-11)。分散コンピューティングとインターネット技術: 第 9 回国際会議、ICDCIT 2013、インド、ブバネシュワール、2013 年 2 月 5 ～ 8 日、議事録。スプリンガー。ISBN 978-3-642-36071-8。
^ 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. 2023-07-07 にオリジナルからアーカイブ(PDF)されました。2018-09-18に取得。値には、アドレス、ドキュメント、または任意のデータ項目を指定できます。
^ Liz, Crowcroft; et al. (2005). 「ピアツーピアオーバーレイネットワークスキームの調査と比較」(PDF) . IEEE Communications Surveys & Tutorials . 7 (2): 72–93. CiteSeerX 10.1.1.109.6124 . doi :10.1109/COMST.2005.1610546. S2CID 7971188. 2023-10-05 にオリジナルからアーカイブ(PDF)されました。2019-09-24に取得。
^ Richter, Stevenson; et al. (2009). 「動的クエリモデルがクライアントとサーバーの関係に与える影響の分析」Trends in Modern Computing : 682–701。
^ Searching in a Small World Chapters 1 & 2 (PDF) 、 2012-03-16にオリジナル(PDF)からアーカイブ、2012-01-10に取得
^ 「セクション 5.2.2」(PDF)、分散型情報ストレージおよび検索システム、オリジナル(PDF)から2012-03-16 にアーカイブ、2012-01-10 に取得
^ Ratnasamy, Sylvia; Francis, Paul; Handley, Mark; Karp, Richard; Shenker, Scott (2001-08-27). 「スケーラブルなコンテンツアドレスネットワーク」. SIGCOMM Comput. Commun. Rev . 31 (4): 161–172. doi :10.1145/964723.383072. ISSN 0146-4833.
^ Hari Balakrishnan、M. Frans Kaashoek、David Karger、Robert Morris、Ion Stoica。P2Pシステムでのデータの検索。Wayback Machineに2016年5月19日にアーカイブ。Communications of the ACM、2003年2月。
^ David Cohen (2002年10月1日). 「米国政府が資金を提供する新しいP2Pネットワーク」。New Scientist。2008年4月6日時点のオリジナルよりアーカイブ。 2013年11月10日閲覧。
^ 「MIT、バークレー、ICSI、NYU、ライス大学がIRISプロジェクトを開始」。プレスリリース。MIT。2002年9月25日。2015年9月26日時点のオリジナルよりアーカイブ。 2013年11月10日閲覧。
^ 「Coral によるコンテンツ公開の民主化」(PDF) NSDI 4 2004 2024年 5 月 1日閲覧。
^ R Mokadem、A Hameurlain、AM Tjoa。階層型 DHT システムにおけるメンテナンスオーバーヘッドを最小限に抑えたリソース検出サービス。Wayback Machineに 2022-08-09 にアーカイブ。Proc. iiWas、2010
^ Guido Urdaneta、Guillaume Pierre、Maarten van Steen。DHTセキュリティ技術の調査、Wayback Machineに2023年6月1日アーカイブ。ACM Computing Surveys 43(2)、2011年1月。
^ Moni Naor と Udi Wieder。P2P アプリケーションの新しいアーキテクチャ: 連続-離散アプローチ Archived 2019-12-09 at the Wayback Machine . Proc. SPAA、2003。
^ Gurmeet Singh Manku. Dipsea: モジュラー分散ハッシュテーブル、Wayback Machineに 2004-09-10 アーカイブ。Ph . D. 論文 (スタンフォード大学)、2004 年 8 月。
^ Girdzijauskas, Šarūnas; Datta, Anwitaman; Aberer, Karl (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に取得。
^ Forestiero, Agostino; Leonardi, Emilio; Mastroianni, Carlo; Meo, Michela (2010 年 10 月). 「Self-Chord: 自己組織化分散システムのためのバイオにヒントを得た P2P フレームワーク」. IEEE/ACM Transactions on Networking . 18 (5): 1651–1664. doi :10.1109/TNET.2010.2046745. S2CID 14797120. 2012-07-01 にオリジナルからアーカイブ。 2019-07-28に取得。
^ Galuba, Wojciech; Girdzijauskas, Sarunas (2009)、「ピアツーピアオーバーレイネットワーク：構造、ルーティング、メンテナンス」、LIU, LING ; ÖZSU, M. TAMER (編)、Encyclopedia of Database Systems、Springer US、pp. 2056–2061、doi :10.1007/978-0-387-39940-9_1215、ISBN 9780387399409
^ Girdzijauskas, Sarunas (2009). ピアツーピアの設計はスモールワールドの視点を重ね合わせる。epfl.ch (論文). EPFL. doi : 10.5075/epfl-thesis-4327. 2020-03-03 にオリジナルからアーカイブ。2019-11-11に取得。
^ グラフの（次数、直径）問題、Maite71.upc.es、2012年2月17日にオリジナルからアーカイブ、2012年1月10日に取得
^ Gurmeet Singh Manku、Moni Naor、Udi Wieder。「隣人の隣人を知る: ランダム化された P2P ネットワークにおける先読みの威力」Wayback Machineに 2008-04-20 にアーカイブ。Proc . STOC、2004 年。
^ Ali Ghodsi (2007 年 5 月 22 日). 「分散 k-ary システム: 分散ハッシュテーブル用のアルゴリズム」。2007 年 5 月 22 日時点のオリジナルよりアーカイブ。. KTH-王立工科大学、2006年。
^ Castro, Miguel; Costa, Manuel; Rowstron, Antony (2004 年 1 月 1 日). 「構造化オーバーレイ上に Gnutella を構築すべきか?」(PDF) . ACM SIGCOMM Computer Communication Review . 34 (1): 131. CiteSeerX 10.1.1.221.7892 . doi :10.1145/972374.972397. S2CID 6587291. 2021 年 2 月 14 日時点のオリジナルよりアーカイブ(PDF) . 2019 年9 月 25 日閲覧。
^ Talia, Domenico; Trunfio, Paolo (2010 年12 月)。「分散ハッシュテーブルでの動的クエリの有効化」。Journal of Parallel and Distributed Computing。70 ( 12): 1254–1265。doi :10.1016/ j.jpdc.2010.08.012。
^ Baruch Awerbuch、Christian Scheideler。「スケーラブルで堅牢な DHT に向けて」2006 年。doi : 10.1145/1148109.1148163
^ Maxwell Young、Aniket Kate、Ian Goldberg、Martin Karsten。「ビザンチン攻撃を許容する DHT における実用的な堅牢な通信」Wayback Machineに 2016 年 7 月 22 日にアーカイブ。
^ ナタリア・フェドトワ;ジョルダーノ・オルゼッティ;ルカ・ヴェルトリ。アレッサンドロ・ザッカニーニ。「DHT ベースのピアツーピアネットワークにおける評判管理に関するビザンチン協定」。土井：10.1109/ICTEL.2008.4652638
^ Whanau: シビル耐性分散ハッシュテーブル https://pdos.csail.mit.edu/papers/whanau-nsdi10.pdf 2022-01-25 にWayback Machineにアーカイブ
^ Lesniewski-Laas, Chris (2008-04-01). 「シビル耐性のあるワンホップ DHT」。第 1 回ソーシャルネットワークシステムワークショップの議事録。SocialNets '08。ニューヨーク、ニューヨーク州、米国: Association for Computing Machinery。pp. 19–24。doi : 10.1145/ 1435497.1435501。ISBN 978-1-60558-124-8。
^ Kelner, Jonathan; Maymounkov, Petar (2011-07-22). 「電気ルーティングと同時フローカッティング」.理論計算機科学. アルゴリズムと計算. 412 (32): 4123–4135. doi :10.1016/j.tcs.2010.06.013. hdl : 1721.1/71604 . ISSN 0304-3975.
^ サンダース、ピーター; メルホーン、カート; ディーツフェルビンガー、マーティン; デメンティエフ、ローマン (2019)。シーケンシャルおよびパラレルアルゴリズムとデータ構造: 基本ツールボックス。シュプリンガーインターナショナルパブリッシング。ISBN 978-3-030-25208-3. 2021年8月17日時点のオリジナルよりアーカイブ。2020年1月22日閲覧。
^ Tribler wiki 2010年12月4日アーカイブ、Wayback Machineで2010年1月に取得。
^ Retroshare FAQ 2013-07-17にWayback Machineでアーカイブ、2011年12月取得

外部リンク

Brandon Wiley 著「分散ハッシュテーブル、パート 1」。
分散ハッシュテーブルは、Carles Pairot の 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 調査」。CiteSeerX 10.1.1.111.4197 :DHT (Chord、Pastry、Tapestry など) を含む非構造化および構造化分散オーバーレイネットワークをカバーします。
フィンランドのヘルシンキ大学コンピューターサイエンス学部におけるメインライン DHT 測定。

[1] ホタ、チッタランジャン;スリマニ、プラディップ K. (2013-01-11)。分散コンピューティングとインターネット技術: 第 9 回国際会議、ICDCIT 2013、インド、ブバネシュワール、2013 年 2 月 5 ～ 8 日、議事録。スプリンガー。ISBN 978-3-642-36071-8。

[StoicaEtAl2001-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. 2023-07-07 にオリジナルからアーカイブ(PDF)されました。2018-09-18に取得。値には、アドレス、ドキュメント、または任意のデータ項目を指定できます。

[3] Liz, Crowcroft; et al. (2005). 「ピアツーピアオーバーレイネットワークスキームの調査と比較」(PDF) . IEEE Communications Surveys & Tutorials . 7 (2): 72–93. CiteSeerX 10.1.1.109.6124 . doi :10.1109/COMST.2005.1610546. S2CID 7971188. 2023-10-05 にオリジナルからアーカイブ(PDF)されました。2019-09-24に取得。

[4] Richter, Stevenson; et al. (2009). 「動的クエリモデルがクライアントとサーバーの関係に与える影響の分析」Trends in Modern Computing : 682–701。

[5] Searching in a Small World Chapters 1 & 2 (PDF) 、 2012-03-16にオリジナル(PDF)からアーカイブ、2012-01-10に取得

[6] 「セクション 5.2.2」(PDF)、分散型情報ストレージおよび検索システム、オリジナル(PDF)から2012-03-16 にアーカイブ、2012-01-10 に取得

[Ratnasamy01-7] Ratnasamy, Sylvia; Francis, Paul; Handley, Mark; Karp, Richard; Shenker, Scott (2001-08-27). 「スケーラブルなコンテンツアドレスネットワーク」. SIGCOMM Comput. Commun. Rev . 31 (4): 161–172. doi :10.1145/964723.383072. ISSN 0146-4833.

[8] Hari Balakrishnan、M. Frans Kaashoek、David Karger、Robert Morris、Ion Stoica。P2Pシステムでのデータの検索。Wayback Machineに2016年5月19日にアーカイブ。Communications of the ACM、2003年2月。

[9] David Cohen (2002年10月1日). 「米国政府が資金を提供する新しいP2Pネットワーク」。New Scientist。2008年4月6日時点のオリジナルよりアーカイブ。 2013年11月10日閲覧。

[10] 「MIT、バークレー、ICSI、NYU、ライス大学がIRISプロジェクトを開始」。プレスリリース。MIT。2002年9月25日。2015年9月26日時点のオリジナルよりアーカイブ。 2013年11月10日閲覧。

[11] 「Coral によるコンテンツ公開の民主化」(PDF) NSDI 4 2004 2024年 5 月 1日閲覧。

[12] R Mokadem、A Hameurlain、AM Tjoa。階層型 DHT システムにおけるメンテナンスオーバーヘッドを最小限に抑えたリソース検出サービス。Wayback Machineに 2022-08-09 にアーカイブ。Proc. iiWas、2010

[13] Guido Urdaneta、Guillaume Pierre、Maarten van Steen。DHTセキュリティ技術の調査、Wayback Machineに2023年6月1日アーカイブ。ACM Computing Surveys 43(2)、2011年1月。

[14] Moni Naor と Udi Wieder。P2P アプリケーションの新しいアーキテクチャ: 連続-離散アプローチ Archived 2019-12-09 at the Wayback Machine . Proc. SPAA、2003。

[15] Gurmeet Singh Manku. Dipsea: モジュラー分散ハッシュテーブル、Wayback Machineに 2004-09-10 アーカイブ。Ph . D. 論文 (スタンフォード大学)、2004 年 8 月。

[16] Girdzijauskas, Šarūnas; Datta, Anwitaman; Aberer, Karl (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] Forestiero, Agostino; Leonardi, Emilio; Mastroianni, Carlo; Meo, Michela (2010 年 10 月). 「Self-Chord: 自己組織化分散システムのためのバイオにヒントを得た P2P フレームワーク」. IEEE/ACM Transactions on Networking . 18 (5): 1651–1664. doi :10.1109/TNET.2010.2046745. S2CID 14797120. 2012-07-01 にオリジナルからアーカイブ。 2019-07-28に取得。

[18] Galuba, Wojciech; Girdzijauskas, Sarunas (2009)、「ピアツーピアオーバーレイネットワーク：構造、ルーティング、メンテナンス」、LIU, LING ; ÖZSU, M. TAMER (編)、Encyclopedia of Database Systems、Springer US、pp. 2056–2061、doi :10.1007/978-0-387-39940-9_1215、ISBN 9780387399409

[19] Girdzijauskas, Sarunas (2009). ピアツーピアの設計はスモールワールドの視点を重ね合わせる。epfl.ch (論文). EPFL. doi : 10.5075/epfl-thesis-4327. 2020-03-03 にオリジナルからアーカイブ。2019-11-11に取得。

[20] グラフの（次数、直径）問題、Maite71.upc.es、2012年2月17日にオリジナルからアーカイブ、2012年1月10日に取得

[21] Gurmeet Singh Manku、Moni Naor、Udi Wieder。「隣人の隣人を知る: ランダム化された P2P ネットワークにおける先読みの威力」Wayback Machineに 2008-04-20 にアーカイブ。Proc . STOC、2004 年。

[22] Ali Ghodsi (2007 年 5 月 22 日). 「分散 k-ary システム: 分散ハッシュテーブル用のアルゴリズム」。2007 年 5 月 22 日時点のオリジナルよりアーカイブ。. KTH-王立工科大学、2006年。

[23] Castro, Miguel; Costa, Manuel; Rowstron, Antony (2004 年 1 月 1 日). 「構造化オーバーレイ上に Gnutella を構築すべきか?」(PDF) . ACM SIGCOMM Computer Communication Review . 34 (1): 131. CiteSeerX 10.1.1.221.7892 . doi :10.1145/972374.972397. S2CID 6587291. 2021 年 2 月 14 日時点のオリジナルよりアーカイブ(PDF) . 2019 年9 月 25 日閲覧。

[24] ^ Talia, Domenico; Trunfio, Paolo (2010 年12 月)。「分散ハッシュテーブルでの動的クエリの有効化」。Journal of Parallel and Distributed Computing。70 ( 12): 1254–1265。doi :10.1016/ j.jpdc.2010.08.012。

[25] Baruch Awerbuch、Christian Scheideler。「スケーラブルで堅牢な DHT に向けて」2006 年。doi : 10.1145/1148109.1148163

[26] Maxwell Young、Aniket Kate、Ian Goldberg、Martin Karsten。「ビザンチン攻撃を許容する DHT における実用的な堅牢な通信」Wayback Machineに 2016 年 7 月 22 日にアーカイブ。

[27] ナタリア・フェドトワ;ジョルダーノ・オルゼッティ;ルカ・ヴェルトリ。アレッサンドロ・ザッカニーニ。「DHT ベースのピアツーピアネットワークにおける評判管理に関するビザンチン協定」。土井：10.1109/ICTEL.2008.4652638

[28] Whanau: シビル耐性分散ハッシュテーブル https://pdos.csail.mit.edu/papers/whanau-nsdi10.pdf 2022-01-25 にWayback Machineにアーカイブ

[29] Lesniewski-Laas, Chris (2008-04-01). 「シビル耐性のあるワンホップ DHT」。第 1 回ソーシャルネットワークシステムワークショップの議事録。SocialNets '08。ニューヨーク、ニューヨーク州、米国: Association for Computing Machinery。pp. 19–24。doi : 10.1145/ 1435497.1435501。ISBN 978-1-60558-124-8。

[30] Kelner, Jonathan; Maymounkov, Petar (2011-07-22). 「電気ルーティングと同時フローカッティング」.理論計算機科学. アルゴリズムと計算. 412 (32): 4123–4135. doi :10.1016/j.tcs.2010.06.013. hdl : 1721.1/71604 . ISSN 0304-3975.

[31] サンダース、ピーター; メルホーン、カート; ディーツフェルビンガー、マーティン; デメンティエフ、ローマン (2019)。シーケンシャルおよびパラレルアルゴリズムとデータ構造: 基本ツールボックス。シュプリンガーインターナショナルパブリッシング。ISBN 978-3-030-25208-3. 2021年8月17日時点のオリジナルよりアーカイブ。2020年1月22日閲覧。

[32] Tribler wiki 2010年12月4日アーカイブ、Wayback Machineで2010年1月に取得。

[33] Retroshare FAQ 2013-07-17にWayback Machineでアーカイブ、2011年12月取得