Distributed Reasoning

The goal of my phd thesis is to study, both theoretically and experimentally, query answering in peer-to-peer inference systems (P2PIS).
A P2PIS is a network of peer theories. Each peer P is a finite set of propositional formulas. Peers are semantically related by sharing common variables in their respective vocabularies.
In a P2PIS, no peer has the knowledge of the global P2PIS theory. Each peer only knows its own local theory and that it shares some variables with some other peers of the P2PIS (its acquaintances). It does not necessarily know all the peers with which it shares variables. When a new peer joins a P2PIS it simply declares its acquaintances in the P2PIS, i.e., the peers it knows to be sharing variables with.

Links with the Semantic Web

The Semantic Web envision a world-wide distributed architecture where data and computational resources will easily inter-operate based on semantic marking up of web resources using ontologies. Ontologies are a formalization of the semantics of application domains (e.g., tourism, biology, medicine) through the definition of classes and relations modelling the domain objects and properties that are considered as meaningful for the application.

Current researches on Semantic Web technologies for information integration investigate a big is beautiful idea that relies on highly expressive languages for bringing semantics to the web. The complexity of handling such languages leads to rather centralized systems. In addition, due to the scale of the Web and the disparity of users, it is unavoidable to have to deal with distributed heterogeneous ontologies.

In our framework, local ontologies, storage description (considered as target variables upon local theories) and mappings are defined using fragment of the two emerging W3C recommendations for the semantic web, namely OWL and RDFS. Performing reasoning in this setting correspond to compute proper prime implicates in a P2PIS (that we define above). For more details on the formal definition of the problem, please reffer to the publication section.

Already performed

The algorithm
We provided the first distributed query answering algorithm which computes proper prime implicates in a peer-to-peer setting. It is anytime and computes consequences gradually from the solicited peer to peers that are more and more distant.
On the data integration point of view, our algorithm could be seen as a P2P version of a centralized queries rewriting using views algorithm (views are chosen target variables upon the distributed theory).
On the propositional logic point of view, our algorithm is computing proper prime implicates of a fully distributed theory.
An animated illustration of the algorithm can be seen here (Require MS Office XP or higher).

Theoretical properties
The algorithm is sound and always terminates. A sufficient condition was exhibited guaranteeing the completeness of this algorithm.

Implementation and test
A prototype in JAVA (about 12 000 lines and 50 JAVA classes) called SomeWhere has been developed.
In collaboration with Laurent Simon, we deployed the prototype over a cluster of more than 80 machines simulating a network of more than 1000 peers and obtained promising results.
Since the P2PIS on which we make tests are randomly generated, we can control their exact size and structure, which allow to make precise statistics on different variables (e.g, the response time or the number of messages exchanged in the network).

Scientific and industrial valorization
For scientific valorisation see the publications section.
This work is also the basis of a joint project between LRI and France-Télécom R&D.