- 追加された行はこの色です。
- 削除された行はこの色です。
[[IDEON合宿/2004秋]]
#contents
- [''MUST''] 必ず理解しよう
- 無印: 未判断
- [MAY] できれば/時間があれば
*Warm Up: Chord [#j6847dcb]
- [''MUST''] I Stoica et al., Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, MIT TR [[ps:http://www.pdos.lcs.mit.edu/chord/papers/chord-tn.ps]], &ref(chord-tn.pdf,,pdf(local copy));
or Tapestry?
*Risson and Moorsとその派生 [#u4734d0b]
- J. Risson and T. Moors, Survey of Research towards Robust Peer-to-Peer Networks: Search Methods, Technical Report UNSW-EE-P2P-1-1 [[pdf:http://uluru.ee.unsw.edu.au/~john/tr-unsw-ee-p2p-1-1.pdf]] &ref(tr-unsw-ee-p2p-1-1.pdf,,pdf(local copy));
網羅的に攻めるのも大切なのですが、時間も大切なのでSemantic-Free Indexを
中心に、あとはちょっとづつ基本的な所をなめる方針で。
** Semantic Free Index [#d6ad8063]
読む順番: 基礎やって、方式の話(one for each)やって、比較評価の話。
*** 基礎 (p.8-) [#t60c4cab]
- [''MUST''] Plaxton Mesh復習: [[(Plaxton, Rajaraman et al. 1997):http://citeseer.ist.psu.edu/plaxton97accessing.html]], 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):http://citeseer.ist.psu.edu/karger97consistent.html]], 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
- [''MUST''] Consistent Hashing: [[(Karger, Lehman et al. 1997):http://citeseer.ist.psu.edu/karger97consistent.html]], 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-) [#ze08ef5b]
- Fault-free performanceの比較
-- [MAY] [[(Christin and Chuang 2004):http://citeseer.ist.psu.edu/644731.html]], 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):http://citeseer.ist.psu.edu/rhea03structured.html]], 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):http://www.cs.washington.edu/homes/gummadi/]], 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.
-- Chord/CAN/De Bruijn: [[(Loguinov, Kumar et al. 2003):http://irl.cs.tamu.edu/people/dmitri/]], 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):http://citeseer.ist.psu.edu/636620.html]], 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)
--- http://www.pdos.lcs.mit.edu/p2psim/ : citeされた先は実装でした‥‥‥ :-)
- Formal analysis
-- [MAY] Many join/leave: [[(Li and Plaxton 2002):http://citeseer.ist.psu.edu/564045.html]], 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):http://citeseer.ist.psu.edu/562396.html]]: 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):http://www.cs.jhu.edu/~scheideler/projects/secure_P2P/]]: 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):http://www.usenix.org/events/usenix04/tech/general/rhea.html]], 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) [#y36de84f]
- Pastry: [[(Rowstron and Druschel 2001a):http://research.microsoft.com/~antr/Pastry/pubs.htm]], 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) [#h520d827]
- chordはwarm upでやる
- [MAY] Distributed K-ary Search(DKS): (Alima, El-Ansary et al.)
*** 方式: Tori (pp.11-12) [#y3ab50b6]
- [MAY] [[(Ratnasamy, Hardley et al. 2001):http://citeseer.ist.psu.edu/ratnasamy01scalable.html]], 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) [#u66f9c79]
- [''MUST''] Viceroy: [[(Malkhi, Naor et al. 2002):http://citeseer.ist.psu.edu/malkhi02viceroy.html]], 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.
*** 方式: de Bruijn Graphs (pp.12-13) [#accc9e7d]
- [''MUST''] Koorde: [[(Kaashoek and Karger 2003):http://citeseer.ist.psu.edu/kaashoek03koorde.html]], M. F. Kaashoek and D. R. Karger. Koorde: A simple degree-optimal distributed hash table. In Proc. 2nd IPTPS, Berkeley, CA, Feb. 2003
*** 方式: Skip Graphs (pp.13-14) [#v58a5a0f]
長いけど、Harveyの方が詳細に書いてあるので良いかも。
- [''MUST''] [[(Harvey, Joens et al. 2003a):http://citeseer.ist.psu.edu/581515.html]], 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.
- [[(Aspnes and Shah 2003):http://cs-www.cs.yale.edu/homes/shah/html/pubs/skip-graphs.html]], James Aspnes, Gauri Shah, Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2003, pp. 384-393. Submitted to Journal of Algorithms.
** Semantic Index [#cca5a5a6]
- [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 [#z23a2996]
- 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 [#n144dca5]
- (Bawa, Manku et al. 2003)
*** Peer Data Management [#wbff8fc4]
- (Tatarinov and Halevy 2004)
** Search [#i6bed30c]
(正直、ここは今回は手付かずかもしれません‥‥‥ 担当者募集中 : YusukeDoi)
*** Range Queries [#d8ba9f12]
*** Multi-Attribute Queries [#i9319e0c]
*** Join Queries [#rdda3a65]
*** Aggregation Queries [#u7ebffd9]
** Security and Trust (Figure 1 Classification of P2P Research Literature から) [#p194ae4f]
もっと絞り込みますのでお待ちを…。
*** 評判 [#m4d51005]
- (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
- (Blaze, Feigenbaum, et al. 2004) "Trust and Reputation in P2P networks." http://www.neurogrid.net/twiki/bin/view/Main/ReputationAndTrust
- (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.
*** インセンティブ [#f49d1159]
- (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
- (Schneidman and Parks 2003) "Rationality and Self-Interest in Peer to Peer Networks," Second International Workshop on Peer-to-Peer Systems (IPTPS 03).
- (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.
- (Daswani, Gracia-Molina et al. 2003) "Open Problems in Data-sharing Peer-to-peer Systems," The 9th International Conference on Database Theory (ICDT 2003).
*** 信用・公平性 [#rbf4b957]
- (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
- (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.
- (Cox and Noble 2003) "Samsara: honor among thieves in peer-to-peer storage." Proceedings of the nineteenth ACM symposium on Operating System Principles
- (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.
- (Feldman, Papadimitriou, et al. 2004) "Free-Riding and Whitewashing in Peer-to-Peer Systems,"
3rd Annual Workshop on Economics and Information Security (WEIS04), May
*** 匿名性・プライバシー [#f794f1a0]
- (Clarke, Sandberg et al. 2001) "Freenet: A Distributed Anonymous Information Storage and Retrieval System," International Workshop on Design Issues in Anonymity and Unobservability.
- (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.
- (Freedman and Morris 2002) "Tarzan: a peer-to-peer anonymizing network layer." Proceedings of the 9th ACM Conference on Computer and Communications Security.
- (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.
- (Serjantov 2002) "Anonymizing Censorship Resistant Systems," Proceedings of the Second International Conference on Peer to Peer Computing, MIT Faculty Club
- (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.
*** 脆弱性 [#jafecf6c]
- (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.
- (Daswani and Garcia-Molina 2002) "Query-flood DoS attacks in gnutella," Proceedings of the 9th ACM Conference on Computer and Communications Security.
- (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
- (Sit and Morris 2002) "Security Considerations for Peer-to-Peer Distributed Hash Tables," First International Workshop on Peer-to-Peer Systems (IPTPS).
- (Surridge and Upstill 2003) "Grid security: lessons for peer-to-peer systems," Proceedings of the Third International IEEE Conference on Peer-to-Peer Computing.
*** その他 [#s5f8b388]
- (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.
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
