Distributed Information Systems Laboratory LSIR

Description

This research addresses the problem of efficiently searching for resources in a decentralized architecture. The goal is to rely for construction and maintenance on self-organization principles to the largest degree possible without sacrificing efficiency [7]. The solution builds on a distributed indexing approach based on prefix routing, P-Grid, which has first been presented at COOPIS 2001 [1]. P-Grid combines the idea of constructing an efficient, distributed, prefix routing scheme, as used in distributed hash tables, with the flexibility of network maintenance as found in practical P2P systems, such as Gnutella or FreeNet [4][13]. P-Grid has the inherent capability of storage load balancing without sacrificing search efficiency [3][15][16][27]. For resilience P-Grid uses dynamic replication of data and replicas are updated using a gossipping mechanism [6]. A self-contained method for maintaining P-Grid in the presence of dynamic physical addresses has been developed in [9][11]. Since based on a trie-structure it naturally supports typical complex query processing needs [17][19]. P-Grid is implemented as a system and currently used as platform for development of various applications [8][24].We also study and develop generic models and architectures for structured overlay networks [10][12][14][18][21][23][26][29]. Recently we started to investigate congestion control mechanisms for high throughout overlay networks [28]. Information on P-Grid and the system are provided at the P-Grid Website www.p-grid.org .

Updated November 21, 2007

References

[1] K. Aberer, P-Grid: A self-organizing access structure for P2P information systems , Sixth International Conference on Cooperative Information Systems (CoopIS 2001), Trento, Italy, September 5-7, 2001.

[2] K. Aberer, M. Punceva, M. Hauswirth, R. Schmid, " Improving Data Access in P2P Systems ", IEEE Internet Computing, 6(1) pp. 58-67, (2002).

[3] K. Aberer, "Scalable Data Access in Peer-to-Peer Systems Using Unbalanced Search Trees", Workshop on Distributed Data & Structures (WDAS 2002), Paris, France, 2002, Carleton Scientific.

