The complexity of fixed point models of trust in distributed networks

In this paper we consider the complexity of some problems arising in a fixed point model of trust in large-scale distributed systems, based on the notion of trust structures introduced by Carbone, Nielsen and Sassone; a set of trust levels with two distinct partial orderings. In the trust model, a global trust state exists as the least fixed point of a collection of local policy functions of nodes in the network. We first show that it is possible to efficiently compute a single component of the global trust state using a simple, robust and totally asynchronous distributed algorithm. We complement this with a lower bound which shows that, if the policies are unrestricted then communication and time linear in the number of distinct trust levels is required in the worst case. We then consider the notion of distributed proof carrying requests previously introduced as a means of safely approximating the global trust state without computing its exact value. We present a new result that enables us to give a continuum of proof carrying protocols, the previously known protocol being one extreme of this. The theorem allows us to generate protocols that can prove all possible trust values (previously, it was only possible to prove trust values representing 'not too much bad behaviour'). However, we show that such a general protocol may not be efficient - it is NP-hard to construct an approximately minimal size proof in our model, and in the worst case the nodes must communicate almost as much data as if they were to compute the global trust state from scratch. The implications of our negative results are that it may be necessary to restrict the policy language in order to efficiently implement a fixed point model of trust in a distributed network.