PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Reasoning in a Peer-to-Peer Setting: Application to the Semantic Web

P. Adjiman, P. Chatalic, F. Goasdoue, M. C. Rousset, L. Simon

arXiv:1109.5716v1cs.AI

TL;DR

The paper addresses consequence finding when peer-to-peer systems distribute propositional theories without exposing a global theory. It develops DeCA and applies the framework to Somewhere, showing a fully decentralized infrastructure evaluated on networks of 1000 peers.

  • Problem

    Peer-to-peer consequence finding must reproduce consequences of the union of local theories without giving any peer a global view or centralized control.

  • Method

    The paper develops DeCA, an anytime distributed algorithm that propagates literals through acquainted peers and combines their consequences.

  • Results

    DeCA is sound and terminating, and it is complete when shared-variable paths connect every pair of peers sharing a variable.

  • Takeaways & Limitations

    The framework supports distributed reasoning and Semantic Web data management through the Somewhere peer-to-peer system.

  • Takeaways & Limitations

    The algorithm is restricted to vocabulary-based target languages, although the paper states it can be adapted to more sophisticated target languages.

Abstract

from arXiv · show

In a peer-to-peer inference system, each peer can reason locally but can also solicit some of its acquaintances, which are peers sharing part of its vocabulary. In this paper, we consider peer-to-peer inference systems in which the local theory of each peer is a set of propositional clauses defined upon a local vocabulary. An important characteristic of peer-to-peer inference systems is that the global theory (the union of all peer theories) is not known (as opposed to partition-based reasoning systems). The main contribution of this paper is to provide the first consequence finding algorithm in a peer-to-peer setting: DeCA. It is anytime and computes consequences gradually from the solicited peer to peers that are more and more distant. We exhibit a sufficient condition on the acquaintance graph of the peer-to-peer inference system for guaranteeing the completeness of this algorithm. Another important contribution is to apply this general distributed reasoning setting to the setting of the Semantic Web through the Somewhere semantic peer-to-peer data management system. The last contribution of this paper is to provide an experimental analysis of the scalability of the peer-to-peer infrastructure that we propose, on large networks of 1000 peers.

1. Introduction

The paper develops distributed inference for peer-to-peer systems where peers reason locally and solicit semantically related acquaintances without access to a global theory. It introduces DeCA, applies the setting to Somewhere for the Semantic Web, and evaluates scalability on networks of 1000 peers.

  • Motivation: Peer-to-peer inference lets each peer reason from a local propositional theory while soliciting acquaintances that share part of its vocabulary.The setting supports distributed reasoning tasks in which peers divide subtasks among semantically related peers.
  • Motivation: The global theory is unknown, distinguishing this setting from partition-based reasoning over a centrally known theory.The peer-to-peer architecture imposes the decomposition rather than deriving it from a centralized theory.
  • Contributions: DeCA is the first peer-to-peer consequence-finding algorithm, producing consequences incrementally from the solicited peer toward increasingly distant peers.A sufficient acquaintance-graph condition guarantees completeness.
  • Contributions: Somewhere applies the distributed reasoning framework to Semantic Web data management using a propositional encoding of taxonomies and mappings between classes.Query answering in Somewhere can be reduced to distributed reasoning over local peer theories.
  • Evaluation: 1000 peers were used to experimentally analyze scalability in a fully decentralized approach.The paper contrasts this scale with Piazza's reported scalability of about 80 peers, whose architecture uses centralized schema and mapping storage.

2. Consequence Finding in Peer-to-peer Inference Systems

The paper formalizes consequence finding when peers hold local propositional theories and know only limited acquaintance relationships. The task is to compute target-language consequences of an input clause through distributed reasoning without a global theory.

  • System model: A peer-to-peer inference system is a network of finite propositional clause theories whose peers may share variables with semantically related acquaintances.Shared variables are interpreted consistently across theories that contain them.
  • System model: No peer knows the global theory; each peer knows its local theory and some shared variables with acquaintances.This information structure is part of the problem definition rather than a centralized partitioning choice.
  • Consequence-finding problem: The goal is to find consequences of an input clause that belong to a target language defined over selected target variables.Consequences may be local, remote, or combined across multiple peers.
  • Consequence-finding problem: Completeness requires matching standard consequence finding over the union of local theories without providing that union as a global input.The reasoning must run independently at peers and distribute subtasks among acquaintances.
  • Distributed example: The algorithm propagates shared literals to appropriate neighbors and recombines returned consequences asynchronously.For the tour example, consequences include clauses involving target variables from different peers.

3. Distributed Consequence Finding Algorithm

