Access Structures for P2P Information Systems
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.
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.
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
Informatik Kolloquium ETHZ, Zürich, "Data
Access in Peer-To-Peer Information Systems", Karl Aberer, EPFL.
E. Adar and B.A. Huberman: Free riding on Gnutella Technical Report, Xerox PARC,
10 Aug 2000.
D. Clark: Face-to-Face with Peer-to-Peer Networking IEEE Computer, January 2001.
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.
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
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.
T. Johnson, P. Krishna: Lazy Updates for Distributed Search Structure SIGMOD
Conference 1993: 337-346.
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.
Jon Kleinberg. The Small-World Phenomenon: An Algorithmic Perspective. Technical
report 99-1776. Cornell Computer Science, October 1999.
B. Kröll, P. Widmayer Distributing a Search Tree Among a Growing Number of
Processors ACM SIGMOD Conference 1994: 265-276
B. Kröll, P. Widmayer Balanced Distributed Search Trees Do Not Exist WADS 1995:
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
W. Litwin, M. Neimat, D.A. Schneider: RP*: A Family of Order Preserving Scalable
Distributed Data Structures. VLDB 1994: 342-353
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
Sylvia Ratnasamy et al. A Scalable Content-Addressable Network. Proceedings of
the ACM SIGCOMM, 2001
Kunwadee Sripanidkulchai. The popularity of Gnutella queries and its
implications on scalability, February 2001.
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):
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
Haruo Yokota, Yasuhiko Kanemasa, Jun Miyazaki: Fat-BTree: An Update-Conscious
Parallel Directory Structure Proc. ICDE, 1999
IC IIF LSIR
IC IIF LSIR