Distributed Approximation of Fixed-Points in Trust Structures
Karl Krukow
February 2005 |
Abstract:
Recently, Carbone, Nielsen and Sassone introduced the
trust-structure framework; a semantic model for trust-management in
global-scale distributed systems. The framework is based on the notion of
trust structures; a set of ``trust-levels'' ordered by two distinct partial
orderings. In the model, a unique global trust-state is defined as the least
fixed-point of a collection of local policies assigning trust-levels to the
entities of the system. However, the framework is a purely denotational
model: it gives precise meaning to the global trust-state of a system, but
without specifying a way to compute this abstract mathematical object.
This paper complements q the denotational model of trust structures with operational techniques. It is shown how the least fixed-point can be computed using a simple, totally-asynchronous distributed algorithm. Two efficient protocols for approximating the least fixed-point are provided, enabling sound reasoning about the global trust-state without computing the exact fixed-point. Finally, dynamic algorithms are presented for safe reuse of information between computations, in face of dynamic trust-policy updates Available as PostScript, PDF. |