Distributed Approximation of Fixed-Points in Trust Structures

Abstract

Recently, developments of sophisticated formal models of trust in large distributed environments, incorporate aspects of partial information, important e.g. in global-computing scenarios. Specifically, the framework based on the notion of trust structures, introduced by Carbone, Nielsen and Sassone, deals well with the aspect of partial information. The framework is ``denotational'' in the sense of giving meaning to the global trust-state as a unique, abstract mathematical object (the least fixed-point of a continuous function). We complement the denotational framework with ``operational'' techniques, addressing the practically important problem of approximating and computing the semantic objects. We show how to derive from the setting of the framework, a situation in which one may apply a well-established distributed algorithm, due to Bertsekas, in order to solve the problem of computation and approximation of least fixed-points of continuous functions on cpos. We introduce mild assumptions about trust structures, enabling us to derive two theoretically simple, but highly useful propositions (and their duals), which form the basis for efficient protocols for sound approximation of the least fixed-point. Finally, we give dynamic algorithms for safe reuse of information between computations, in face of dynamic trust-policy updates.