[PromiseBook] / trunk / chap_reliability.tex Repository: Repository Listing PromiseBook

# View of /trunk/chap_reliability.tex

Wed Jan 19 20:20:17 2011 UTC (2 years, 4 months ago) by mark
File size: 13589 byte(s)
Initial import


\chapter{Fault finding}

frpm \cite{siri1}.

\section{Management: reliability and sustainability}

There are many reasons why a promise, once offered, might not be
kept. These include unforeseen failures, human errors, specification
errors, emergent effects, and so on. The breaking of a promise can be
easily be viewed as a fault that is to be repaired (if one did not
expect the promise to be kept, it would not normally be made), and
hence we should only realistically expect promises to be kept with
some probability. In our graphical framework, it is easy to make
contact with classical reliability theory\cite{hoyland1}.

Reliability under the constraint of autonomy seems to some to be a
hopeless scenario, but it is of course the normal situation in
end-to-end service provision.  If policy were simply a matter of
finding a route from one node to another, as in network routing, one
could provide multiple paths and other strategies for
redundancy. However, the graph edges are labelled with constraints
that must be compatible and hence there is a problem with the
combinatorics of the constraints. This problem is too involved to
present in this paper, but we claim here without justification that
promises make it a soluble problem, in principle, whereas obligations
do not.

How do promises assist the understanding of
management in a pervasively autonomous environment?  We believe that
control is an unrealiastic goal in a distributed system and hence that
ability to guide systems in approximate terms, using incentives to
entice autonomous change, without the necessity complete information
about system specification and state. Unless the amount of information
required to formulate a policy is considerably less than the total
information describing the state of the system, one must surely
consider the system to be unmanageable\cite{burgessbook2} -- for one
is then talking about design rather than management.

To discuss management, we would therefore like to examine ways of
coarse graining, or eliminating detail in a way that is faithful to
the functional behaviour of the system. Promises offer an ideal
starting point for this.

A policy, based on promises, leads to a labelled graph over possibly
disjoint or partially connected sets of agents in different
regions. One can then take this graph and replace it with a graph that
captures the essence' of this picture.  The economics and reliability
of promises are typeless, i.e. the value of any promise can be
measured in one single currency, so in practice one can remove labels from
the promise network structure and consider the effective connectivity,
to see:
\begin{itemize}
\item Logical errors or missing bindings are seen as residual directed edges.
\item Which nodes are providing services with acceptable SLAs?
\item What roles are necessary to distinguish or extend the functionality?
\item Where are the vulnerable parts of the cooperative network?
\item What is the probability that a failure will be fatal?
\end{itemize}

Our theory addresses these questions directly. The first few points
should already be clear, within the scope of this paper. The latter
require us to develop promises as fault networks\cite{hoyland1}.

\subsection{Graphical fault finding}

Each promise is associated with a topic or a theme and a constraint,
the details of which have been largely suppressed in this paper for
clarity.  Thus each edge or link in the promise graph is labelled.
Promises with different labels are not directly comparable, but it is
useful to see the extent of larger classes of promise within the
graph, in order to model the collective behaviour of the agents or see
the penetration of certain promises.

Any non-labelled graph can be represented by its adjacency matrix
$A_{ij}$ in which the indices $i,j$ of the matrix run over the agents
in the graph.  A non-zero element $A_{ij}\not= 0$ means that there is
an edge or link in the graph from $i\rightarrow j$. The value of the
element is a weight associated with that edge. Often these weights are
simply 1 or 0.  A labelled graph can, of course, be represented as a
matrix of labels, but this limits the ability to use the matrix for
numerical reasoning.

By removing labels, we invoke a common currency' in any connected
policy graph\cite{burgessbook2}, which evaluates how much a promise is
worth' in some context to our management model. This currency might
be measured in money or as an expectation value of reliability, or in
any convenient function of the promises.  All variables are expressed
in terms of a common scale of measurement, i.e. one forms an
equivalent graph of directed relationships, at each moment, that has
no labels, only weighted edges.
\bigskip
\begin{definition}[Common Currency Equivalent Graph]
A common currency equivalent graph (CCEG) is a transformation of the
labelled promise graph, in which each promise is reduced to a single
dimensionless value that can be summed.  A currency value can be
defined as any linear combination of functions which takes a promise
body as an argument and maps it into the real numbers, e.g. the
probability of the promise being kept.  Then the common
currency graph has an adjacency matrix of the general form:
\beq
A_{ij} &=& \alpha_1 f_1(\stackrel{b_1}{n_i\rightarrow n_j}) + \alpha_2 f_2(\stackrel{b_2}{n_i\rightarrow n_j}) + \ldots \nonumber\\
&=& \alpha_1 f_1(A^1_{ij}) +  \alpha_2 f_2(A^2_{ij}) + \ldots
\eeq
where the $A_{ij}^k$ is the adjacency matrix for promises
of type $k$ and agents $i,j$.
\end{definition}
\bigskip
One can formulate a precise definition of how {\em constrained}
autonomous agents are by their voluntary promises to the neighbours,
using the topology of the graph as a guide. In particular, the concept
known as {\em eigenvector centrality} is a useful perspective for
management, which ranks the nodes in a graph according to the
recursively counted involvement in the
network\cite{bonacich1,bonacich2,burgessbook2}.

If one multiplies a row of the adjacency matrix, of ones and zeroes,
by a column vector of ones, this simply counts the number of promises
which that node exchanges with its neighbours. One can use this fact
to self-consistently sum the promises from the entire graph and see
which agents are most entangled. By rescaling, this leads to a unique
ranking in terms of the connectivity.

Since the labelled edges of the promises lead to many typed graphs,
one must decide how to deal with the different labels: whether to separate
them or remove them (see next section).

