P2P deductive databases: Well founded semantics and distributed computation

This paper stems from previous works of the same authors in which a declarative semantics for Peer-to-Peer (P2P) systems, defined in terms of Preferred Weak Models, is proposed. Under this semantics only facts not making the local databases inconsistent can be imported. As in the general case a P2P system may admit many preferred weak models whose computational complexity is prohibitive, the paper looks for a more pragmatic solution. It assigns to a P2P system its Well Founded Model, a partial deterministic model that captures the intuition that if an atom is true in a preferred weak model, but it is false in another one, then it is undefined in the well founded model. The paper presents a distributed algorithm for the computation of the well founded model and a system prototype.