IdeonInternal:IDEON合宿/2004秋
- [MUST] 必ず理解しよう
- 無印: 未判断
- [MAY] できれば/時間があれば
Warm Up: Chord †
- [MUST] I Stoica et al., Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, MIT TR ps,
pdf(local copy)
or Tapestry?
Risson and Moorsとその派生 †
- J. Risson and T. Moors, Survey of Research towards Robust Peer-to-Peer Networks: Search Methods, Technical Report UNSW-EE-P2P-1-1 pdf pdf(local copy)
Semantic Free Index †
読む順番: 基礎やって、方式の話(one for each)やって、比較評価の話。
基礎 (p.8-) †
- [MUST] Plaxton Mesh復習: (Plaxton, Rajaraman et al. 1997), C. Plaxton, R. Rajaram, and A. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 311--320, June 1997
- [MAY] global knowledgeの必要性: (Zhao, Kubiatowicz et al. 2001)
- [MUST] Consistent Hashing: (Karger, Lehman et al. 1997), D. Karger, E. Lehman, F. T. Leighton, M. Levine, D. Lewin, and R. Panigrahy. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 654--663, May 1997., 担当: yatch
- [MAY] SDDS(注目されなかった先行事例): (Litwin, Niemat et al. 1993)
- [MAY] SDDSとChordとの比較: (Litwin 2004a)
比較評価 (p.9-) †
- Fault-free performanceの比較
- [MAY] (Christin and Chuang 2004), N. Christin and J. Chuang. On the cost of participating in a peer-to-peer network. In Proceedings of the 3rd International Workshop on Peer-to-Peer Systems (IPTPS'04), San Diego, CA, February 2004.
- (Rhea Roscoe et al. 2003), Sean Rhea, Timothy Roscoe, and John Kubiatowicz. Structured peerto -peer overlays need application-driven benchmarks. In Proceedings of the Second IPTPS, 2003
- Static dependability
- [MUST] tree, hypercube, butterfly, ring, XOR and hybrid: (Gummadi, Gummadi et al. 2003), The Impact of DHT Routing Geometry on Resilience and Proximity,
by Krishna P. Gummadi, Ramakrishna Gummadi, Steven D. Gribble, Sylvia Ratnasamy, Scott Shenker and Ion Stoica
Proceedings of the ACM SIGCOMM 2003, Karlsruhe, Germany, August 2003., 担当: narupy
- Chord/CAN/De Bruijn: (Loguinov, Kumar et al. 2003), D. Loguinov, A. Kumar, V. Rai, and S. Ganesh, "Graph-Theoretic Analysis of Structured Peer-to-Peer Systems: Routing Distances and Fault Resilience," ACM SIGCOMM, August 2003.
- adaptability: Chord, Tapestry, Pastry, and Tornado: (Hsiao and King 2003) → pdf見つからず‥‥‥
- Dynamic Dependability
- (Li, Stribling et al. 2004), J. Li, J. Stribling, T. M. Gil, R. Morris, and F. Kaashoek. Comparing the performance of distributed hash tables under churn. In Proc. IPTPS, 2004.
- Latency/bandwidth tradeoff (Gil, Kaashoek et al. 2003)
- Formal analysis
- [MAY] Many join/leave: (Li and Plaxton 2002), X. Li and C. G. Plaxton. On name resolution in peer-to-peer networks. In Proceedings of the 2nd Workshop on Principles of Mobile Computing, pages 82--89, October 2002.
- [MAY] Chord atomicity: (Lynch, Malkhi et al. 2002)
- [MAY] in limited environment: (Lynch and Stoica 2004)
- API Specifications
- (Dabek, Zhao et al. 2003): Frank Dabek, Ben Zhao, Peter Druschel, and Ion Stoica. Towards a common API for structured peer-to-peer overlays. In IPTPS'03, Berkeley, CA, February 2003.
- (Awerbuch and Scheideler 2003): B. Awerbuch and C. Scheideler, Peer-to-peer systems for prefix search, In Proc. 22nd ACM Symposium on Principles of Distributed Computing (PODC), 2003.
- (Huebsch, Hellerstein et al. 2003)
- Churn対策
- (Rhea, Geels et al. 2004), Sean Rhea and Dennis Geels, University of California, Berkeley; Timothy Roscoe, Intel Research, Berkeley; John Kubiatowicz, University of California, Berkeley, Handling Churn in a DHT USENIX 2004 Annual Technical Conference, General Track
方式: Plaxton Trees (p.10) †
- Pastry: (Rowstron and Druschel 2001a), A. Rowstron and P. Druschel, "Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems". IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), Heidelberg, Germany, pages 329-350, November, 2001
方式: Rings (p.11) †
- chordはwarm upでやる
- [MAY] Distributed K-ary Search(DKS): (Alima, El-Ansary et al.)
方式: Tori (pp.11-12) †
- [MAY] (Ratnasamy, Hardley et al. 2001), Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker. A scalable content-addressable network. In Proc. ACM SIGCOMM 2001, August 2001.
方式: Butterflies (p.12) †
- [MUST] Viceroy: (Malkhi, Naor et al. 2002), MALKHI, D., NAOR, M., AND RATAJCZAK, D. Viceroy: A scalable and dynamic emulation of the butterfly. In Proceedings of the 21st annual ACM symposium on Principles of distributed computing (2002), ACM Press., 担当: com@tera
方式: de Bruijn Graphs (pp.12-13) †
- [MUST] Koorde: (Kaashoek and Karger 2003), M. F. Kaashoek and D. R. Karger. Koorde: A simple degree-optimal distributed hash table. In Proc. 2nd IPTPS, Berkeley, CA, Feb. 2003, 担当: ydoi
方式: Skip Graphs (pp.13-14) †
長いけど、Harveyの方が詳細に書いてあるので良いかも。
- [MUST] (Harvey, Joens et al. 2003a), HARVEY, N. J. A., JONES, M. B., SAROIU, S., THEIMER, M., AND WOLMAN, A. Skipnet: A scalable overlay network with practical locality properties. In Proceedings of USITS (Seattle, WA, March 2003), USENIX., 担当: ydoi
- (Aspnes and Shah 2003), James Aspnes, Gauri Shah, Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2003, pp. 384-393. Submitted to Journal of Algorithms.
Semantic Index †
- [MAY] RDBMS in up to 1000nodes: (Stonebraker, Aoki et al. 1996; Loo, Hellerstein et al. 2004)
- xFS関連？: (Gribble, Brewer et al. 2000)
- CDNっぽい？: (Hellerstein 2003)
Keyword Lookup †
- Gnutella QRT: (Singla and Rohrs 2002)
- Gaia Random Walk: (Chawathe, Ratnasamy et al. 2003)
- Key-to-Node bind (not Document-to-Node): (Shi, Guangwen et al. 2004)
- comprehensive(exhaustive) keyword search / Bitzipper: (Daswani, Garcia-Molina et al. 2003)
Peer Information Retrieval †
- (Bawa, Manku et al. 2003)
Peer Data Management †
- (Tatarinov and Halevy 2004)
Search †
(正直、ここは今回は手付かずかもしれません‥‥‥ 担当者募集中 : YusukeDoi)
Range Queries †
Multi-Attribute Queries †
Join Queries †
Aggregation Queries †
Security and Trust (Figure 1 Classification of P2P Research Literature から) †
もっと絞り込みますのでお待ちを…。
評判 †
- [MUST] (Blaze, Feigenbaum, et al. 2004) "Trust and Reputation in P2P networks." http://www.neurogrid.net/twiki/bin/view/Main/ReputationAndTrust
- P2P におけるトラストの第一線研究者達自身によるサーベイ
- (Damiani, di Vimercati, et al. 2002) "A reputation-based approach for choosing reliable resources in peer to peer networks," Proceedings of the 9th conference on computer and communications security: 207-216
- 分散ポーリングによって評判を取得することによって悪意のあるコンテント (virus とか) の拡散を防ぐ XRep プロトコルの説明 (Gnutella 上)。
- フェーズ
- resource searching → resource selection → vote polling → vote evaluation → best servent check → resource downloading
- (Sieka, Kshemkalyani et al. 2004) "On the Security of Polling Protocols in Peer-to-Peer Systems,"
Proceedings of the Fourth IEEE International Conference on Peer-to-Peer Computing, August.
- Gnutella における評判プロトコルを改善。
- 過去に提案されたプロトコルの脆弱性 (vote におけるなりすましなどが可能) を指摘し、改善したプロトコルを提案する。
- (Papaioannou and Stamoulis 2004) "Effective Use of Reputation in Peer-to-Peer Environments," Fourth International Workshop on Global and Peer-to-Peer Computing, April 2004.
- (Selcuk, Uzun, et al. 2004) "A Reputation-based Trust Management System for P2P Networks," Fourth International Workshop on Global and Peer-to-Peer Computing, April 2004.
インセンティブ †
- (Buragohain, Agrawal, et al. 2003) "A game theoretic framework for incentives in P2P systems." Proceedings of the Third International IEEE Conference on Peer-to-Peer Computing, 1-3 Sept 2003: 48-56
- [MAY] (Schneidman and Parks 2003) "Rationality and Self-Interest in Peer to Peer Networks," Second International Workshop on Peer-to-Peer Systems (IPTPS 03).
- P2P ネットワークにおいて利己的なノードが巻き起こす問題を整理。
- 論文の 3つのゴール
- 合理性 (利己的であること) が P2P において現実の問題であることを納得させる。
- 道具としてのメカニズムデザインの紹介。
- 3つのオープンプロブレムの説明。
- 戦略的なノードがいる場合、ネットワークトポロジはメッセージ転送にどう影響するか？
- 分散システムにおいてメカニズムデザインが保証を行える範囲は？また、最低限の支援テクノロジー (catch-and-punish など) とは？
- 戦略的なノードの分布に関する前提を設けることで、メカニズムデザインはどう作りやすくなるか？
- (Anagnostakis and Greenwald 2004) "Exchange-based Incentive Mechanism for Peer-to-Peer File Sharing," Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS 2004), March 23-26. Tokyo
- 交換ベースのインセンティヴメカニズム。
- (推移的に) 同時に、対称的に、サービスを提供してくれるピアからのサービス要求を優先的に処理する。
- 多角交換を前提: 環を発見する。
- (Feldman, Lai, et al 2004) "Robust Incentive Techniques for Peer-to-Peer Networks," ACM E-Commerce Conference (EC'04). May. ,担当: youki-k
- GPD (一般化された囚人のジレンマ) により P2P システムをモデル化、相互判断関数により、様々なインセンティヴ・テクニックを導出する。
- P2P の抱える問題
- 大きな人口と激しい (分のオーダーでの) 構成員の入れ替わり
- 利益の非対称性
- ゼロコスト・アイデンティティ (ホワイトウォッシュ可能)
- サービス提供者の差別的な選択 (悪者を選ばない)
- 履歴の共有
- 主観的評価
- 見知らぬ他人への適応的ポリシー
- 短期履歴
- (Daswani, Gracia-Molina et al. 2003) "Open Problems in Data-sharing Peer-to-peer Systems," The 9th International Conference on Database Theory (ICDT 2003).
信用・公平性 †
- (Caronni and Waldvogel 2003) "Establishing trust in distributed storage providers," Proceedings of the Third International IEEE Conference on Peer-to-Peer Computing. 1-3 Sept 2003: 128-133
- 事前の信用付けや鍵交換を用いずに、複製の所持者に対して信用を形成するための軽量な方法を紹介。
- 正直な複製所持者の方が、はるかに少ないリソースしか要求されない。
- 問題: 複製を持っていると嘘をつきたい人には、次の選択肢がある。
- ハッシュ値を計算し、その値だけ持つ。
- 検証要求を、正しい複製保持者に転送する。
- 検証要求を、共謀している複製保持者に転送する。
- 検証要求に応えるに足るコンテントだけを、正しい複製保持者からダウンロードする。
- (Marti, Genesan, et al. 2004) "DHT Routing using Social Links," The 3rd International Workshop on Peer-to-Peer Systems, February 26-27
- 社交的なリンクに関連づけられている信用は P2P ネットワークにどう活用できるか。
- 社交的なリンクを用いた DHT (SPROUT: Social Path ROUTing) を提案。
- Chord 上に実現 (Chord に、オンラインである友だちへのリンクを追加)。
- アルゴリズム (k を検索)
- k に内輪で最も近い ID を持つ友だちを見つける。
- 見つかったら、その友だちにメッセージを転送する (再帰する)。
- 見つからなかったら、Chord のアルゴリズムを用いる。
- (Bawa, Sun, et al. 2004) "Peer-to-peer research at Stanford," ACM SIGMOD Record 32(3): 23-28. Sept
- (Berket, Essiari et al. 2004) "PKI-Based Security for Peer-to-Peer Information Sharing," Proceedings of the Fourth IEEE International Conference on Peer-to-Peer Computing, 25-27 August.
- 情報通信の秘匿性や完全性を求めるコミュニティで使用可能な一連のセキュリティメカニズムを紹介。
- [MAY] (Cox and Noble 2003) "Samsara: honor among thieves in peer-to-peer storage." Proceedings of the nineteenth ACM symposium on Operating System Principles
- 信用できる第三者も、対称的なストレージ使用も、支払いも、証明されたアイデンティティも用いずに公正な P2P ストレージシステムを構築。
- ピアのストレージを要求する場合は「クレーム」を保持することに合意。
- クレーム: ストレージの約束。
- ノードのチェインにクレームをフォワードして、環を形成するとクレームは破棄できる。← WAT か？
- 監査に応えない悪者は「確率的」に処罰される。
- 処罰: データの削除。
- 障害により応えられない場合も、複製が徐々に削除されていくことにより対応。
- [MAY] (Ngan, Wallach, et al. 2003) "Enforcing Fair Sharing of Peer-to-Peer Resources," Second International Workshop on Peer-to-Peer Systems (IPTPS 03)
- 悪者が協調する環境を想定した、リソースのフェアな共有のためのアーキテクチャを提案。
- 各ノードに、監査可能な使用記録の公開を義務づける。
- 各ノードには正直になることへのインセンティヴがある。
- モデル
- 各ノードは、自分がローカルディスクで提供しているだけのネットワークストレージを使用できる。
- 使用記録を公開 (提供するスペース、保存ファイルのローカル/リモートリスト) し、ランダムな相手を互いに監査 (リモートリストに載っていないファイルは削除して構わない)。
- (Ramaswamy and Liu 2003) "FreeRiding?: A New Challenge for Peer-to-Peer File Sharing Systems," Proceedings of the 2003 Hawaii International Conference on System Sciences (P2P Track) HICSS 2003.
- ユーティリティ関数ベースのフリーライディングの制御。
- ユーティリティ (ユーザがシステムに役立っている度合い) を測るための 3大要素
- 共有しているファイルの数
- 共有しているデータのサイズ
- 共有しているファイルのポピュラリティ
- [MAY] (Feldman, Papadimitriou, et al. 2004) "Free-Riding and Whitewashing in Peer-to-Peer Systems,"
3rd Annual Workshop on Economics and Information Security (WEIS04), May
- フリーライダを特定したり、罰するためのメカニズム。
- ホワイトウォッシャが存在する場合も想定。
- 罰則がすべての新入りに対して適用される場合でも、入れ替わりが激しくなければシステムの性能は落ちないという結果を得る。
匿名性・プライバシー †
- [MUST] (Clarke, Sandberg et al. 2001) "Freenet: A Distributed Anonymous Information Storage and Retrieval System," International Workshop on Design Issues in Anonymity and Unobservability.
- 著者と読者の匿名性を維持しつつデータの公開、複製、取得を可能にする。
- 5つのゴール:
- プロデューサとコンシューマの双方の匿名性
- 否認可能性
- 第三者によるアクセス拒否への耐性
- 効率的な動的ストレージおよびルーティング
- 機能の完全な分散
- ファイルは SHA-1 等のハッシュ関数により生成するキーにより識別される。
- サブスペース (鍵ペアにより識別される) キーにより名前空間を分離。
- サブスペースへのファイルの保存はサブスペースを識別する秘密鍵での署名が必要
- コンテントキーによりファイルそのものを識別。
- サブスペースキーと組み合わせることによりファイルのバージョンを表現可能。
- 経路情報を各ノードが蓄積・学習。
- 各ノードにてキャッシュを作成。
- 耐故障性: 30% のノードが落ちても OK (シミュレーション)。
- 匿名のため、健全性に問題があり得ることは著者らも認識。
- (Daswani, Gracia-Molina et al. 2003) "Open Problems in Data-sharing Peer-to-peer Systems," The 9th International Conference on Database Theory (ICDT 2003).
- (Fiat and Saia 2002) "Censorship resistant peer to peer content addressable networks," Proceedings of the 13th annual ACM-SIAM symposium on discrete algorithms.
- n 個のデータを n 個のノードを通してアクセス可能にする耐検閲ネットワーク。
- 耐スパム性を持つ変形版も提案。
- スパム: ここでは、検索されたデータの代わりに別のデータを返すこと。
- [MAY] (Freedman and Morris 2002) "Tarzan: a peer-to-peer anonymizing network layer." Proceedings of the 9th ACM Conference on Computer and Communications Security.
- Chaum の mix のような仕組みにより匿名性を実現しつつ IP サービスを提供するレイヤ。
- 5つのゴール
- アプリケーションからの独立 (IP トンネルを提供)。
- 悪意のあるノードからの匿名性。
- sender/recipient anonymity (あるメッセージの sender/recipient として特定されない)
- anonymity set: 可能な送信者の集合 - 大きいとより匿名性が高い。
- relationship anonymity (ふたつのホストが互いと通信していると特定されない)
- 耐故障性。
- 性能。
- 大域盗聴者からの匿名性。
- (Hazel and Wiley 2002) "Achord: A Variant of the Chord Lookup Service for Use in Censorship Resistant Peer-to-Peer Publishing Systems," Proceedings of the Second International Conference on Peer to Peer Computing. ,担当: narupy
- Chord を耐検閲パブリッシングシステムに適用する上での問題点を分析し、必要な変更を施した Achord を提案。
- 耐検閲パブリッシングシステムが満たすべき性質
- 素性を明かさずにデータを挿入できる。
- 素性を明かさずにデータを取得できる。
- ノードを、特定のドキュメントを担う役割を持つ者としてはネットワークに挿入しにくい。
- あるドキュメントを担うノードを特定しにくい (Chord はこれを満足できない)。
- Achord ではノードではなく値をルックアップすることで最後の性質を満たす。
- (Serjantov 2002) "Anonymizing Censorship Resistant Systems," Proceedings of the Second International Conference on Peer to Peer Computing, MIT Faculty Club
- 耐検閲アーキテクチャの提案。
- ドキュメントの保存者の役割を、ユーザから見えるマシンから分離。
- 既存の P2P ファイルシステム上に実装可能。
- Chaum, "Untraceable electronic mail, return addresses and digital pseudonyms" のアイデアに基づく。
- 公開者はファイルを分解し、オニオンを形成して、転送者に渡す。
- (Singh and Liu 2003) "TrustMe?: anonymous management of trust relationships in decentralized P2P systems," Proceedings of the Third International IEEE Conference on Peer-to-Peer Computing.
- (評判に基づく) 信用値の管理のための、匿名性を維持するプロトコルを提案。
- 問題
- 信用値はどこに格納されるべきか。
- 他のピアの信用値には、どのようにしてセキュアにアクセスできるか。
- あるピアの信用値は、ランダムに選ばれたピアが保持 (ブートストラップサーバが必要)。
- あるピアの信用値を得るためにはブロードキャストする。
脆弱性 †
- (Daswani and Garcia-Molina 2002) "Query-flood DoS attacks in gnutella," Proceedings of the 9th ACM Conference on Computer and Communications Security.
- Gnutella のネットワークにおける DoS 攻撃の影響を理解するために適したトラフィックモデルを説明し、シミュレーションによって分析する。
- ポリシーによりダメージはかなり変わってくる。
- [MAY] (O'Donnel and Vaikuntanathan 2004) "Information Leak in the Chord Lookup Protocol," Proceedings of the Fourth IEEE International Conference on Peer-to-Peer Computing, August
- 悪意のある中間ノードは、P2P ネットワークのトラフィックを観察することで、ピアに関するどのような情報を取得できるのか、という疑問に対し、具体的に Chord を分析。
- とりあえず受動的な観察者だけを考えている。
- 結果
- 要求元の匿名性は意外と守られている。
- ロケーションキャッシングはデータキャッシングよりも少ないリソースで匿名性の向上に効果がある。
- [MUST] (Sit and Morris 2002) "Security Considerations for Peer-to-Peer Distributed Hash Tables," First International Workshop on Peer-to-Peer Systems (IPTPS). ,担当: youki-k
- 問題の種類
- 既存のシステムでの例
- 設計指針の提案
- 前提
- 悪者は、第三者攻撃 (盗聴と改竄) は行われないが、プロトコルには従わない。
- 悪者は、共謀しうる。
- ルーティング攻撃
- 間違ったルーティングを行う。
- 間違ったアップデートを行う。
- 偽のオーバレイにジョインさせる。
- ストレージ攻撃
- その他の攻撃
- 一貫性のない振る舞い (近所に対しては善人、等)
- DoS
- ゴミパケットの送信
- ジョインとリーヴを高速に反復
- 情報の改竄 (正規のルートを通って、間違った情報を返す)
- 検証可能なシステム不変項を定義せよ！ (そして検証せよ)
- 検索元がルックアップの進行を観察できるようにせよ！
- 検証可能な方法でノードにキーを付与せよ！
- ルーティングでのサービス提供者の選択は悪用されうる。
- ランダムなクエリによって経路表をクロスチェックせよ
- 単一点に責任を負わすな！
- (Surridge and Upstill 2003) "Grid security: lessons for peer-to-peer systems," Proceedings of the Third International IEEE Conference on Peer-to-Peer Computing.
その他 †
- (Josephson, Sirer et al. 2004) "Peer-to-Peer Authentication with a Distributed Single Sign-On Service." The 3rd International Workshop on Peer-to-Peer Systems. ,担当: youki-k
- 複数の管理ドメインに分かれて存在しうる認証サーバを組み合わせてチェックすることでクライアントを認証する。
- (Zhang, Lai et al. 2004) "A Transport Layer Approach for Improving End-to-End
Performance and Robustness Using Redundant Paths." The Advanced Computing Systems Association (USENIX). ,担当：shun
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
