現実世界の条件に適応する分散ハツシュテーブル

摘要

今世紀最初の年に分散システムの理論的世界に登場した分散ハツシュテーブル（DHT: Distributed Hash Table）は，Key-Value型検索（キーに対応する値をルックアップするサービス）を規模拡大性かつ可塑性(特に，壞れても，残った部分の変化により機能を維持できる性質）をもちつつ提供することを可能とし，その後の分散データ構造及びアルゴリズムの研究の基盤として用いられてきた。しかし，その圧倒的な関連論文の数と比較して，実用された例は極端に少ない。DHTが現実の問題に対応するためには，実社会での応用が要求する性能（検索や経路表の維持の効率性）と機能（範囲検索等）の条件を満たすとともに，現実に運用されているネットワークにおける様々な制約（NAT: Network Address Translation等）を乗り越える必要がある.本論文では，DHTがこれらの困難を克服し現実の問題の解決に寄与できるための要素技術を調査・解説する。