[4] K. Aberer, M. Hauswirth, M. Punceva, " Self-organized construction of distributed access structures: A comparative evaluation of P-Grid and FreeNet ", The 5th Workshop on Distributed Data and Structures (WDAS'2003), Thessaloniki, Greece, June 13-14, 2003.

[5] K. Aberer, P. Cudré-Mauroux, A. Datta, Z. Despotovic, M. Hauswirth, M. Punceva, R. Schmidt: P-Grid: a self-organizing structured P2P system. SIGMOD Record 32(3): 29-33 (2003).

[6] A. Datta, M. Hauswirth, K. Aberer " Updates in Highly Unreliable, Replicated Peer-to-Peer Systems ", ICDSC 2003.

[7] S. Staab, F. Heylighen, C. Gershenson, G. William Flake, D. M. Pennock, D. C. Fain, D. De Roure, K. Aberer, Wei-Min Shen, O. Dousse, P. Thiran: Neurons, Viscose Fluids, Freshwater Polyp Hydra-and Self-Organizing Information Systems. IEEE Intelligent Systems 18(4): 72-86 (2003).

[8] K. Aberer, P. Cudré-Mauroux, A. Datta, Z. Despotovic, M. Hauswirth, M. Punceva, R. Schmidt, J. Wu: " Advanced Peer-to-Peer Networking: The P-Grid System and its Applications ", PIK - Praxis der Informationsverarbeitung und Kommunikation, Special Issue on P2P Systems, 26(3), 2003.

[9] K. Aberer, A. Datta, M. Hauswirth: Efficient, self-contained handling of identity in Peer-to-Peer systems, IEEE Transactions on Knowledge and Data Engineering 16(7): 858-869 (2004).

[10] A. Datta, S. Girdzijauskas, K. Aberer: "On de Bruijn Routing in Distributed Hash Tables: There and Back Again", The Fourth IEEE International Conference on Peer-to-Peer Computing, Zurich, Switzerland, 25-27 August 2004.

[11] K. Aberer, A. Datta, M. Hauswirth: "Route maintenance overheads in DHT overlays", WDAS 2004. The 6th Workshop on Distributed Data and Structures, EPF Lausanne, Switzerland, July 8-9, 2004.

[12] S. Girdzijauskas, A. Datta, K. Aberer, "On SmallWorld Graphs in Non-uniformly Distributed Key Spaces" 1st IEEE International Workshop on Networking Meets Databases (NetDB) in cooperation with 21st IEEE Conference on Data Engineering (ICDE 2005), Tokyo, Japan, April 8-9, 2005.

[13] K. Aberer, A. Datta, M. Hauswirth, R. Schmidt, "Das P-Grid-Overlay-Netzwerk: Von einem einfachen Prinzip zu einem komplexen System", Datenbank Spektrum, 2005.

[14] K. Aberer, A. Datta, M. Hauswirth, "P-Grid: Dynamics of Self-organizing Processes in Structured P2P systems", In: Peer-to-Peer Systems and Applications, LNCS 3485, Springer, Aug 2005.

[15] K. Aberer, A. Datta, M. Hauswirth: "Multifaceted Simultaneous Load Balancing in DHT-based P2P systems: A new game with old balls and bins" Self-* Properties in Complex Information Systems, "Hot Topics" Series, Lecture Notes in Computer Science, Springer Verlag, 2005.

[16] K. Aberer, A. Datta, M. Hauswirth, R. Schmidt, "Indexing data-oriented overlay networks", 31st International Conference on Very Large Databases (VLDB), Trondheim, 30 Aug - 2 Sep, 2005.

[17] A. Datta, M. Hauswirth, R. John, R. Schmidt, K. Aberer, "Range queries in trie-structured overlays", The Fifth IEEE International Conference on Peer-to-Peer Computing, Konstanz, 31 Aug - 2 Sep 2005.

[18] K. Aberer, L. Onana Alima, A. Ghodsi, S. Girdzijauskas, M. Hauswirth, S. Haridi "The essence of P2P: A reference architecture for overlay networks", The Fifth IEEE International Conference on Peer-to-Peer Computing, Konstanz, 31 Aug - 2 Sep 2005.

[19] G. Skobeltsyn, M. Hauswirth, K. Aberer, "Efficient processing of XPath queries with structured overlay networks", The 4th International Conference on Ontologies, DataBases, and Applications of Semantics (ODBASE), Agia Napa, Cyprus, Oct 31 - Nov 4, 2005.

[20] A. Datta, K. Aberer, " Internet-scale storage systems under churn - A study of the steady state using Markov models ", The Sixth IEEE International Conference on Peer-to-Peer Computing (P2P 2006), Cambridge, UK, September 2006.

[21] S. Girdzijauskas, A. Datta, K. Aberer, " Oscar: A Data-Oriented Overlay For Heterogeneous Environments " , (short paper), ICDE 2007, The 23rd International Conference on Data Engineering (ICDE), April 16-20, 2007, Istanbul, Turkey, 2007.

[22] A. Datta, R, Schmidt, K. Aberer, " Query-load balancing in structured overlays ", Seventh IEEE International Symposium on Cluster Computing and the Grid (CCGRID) , Rio de Janeiro, Brazil, May 14-17, 2007.

[23] F. Klemm, S. Girdzijauskas, J.-Y. Le Boudec and K. Aberer: " On Routing in Distributed Hash Tables ", The Seventh IEEE International Conference on Peer-to-Peer Computing (P2P 2007), Galway, Ireland, September 2007.

[24] K. Aberer, D. Bickson, D. Dolev, M. Hauswirth, Y. Weiss, Indexing data-oriented overlay networks using belief propagation , 7th Workshop of distributed algorithms and data structures (WDAS 06'), January 2006.

[25] A. Datta, K. Aberer, " The challenges of merging two similar structured overlays: A tale of two network s" (Best paper award), IWSOS 2006, International Workshop on Self-Organizing Systems, Passau, Germany, September 2006.

[26] S. Girdzijauskas, A. Datta, K. Aberer, " Oscar: Small-World Overlay For Realistic Key Distributions ", The 4th International Workshop on Databases, Information Systems and Peer-to-Peer Computing (DBISP2P 2006), Seoul, South Korea, September 2006.

[27] A. Datta, W. Nejdl, K. Aberer, "Optimal caching for first-order query load-balancing in decentralized index structures", The 4th International Workshop on Databases, Information Systems and Peer-to-Peer Computing (DBISP2P 2006), Seoul, South Korea, September 2006.

[28] F. Klemm, J.Y. Le Boudec, D. Kostic, K. Aberer: " Improving the Throughput of Distributed Hash Tables Using Congestion-Aware Routing ", Proceedings of the Sixth International Peer to Peer Symposium (IPTPS), 2007.

[29] W. Galuba and K. Aberer, " Generic emergent overlays in arbitrary peer identifier spaces" , (Best paper award), Self-Organizing Systems, Second International Workshop (IWSOS 2007), The Lake District, UK, September 11-13, 2007, Vol. 4725, pp. 88-102, 2007.