A Formal Model for Decentralized Query Processing in P2P Databases with a Ledger-Based Semantic Registry

Abstract Integrating data across autonomous, peer-to-peer (P2P) systems presents a fundamental trilemma involving autonomy, heterogeneity, and trust. Existing frameworks often sacrifice one of these aspects, relying on centralized components that create single points of failure and preclude verifiable query processing. This paper resolves this trilemma by introducing a novel theoretical framework where a distributed ledger acts as a decentralized arbiter of semantic truth. We formally model the ledger as an immutable Semantic Registry for managing peer schemas and their mappings. Based on this, we develop a query processing protocol that leverages the registry for trustworthy discovery and consistent query rewriting. The primary contribution is the rigorous formalization of this model, including mathematical proofs of soundness and completeness for our protocol. By formally guaranteeing the correctness of queries in a trustless P2P setting, this research provides the theoretical underpinnings for building robust and verifiable data-sharing ecosystems. Our work paves the way for secure collaboration across organizational boundaries without centralized intermediaries.