Semantic Overlay Networks | EPFL Graph Search

In a handful of years only, Peer-to-Peer (P2P) systems have become an integral part of the Internet. After a few key successes related to music-sharing (e.g., Napster or Gnutella), they rapidly developed and are nowadays firmly established in various contexts, ranging from large-scale content distribution (BitTorrent) to Internet telephony(Skype) or networking platforms (JXTA). The main idea behind P2P is to leverage on the power of end-computers: Instead of relying on central components (e.g., servers), services are powered by \emph{decentralized overlay} architectures where end-computers connect to each other dynamically. So far, much effort has been devoted to the development of distributed hashtables (DHTs) to index data in a totally decentralized way. Though extremely robust and scalable, these systems suffer from simplistic data models, which mainly consist of unstructured collections of key-value pairs. More recently however, a significant number of uncorrelated research efforts focused on enriching P2P systems with more expressive data models and query languages. As a result, various Semantic Overlay Networks (SON) supporting relational, semi-structured or triple-based collections of data over decentralized P2P networks started to appear. SON can be considered as truly unique as they aim at managing structured data in very large-scale, decentralized, heterogeneous and highly dynamic environments.

Sharing of probabilistically correlated data in peer-to-peer networks

Roman Schmidt

The impact of Peer-to-Peer (P2P) networks on the Internet landscape is undisputed. It has led to a series of new applications, e.g., as part of the so-called Web 2.0. The shift from the classical client-server based paradigm of the Internet, with a clear distinction between information providers and consumers, towards consumers sharing information among each other led to the rise of the P2P paradigm. The distributed setting enables users to share their content autonomously and locally, i.e, information remains at computers at the edge of the Internet and is not gathered and organized at central servers. Structured overlay networks were designed to organize the huge quantity of data shared in P2P networks by building a global, though distributed, index of shared information. Whereas the initial aim of these systems was to provide efficient lookup operations for single keyword operations, the need for more complex operations emerged very quickly. Peer Data Management Systems (PDMS) is one such example of application that enables data integration and complex query processing similar to (distributed) database systems on top of structured overlays. Complex query operators usually require joint access to multiple data entries whereas single key lookups usually only affect a single data entry. The partitioning of the distributed index of standard structured overlays is optimized towards single key lookups and joint data access as required by PDMS was neglected so far. (Distributed) databases have already shown that (index-)data organization supporting correlated data access is necessary and crucial for efficient processing, as network usage is minimized. We aim at applying this insight to structured overlays by clustering correlated data frequently accessed jointly by applications, including PDMS but also other types of applications. Data correlations can be derived from different sources, data properties, processing properties, users and applications. We study and present solutions for three different types of correlations in the context of different applications: (i) range queries where exploiting the order relationship of data is a fundamental basis for any database-like system; (ii) distributed probabilistic inference where exploiting user-defined complex data correlations gains importance through the Web 2.0; (iii) multi-term queries where exploiting data correlations derived from data access statistics enables simple but powerful keyword search to users. Our approach exploits properties of structured overlays, such as order-preserving hashing, to realize efficient range query processing. We further introduce a distributed clustering algorithm based on the spring relaxation technique to cluster strongly correlated data entries at one node respectively in its proximity. Joint data access is thus performed on a single or few nodes to reduce network bandwidth consumption and therefore to increase system performance. Our approaches are realized on top of the structured overlay network P-Grid although they are generic enough to be applied to other P2P networks with similar properties. This thesis presents details about the Java implementation of P-Grid, its architectural design and its evaluation on PlanetLab, today's standard testbed for P2P systems. The implementation of P-Grid in a Java application finally enabled us to build a PDMS system on top relying on P-Grid's efficient query processing. We present the UniStore system, a distributed data management system aiming at public data management and support for database-like query operators on heterogeneous data, and its evaluation on PlanetLab.

EPFL2008

Indexing data-oriented overlay networks

Karl Aberer, Anwitaman Datta, Manfred Hauswirth, Roman Schmidt

We address the problem of how a data-oriented, structured overlay networks can be constructed efficiently from scratch in a self-organized way, a problem that has so far not been addressed in the literature. This problem occurs when using overlay networks to implement index structures for data-oriented applications such as peer-to-peer databases or peer-to-peer information retrieval. There changing application requirements frequently lead to re-indexing of the data and hence (re-)construction of overlay networks. Standard maintenance algorithms for overlay networks cannot efficiently deal with this task as they are inherently sequential. We propose a randomized algorithm which is completely decentralized and parallel that can construct a new overlay network with short latency. At the same time our approach ensures good load-balancing for skewed data key distributions which result from preserving key order relationships as necessitated by data-oriented applications. We provide both a theoretical analysis of the basic algorithms and a complete system implementation that has been tested on PlanetLab. We are using this system to support peer-to-peer information retrieval and database applications.

2005

Advanced Peer-to-Peer Networking: The P-Grid System and its Applications

Karl Aberer, Philippe Cudré-Mauroux, Anwitaman Datta, Zoran Despotovic, Manfred Hauswirth, Roman Schmidt, Jie Wu

The limitations of client/server systems become evident in an Internet-scale distributed environment. Peer-topeer (P2P) systems offer an interesting alternative to traditional client/server systems: Every node acts both as a client and a server and “pays” its participation by providing access to its computing resources. Systems such as Napster and Gnutella have proven their practical applicability. In this article we give an overview of our PGrid system which provides an advanced P2P infrastructure targeted at application domains beyond mere filesharing. We present the conceptual foundations and outline some of the applications we are developing at the moment.

2003

Sharing of probabilistically correlated data in peer-to-peer networks

Roman Schmidt

EPFL2008