Self-organizing Access Structures for P2P Information Systems




Our first approach is based on an access structure that we call P-Grid (Peer-Grid). The P-Grid access structure relies on a virtual search tree that is distributed among the peers. Each peer is responsible for one part of the tree, which is described by its path, meaning that the peer has specialized for the corresponding data. P-Grid structure provides efficient search (O(log2n)). An interesting question is which mechanisms can be used for peer’s specialization and growth of the P-Grid tree structure. For solving this problem, different bio-inspired or economic principles can be exploited.

Some examples of popular P2P systems include Gnutella and Freenet. Gnutella doesn’t rely on an indexing mechanism. As a consequence search requests are broadcasted over the network, which results in a large amount of traffic over the network. Freenet makes replication of the files during the inserting and the searching. Currently, we are doing evaluation of the performances of P-Grid, Freenet and Gnutella based on simulation.


This project is conducted in the framework of P-Grid, a project in LSIR aiming at a platform for P2P information management. The project is financially supported by Swiss National Science Foundation under contract number 2100-064994.01




11.6.2001, Informatik Kolloquium ETHZ, Zürich, "Data Access in Peer-To-Peer Information Systems", Karl Aberer, EPFL.

Interesting Literature:

[1] E. Adar and B.A. Huberman: Free riding on Gnutella Technical Report, Xerox PARC, 10 Aug 2000.

[2] D. Clark: Face-to-Face with Peer-to-Peer Networking IEEE Computer, January 2001.

[3] Ian Clarke et al. Freenet: A Distributed Anonymous Information Storage and Retrieval System. Designing Privacy Enchancing Technologies: International Workshop on Design Issues in Anonymity and Unobservability. LNCS 2009, Springer, 2001.

[4] F. Dabek et al. Building Peer-to-peer Systems with Chord, a Distributed Lookup Service. Proc. 8th Workshop on Hot Topics in Operating Systems (HotOS-VIII), 2001

[5] D.F. Ferguson, C. Nikolau and Y. Yemini: An Economy for Managing Replicated Data in Autonomous Decentralized Systems Proc. Int. Symp. on autonomous Decentralized Sys.(ISAD '93), Kawasaki, Japan, 1993.

[6] T. Johnson, P. Krishna: Lazy Updates for Distributed Search Structure SIGMOD Conference 1993: 337-346.

[7] M. A. Jovanovic, Fred S. Annexstein and Kenneth A. Berman. Scalability Issues in Large Peer-to-Peer Networks - A Case study of Gnutella. University of Cincinnati, Laboratory for Networks and Applied Graph Theory, 2001.

[8] Jon Kleinberg. The Small-World Phenomenon: An Algorithmic Perspective. Technical report 99-1776. Cornell Computer Science, October 1999.

[9] B. Kröll, P. Widmayer Distributing a Search Tree Among a Growing Number of Processors  ACM SIGMOD Conference 1994: 265-276

[10] B. Kröll, P. Widmayer Balanced Distributed Search Trees Do Not Exist WADS 1995: 50-61

[11] John Kubiatowicz et al. OceanStore: An Architecture for Scale Persistent Storage. Proc of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000), November 2000

[12] W. Litwin, M. Neimat, D.A. Schneider: RP*: A Family of Order Preserving Scalable Distributed Data Structures. VLDB 1994: 342-353

[13] C. Greg Plaxton, Rajmohan Rajaraman and Andrea Richa, accessing Nearby Copies of Replicated Objects in a Distributed Environment. Proc. ACM Symposium on Parallel Algorithms and Architecture, June 1997

[14] Sylvia Ratnasamy et al. A Scalable Content-Addressable Network. Proceedings of the ACM SIGCOMM, 2001

[15] Kunwadee Sripanidkulchai. The popularity of Gnutella queries and its implications on scalability, February 2001.

[16] M. Stonebraker, P.M. Aoki, W. Litwin, A. Pfeffer, A. Sah, J. Sidell, C. Staelin, A. Yu: Mariposa A Wide-Area Distributed Database System VLDB Journal 5(1): 48-63, 1996

[17] R. Vingralek, Y. Breitbart, G. Weikum SNOWBALL: Scalable Storage on Networks of Workstations with Balanced Load Distributed and Parallel Databases Vol 6(2), Kluwer, Academic Publishers, 1998

[18] Haruo Yokota, Yasuhiko Kanemasa, Jun Miyazaki: Fat-BTree: An Update-Conscious Parallel Directory Structure Proc. ICDE, 1999



Magdalena Punceva <>


CH-1015 Lausanne



Karl Aberer <>


CH-1015 Lausanne