Heuristic Discovery of Role-Based Trust Chains in Peer-to-Peer Networks

Credential chains are needed in trusted peer-to-peer (P2P) applications, where trust delegation must be established between each pair of peers at specific role level. Role-based trust is refined from the coarse-grained trust model used in most P2P reputation systems. This paper offers a novel heuristic-weighting approach to selecting the most likely path to construct a role-based trust chain. We apply history-sensitive heuristics to measure the path complexity and to assess the chaining efficiency. Our method discovers successive edges of a trust chain, adaptively, to match with the demands in any given P2P application. New heuristic chaining algorithms are developed for backward, forward, and bidirectional discovery of trust chains. Our heuristic chain discovery scheme shortens the search time, reduces the memory requirement, and enhances the chaining accuracy in scalable P2P networks. Consider a trust graph over N credentials and M distinct role nodes. Our heuristic trust-chain discovery algorithms require O(N(2)logN) search time and O(M) memory space, if the secondary heuristics are generated offline in advance. These are improved from O(N-3) search time and O(NM) space required in nonheuristic discovery algorithms developed by Li et al. [12]. Our analytical results are verified by extensive simulation experiments over typical classes of role- based trust graphs.