|
Distributed Approximation of Fixed-Points in Trust Structures
Karl Krukow
September 2004 |
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.
Available as PostScript, PDF. |