The paper presents recursive and message-based distributed consequence-finding algorithms that propagate literals through acquaintance graphs and combine returned consequences. The algorithms terminate and are sound, while completeness follows under a sufficient shared-variable connectivity condition.

  • Recursive algorithm: RCF computes local consequences first, then recursively follows acquaintances while tracking processed literals to ensure termination.The recursive history records reasoning branches and prevents repeated processing.
  • Recursive algorithm: The recursive procedure splits clauses over shared literals, queries corresponding acquaintances, and recombines the returned answers with local literals.The distribution operator forms disjunctive combinations of the recursively obtained results.
  • Properties: RCF is sound and terminates for every literal in a peer's vocabulary.Its returned results are implicates in the target language.
  • Properties: Completeness is guaranteed when every pair of peers sharing a variable is connected by a path whose edges all carry that variable.If the condition fails, the algorithm remains sound but need not be complete.
  • Message-based algorithm: The message-based algorithm computes the same results as the recursive algorithm and notifies the user when the final result is produced.This termination notification is important for the algorithm's anytime behavior.

4. Application to the Semantic Web: the somewhere Peer-to-peer Data Management System

Somewhere applies distributed semantic peer-to-peer management to personalized ontologies and mappings, targeting Web-scale interoperability without centralized schema storage. Its propositional data model supports query answering through distributed reasoning.

  • Somewhere models the Semantic Web as a large peer-to-peer data-management system built from personalized ontologies and logical mappings.The approach favors distributed, simple semantic descriptions over imposing one ontology on all users.
  • Unlike centralized-mediator systems, each peer maintains its own ontology and data while mediating with selected peers through schema mappings.Related systems include Edutella and Piazza, but their architectures differ in reference schemas, topology, or centralized storage.
  • Piazza had published scalability results of about 80 peers and relied on centralized storage of schemas and mappings for optimization.
  • Somewhere uses a fully distributed, propositional OWL data model with class-based schemas and mappings, aiming to scale to thousands of peers.The model represents data as resource identifiers and supports inclusion, disjunction, and equivalence statements between classes.
  • Somewhere query rewriting and query answering can be reduced to distributed reasoning in propositional logic.

4.1 Somewhere Data model

Somewhere distributes ontologies, stored-data descriptions, and mappings across peers that know only local schema information and mappings to acquaintances. Its class-based semantics is expressible using propositional constructs and standard model-theoretic interpretation.

  • Each peer joins through acquaintances, declares ontology mappings, and answers queries over local or remotely inferred classes.The considered OWL PL fragment uses conjunction, disjunction, and negation to build class descriptions.
  • A peer ontology contains class definitions plus equivalence, inclusion, or disjointness axioms over class descriptions.Allowed descriptions include ⊤, ⊥, atomic classes, unions, intersections, and complements.
  • A peer’s vocabulary consists of names of its uniquely identified atomic classes, written with a peer prefix such as P:A.
  • Local storage is represented by atomic extensional classes included in ontology descriptions, together with assertions linking identifiers to those extensional classes.
  • Mappings connect atomic classes from different peers through disjointness, equivalence, or inclusion statements.The distributed schema is the union of all peer ontologies, extensional-class declarations, and mappings, although each peer knows only a partial view.
  • The network uses standard first-order interpretations, and satisfiability requires a model satisfying every distributed-schema axiom.Subsumption holds when every model of the schema interprets the subsumed class as a subset of the subsuming class.

4.2 Illustrative Example

The restaurant example shows how four peers organize local restaurant data with distinct taxonomies and exchange semantic mappings. Combined inclusions, equivalences, and intersections support cross-peer query answering.

  • Ann organizes restaurants by quality, ratings, cuisine, and star classes, exposing extensional views for selected categories.Her rated restaurants are partitioned into three disjoint one-, two-, and three-star classes.
  • Bob uses Asian and high-quality restaurant classes and exposes both corresponding extensional views.
  • Chris distinguishes fish and Cantonese restaurants and exposes views for those categories, while Dora organizes preferred restaurants into pizzeria and seafood subclasses.
  • The peers express cross-ontology relationships through mappings, including Bob–Ann equivalence, Ann–Bob inclusions, and Chris–Dora inclusion.These mappings encode differing perspectives as well as shared class meanings.
  • Dora’s preferred-restaurants class is inferred from the intersection of Bob’s Asian and Ann’s good-restaurant classes.The resulting mappings form the restaurants overlay network shown in Figure 2, whose edges identify shared class identifiers.

4.3 Query Rewriting in Somewhere through Propositional Encoding

