論文翻訳: Skip Graphs
Abstract
Skip Graph は、要素を格納する分散システムでバランスツリーの全機能を提供する、Skip List に基づく新しい分散データ構造である。要素はいつでも失敗する可能性のある別々のノードに格納される。これらは peer-to-peer ネットワークでの検索に使用されるように設計されており、キーの順序付けに基づいてクエリーを実行する機能を提供することで、ハッシュテーブル機能のみを提要する既存の検索ツールを改善している。Skip List や他のツリーデータ構造とは異なり、Skip Graph には高度な回復力があり、接続性を失うことなくフェイルしたノードの大部分を許容する。さらに、新しい要素の構築と挿入、スキップグラフの検索、およびノード障害によって発生したデータ構造内のエラーの検出と修復は、単純で直線的なアルゴリズムを使用して行うことができる。
1 Introduction
P2P ネットワークは共有リソースを効率的に配置するために使用される中央機関をもたない分散システムである。そのようなシステムはインターネットアプリケーションとして短期間で非常にポピュラーなものとなった。最近の P2P 研究の調査では、非中央化、スケーラビリティ、耐障害性、自己安定化、データの利用可能性、負荷分散、ピアノードの動的アドレスや削除、効率的で複雑なクエリー検索、検索への地理情報の埋め込み、検索での空間的および時間的局所性の活用、といった P2P ネットワークに望まれている機能が多く生じている。しかし Napster [NAP], Gnutella [GNU], Freenet [FRE] などの初期のシステムはこれらの機能をほとんどサポートしておらず、中央サーバの使用 (Napster) やネットワークフラッディングによる検索実行に起因する高いメッセージ複雑さ (Gnutella) のために拡張不可能であることは明らかだった。Freenet のパフォーマンスを評価することは難しいが、それは検索の完了時間を明確に保証しておらず、アクセス可能なデータを見逃す余地がある。
1.1 Our approach
1.2 Model
アルゴリズムのモデルについて簡単に説明する。通信チャネルを介してメッセージを送信することによってすべてのプロセスが互いに通信するメッセージパッシング環境を想定する。このシステムは部分的に同期している、つまりメッセージの伝達遅延に固定上限 (タイムアウト) が存在する。プロセスはクラッシュすることができる、つまり時期尚早に停止しクラッシュは恒久的である。ノードという用語は特定のマシンで実行されているプロセスを表すのに使用する。各メッセージは配信されるのに最大で単位時間がかかり、マシンの内部処理には時間がかかると仮定する。
2 Skip graphs
2.1 Algorithms for a skip graph
2.1.1 The search operation
2.1.1 The insert operation
3 Repair Mechanism
3.1 Maintaining the invariant
3.2 Restoring skip graph constraints
4 Fault Tolerance
4.1 Adversarial failures
4.2 Random failures
5 Load balancing
6 Conclusion
References
参考文献
- James Aspnes, Gauri Shah (2003) Skip Graphs