Formal Definitions and Complexity Results for Trust Relations and Trust Domains

We propose computational, declarative definitions of the concepts of weak and strong trust relations between interacting agents, and trust domains of trust-related agents in distributed systems. Our definitions yield computational complexity results for deciding potential and actual trust relationships and membership in trust domains, as well as a positive (negative) compositionality result for strong (weak) trust domains. Our defining principle for weak and strong trust is (common) belief in and knowledge of agent correctness, respectively.

KEYWORDS:

computability, compositionality, and scalability of trust and trustworthiness; computer-aided decision making (CADM); dependable distributed or multi-agent systems; modal logics of belief and knowledge.