Somewhere query rewriting is reduced to distributed propositional reasoning by encoding queries and schemas with class identifiers as variables. This encoding preserves satisfiability and connects maximal conjunctive rewritings with prime implicates, under a graph condition supporting completeness.

  • Several distant peers can contribute extensional classes to rewritings and therefore to answers for a query posed at one peer.Somewhere queries use a peer’s local ontology, while answers may involve classes from distant peers.
  • All certain answers can be obtained as the union of answer sets from maximal conjunctive rewritings, while no proper rewriting yields no answers.Thus, query answering is BH2-complete in query complexity and polynomial in data complexity.
  • Queries and Somewhere schemas are transformed into propositional formulas using class identifiers as propositional variables.Class descriptions are encoded inductively, and resulting formulas are converted to clausal form.
  • The encoding preserves satisfiability and makes proper maximal conjunctive rewritings correspond to proper prime implicates over extensional classes.This establishes the formal bridge between Somewhere query rewriting and consequence finding.
  • The encoded Somewhere network satisfies the graph property required by the completeness theorem when shared variables connect peers through paths labeled with those variables.For every shared variable, the corresponding P2PIS contains a path between the peers using that variable on every edge.

5. Experimental Analysis

The experiments show that prime-implicate computation becomes rapidly harder as clause structure and distributed query conditions become more complex, while the anytime algorithm still returns many answers and scales on heterogeneous clusters.

  • 2- and 3-clauses encode taxonomies and mappings, with longer mappings restricted to clauses of length 3.
  • More than 680 prime implicates of length 7 appeared on average for 30-clause, 28-variable random 3-CNF theories.The median total size already exceeded 10,000 literals, while fewer than 5% of runs exceeded 100,000 literals.
  • Proper prime implicate sets were about one order of magnitude smaller than prime-implicate sets, yet still reached about 1,000 literals at the median for n = 28.
  • Hardness grew exponentially with the proportion of 3-clauses in 2 + p-CNF theories, and larger clauses appeared quickly as p increased.Even small values of p could produce hard instances.
  • With p = 10%, theories of up to 100 clauses behaved more reasonably: half of queries were very short, although a small fraction remained very hard.
  • For distributed queries, q = 2 and %3cnf = 0 produced no depth above 7, whereas q = 3 and %3cnf = 20 produced 22% of queries deeper than 100, with a maximum of 134.
  • Timeouts bounded observed depth, while the hardest cases suggested that rare difficult queries could require very long reasoning branches.The experiments also linked exponential depth distributions to short paths and repeated peer solicitation in small-world graphs.
  • On heterogeneous clusters, the algorithm returned many answers even for Very Hard instances and was reported to scale very well.For q = 3 and q = 5 it averaged 1006 and 1004 answers, while Very Hard queries produced at least one answer in half of cases despite only 13% completing without timeout.

6. Related work

The paper distinguishes its decentralized consequence-finding setting from centralized, partition-based reasoning and situates Somewhere among distributed reasoning and peer data-management systems. It emphasizes differences in decomposition assumptions, semantics, network organization, and mapping expressiveness.

  • The algorithm distributes work by splitting clauses and sending clause pieces to appropriate neighboring peers, echoing the splitting rule from natural deduction.The paper connects this message-passing design to earlier logical and distributed-reasoning procedures.
  • Peer-to-peer consequence finding differs from centralized theory decomposition because peers lack a global theory and cannot rely on a tree decomposition of the acquaintance graph.Completeness requirements also differ from those of partition-based reasoning.
  • Distributed reasoning alternatives include multiagent constraint solving, Bayesian belief updating, distributed first-order logic, and distributed description logics, but address different formalisms or semantics.These approaches respectively involve interacting constraint subproblems, posterior beliefs, bridge rules, or distributed tableau reasoning.
  • Somewhere differs from Edutella and Piazza by requiring neither super-peers nor a central server with a global overlay view.It also differs from coDB because no node must know the network topology.
  • Somewhere uses propositional semantics with unrestricted-formula mappings, whereas other peer data-management systems use relational or first-order-logical mappings with different query-answering properties.The comparison includes standard first-order semantics and an epistemic alternative whose answers can be a subset of those under standard semantics.
  • Compared with KadoP and Drago, Somewhere supports more expressive mappings that can combine answers from different sources.KadoP and Drago are described as using simple inclusion statements between atomic classes.

7. Conclusion

The paper combines theoretical and practical contributions: a distributed consequence-finding architecture, extensions for richer representations and Semantic Web resources, and planned handling of multi-agent inconsistencies.

  • Conclusion: The paper provides a distributed consequence-finding algorithm and a peer-to-peer architecture with promising initial experimental results.The architecture supports reasoning services for peer-to-peer web applications.
  • Conclusion: The algorithm is currently restricted to vocabulary-based target languages, but message tags can support more sophisticated target languages.Examples include implicates with a given maximal length and languages based on literals.
  • Conclusion: The architecture could send compressed sets of clauses instead of one clause per message without changing its deep architecture.This extension relies on an efficient clause-distribution operator.
  • Conclusion: Future Semantic Web work will address distributed RDF(S) resources shared at large scale through propositional encoding.RDF(S) is identified as a W3C standard for annotating web resources.
  • Conclusion: Future distributed-reasoning work will consider richer reasoning for multi-agent settings where agents may be inconsistent.The planned extension explicitly addresses possible inconsistencies between agents.
Loading 1109.5716v1…