Let $v_i$ denote a vector for the cooperative ranking of each node $i$. Then, the
importance of node $i$ is proportional to the sum of the importances
of all of $i$'s nearest neighbours ${\cal N}(i)$:
\beq
v_i \propto\sum_{j={\cal N}(i)} v_j .
\label{pevc1}
\eeq
Writing this more compactly gives
\beq
v_i \propto \sum_j A_{ij} v_j \ ,
\label{pevc2}
\eeq
where
$A$ is the adjacency matrix, and hence:
\beq
{A}\,\vec{v} =\lambda \vec v \ .
\label{pevcfin}
\eeq
The ranking vector is seen to be an eigenvector of the adjacency
matrix $A$. If $A$ is an $N\times N$ matrix, it has $N$ eigenvectors
(one for each agent in the network), and correspondingly many
eigenvalues. The eigenvalue of interest is the principal eigenvector,
i.e. that with highest eigenvalue, since this is the only one that
results from summing all of the possible pathways with a positive
sign.  The components of the principal eigenvector rank how
self-consistently central' a node is in the graph. Here, it signifies
how many promises an agent is involved in.  The highest valued
component is the most central'', i.e. the most entangled in
promises.

Applications of the centrality have been
given in refs. \cite{archipelago,roles,burgessbook2} and further
applications for directed graphs are studied in ref. \cite{burgessroles}.
We note some further points:
\begin{itemize}

\item Sources and sinks, signifying incomplete agreements, show up readily
in these graphs and are thus easily identifiable with a simple method.

\item $A^{\rm T}$ gives a higher ranking to the recipient of a
promise, whereas $A$ gives a high ranking to the provider of a
promise.

\item If one takes the undirected common currency graph of all collaborative $C(b)$'' promises,
this shows us the collaborations, social structures or roles amongst
the agents. Tightly bound regions will form topological
roles\cite{roles} and the highest ranking node will be that which is
most important in binding the collaborative structure. This is both an
agent that one should be wary of and which should have enough
resources to fulfill its contractual obligations.

\item If one takes the common currency graph of all promises of type $b$ and $U(b)$
together, these represent bindings. Even though the
promises only have meaning between pairs of nodes, the viewpoint
offered by the eigenvector is the level of entanglement of the agents
in a collaborative network. Again, this allows one to focus attention
on agents where problems more likely will arise. One now has a choice
between ranking by $A^{\rm T}$ or by $A$.

\end{itemize}

\section{Further applications: software management}

Let us draw another parallel with pervasive computing management,
namely software engineering management, and suggest how promise theory
can offer insights into the structure of programming objects. This has
been developed at length in ref. \cite{aredo1}.

A service view of software has been developed in detail, especially
since the example of object orientation, in particular Smalltalk.
Software is a collection of objects, including storage and methods,
which perform services for one another like granting access' or
transfer data'. The theory of object orientation has been built up
very much around the tree-like hierarchy, but developments such as
Aspect Oriented Programming underlines the fact that computer programs
are not well modelled by strict hierarchies.

Our theory of promises can be applied to programming by treating every
addressable item in a program as a node in a graph\cite{aredo1}. By
explicitly adding arrows for the services that bind the objects
together, one obtains a graph of the necessary and sufficient
relationships between the objects. The traditional approach to
deciding encapsulation is one of doctrine, but our approach yields an
answer to the natural boundaries based only on the roles in the
promise graph. This graph is constructed only with the principle that
{\em all} objects are private (autonomous) unless they promise to give
up that autonomy in order to cooperate with another.  We provide only
the smallest example here as a taster of this approach, to be
expounded elsewhere.

organizational decisions about objects and their levels of privacy and
encapsulation. Promise theory offers a method for addressing this
issue based on minimalism. We call the result a {\em policy} for
design.  One sees that computer programs are examples of pervasive
services.  This idea must be explored further elsewhere.

\section{Conclusions and discussion}

As a management tool for understanding and designing policy, promises
have attractive properties; they make hidden assumptions explicit and
thus help one to unravel the requirements for solving different
problems.  Promises assist us in assessing the uncertainties
remaining, since they take a more realistic view of cooperation within
a network than many software driver' models.

There is a close similarity between the promise approach and the
operator approach used by the autonomous agent cfengine, in
configuration management. Although cfengine is not explicitly
concerned with network management, its modus operandi is to build a
policy from atomic promises about certain resources available on
computers that are optionally linked by a network\cite{burgessC1}.

By translating the detailed graph into a graph of common currency, we
can make certain approximations and predictions about their meaning.
For example, research on eigenvectors of directed graphs suggests
that one might be able to reduce some complex questions to very simple
tests\cite{burgessroles}. We hypothesize the following:
\bigskip
\begin{hype}[CCEG minimum requirement]
The minimum requirement for a network policy to be sustainable across
all affected nodes is the existence of a positive definite principal
eigenvector for the adjacency matrix of the common currency equivalent
graph.
\end{hype}
\bigskip
Further work is required to answer this question. However, if true it
would be remarkable, because there is a second motivation for the
common currency graph, namely the economic or cooperative
motivation\cite{siri2}. Our preliminary studies do not contradict this
hypothesis.

We are now in a position to be able to attempt to answer vital
questions in future work.  How stable is the network to cooperation?
Could it ever be completely stable or completely unstable?  The
models of voluntary cooperation indicate that policy should be
formulated in a way that builds both rewards and punishments into
interactions between peers in order to secure stability.

In this paper we are afforded just enough space to lay the
foundations for studying the uncertainties inherent in pervasive
computing management'. It remains to be seen how easily these
concepts can be harnessed to develop stable rule-based cooperatives in
the real world.  We return to these details in the subsequent papers.