Design, formalization and implementation of overlay networks : application to RDF data storage
Francesco Bongiovanni · OpenGrey (Institut de l'Information Scientifique et Technique) · 2012
Structured Overlay Networks (SONs) are a new class of Peer-to-Peer (P2P) systems which are widely used for large scale applications such as file sharing , information dissemination, storage and retrieval of different resources Many different SONs co-exist on the Web yet they do not cooperate with each other. In order to promote cooperation, we propose two protocols, Babelchord and Synapse, whose goals are to enable the inter-connection of structured and heterogeneous overlays networks through meta-protocols. Babelchord aims to aggregate small structured overlay networks in an unstructured fashion while Synapse generalizes this concept and provides flexible mechanisms relying on co-located nodes, i. e. nodes which belong to multiple overlays at the same time. We provides the algorithms behind both protocols, as well as simulations results showing their behaviours in the context of information retrieval. We have also implemented and experimented a prototype of JSynapse on the Grid 5000 platform, confirming the obtained simulation results and giving a proof of concept of our protocol. A novel generation of SONs was created in order to store and retrieve semantic data in large scale settings. The Semantic Web community is in need for scalable solutions which are able to store and retrieve RDF data, the core data model of the Semantic Web. The first generation of these systems is too monolithic and provided limited support for expressive queries. We propose the design and implementation of a new modular P2P-based system for these purposes. We build the system with RDF in mind and used a three-dimensional CAN overlay network, mimicking the nature of an RDF triple. We made specific design choices which preserve data locality but raises interesting technical challenges. Our modular design reduces the coupling between its underlying components, allowing them to be inter-changed with others. We also ran some micro-benchmarks on Grid 50000 which will be discussed. SONs have a specific geometrical topology which could be leveraged in order to increase the overall performance of the system. In this regard we propose a new broadcast efficient algorithm for CAN, developed in response to the results found from running the experiments in the RDF data store we have built, which used too many messages. Along this algorithm, we also propose a reasoning framework, developed with the Isabelle/HOL proof assistant, for proving correctness properties of dissemination algorithms for CAN-like P2P-systems. We focus on providing the minimal set of abstractions needed to devise efficient correct-by-construction dissemination algorithms on top of such overlay.