Parent Directory
| 
Revision Log
Revision 1 - (view) (download) (as text)
| 1 : | mark | 1 | |
| 2 : | \chapter{Fault finding} | ||
| 3 : | |||
| 4 : | frpm \cite{siri1}. | ||
| 5 : | |||
| 6 : | \section{Management: reliability and sustainability} | ||
| 7 : | |||
| 8 : | There are many reasons why a promise, once offered, might not be | ||
| 9 : | kept. These include unforeseen failures, human errors, specification | ||
| 10 : | errors, emergent effects, and so on. The breaking of a promise can be | ||
| 11 : | easily be viewed as a fault that is to be repaired (if one did not | ||
| 12 : | expect the promise to be kept, it would not normally be made), and | ||
| 13 : | hence we should only realistically expect promises to be kept with | ||
| 14 : | some probability. In our graphical framework, it is easy to make | ||
| 15 : | contact with classical reliability theory\cite{hoyland1}. | ||
| 16 : | |||
| 17 : | Reliability under the constraint of autonomy seems to some to be a | ||
| 18 : | hopeless scenario, but it is of course the normal situation in | ||
| 19 : | end-to-end service provision. If policy were simply a matter of | ||
| 20 : | finding a route from one node to another, as in network routing, one | ||
| 21 : | could provide multiple paths and other strategies for | ||
| 22 : | redundancy. However, the graph edges are labelled with constraints | ||
| 23 : | that must be compatible and hence there is a problem with the | ||
| 24 : | combinatorics of the constraints. This problem is too involved to | ||
| 25 : | present in this paper, but we claim here without justification that | ||
| 26 : | promises make it a soluble problem, in principle, whereas obligations | ||
| 27 : | do not. | ||
| 28 : | |||
| 29 : | How do promises assist the understanding of | ||
| 30 : | management in a pervasively autonomous environment? We believe that | ||
| 31 : | control is an unrealiastic goal in a distributed system and hence that | ||
| 32 : | management is not about such totalitarian control, but about the | ||
| 33 : | ability to guide systems in approximate terms, using incentives to | ||
| 34 : | entice autonomous change, without the necessity complete information | ||
| 35 : | about system specification and state. Unless the amount of information | ||
| 36 : | required to formulate a policy is considerably less than the total | ||
| 37 : | information describing the state of the system, one must surely | ||
| 38 : | consider the system to be unmanageable\cite{burgessbook2} -- for one | ||
| 39 : | is then talking about design rather than management. | ||
| 40 : | |||
| 41 : | To discuss management, we would therefore like to examine ways of | ||
| 42 : | coarse graining, or eliminating detail in a way that is faithful to | ||
| 43 : | the functional behaviour of the system. Promises offer an ideal | ||
| 44 : | starting point for this. | ||
| 45 : | |||
| 46 : | A policy, based on promises, leads to a labelled graph over possibly | ||
| 47 : | disjoint or partially connected sets of agents in different | ||
| 48 : | regions. One can then take this graph and replace it with a graph that | ||
| 49 : | `captures the essence' of this picture. The economics and reliability | ||
| 50 : | of promises are typeless, i.e. the value of any promise can be | ||
| 51 : | measured in one single currency, so in practice one can remove labels from | ||
| 52 : | the promise network structure and consider the effective connectivity, | ||
| 53 : | to see: | ||
| 54 : | \begin{itemize} | ||
| 55 : | \item Logical errors or missing bindings are seen as residual directed edges. | ||
| 56 : | \item Which nodes are providing services with acceptable SLAs? | ||
| 57 : | \item What roles are necessary to distinguish or extend the functionality? | ||
| 58 : | \item Where are the vulnerable parts of the cooperative network? | ||
| 59 : | \item What is the probability that a failure will be fatal? | ||
| 60 : | \end{itemize} | ||
| 61 : | |||
| 62 : | Our theory addresses these questions directly. The first few points | ||
| 63 : | should already be clear, within the scope of this paper. The latter | ||
| 64 : | require us to develop promises as fault networks\cite{hoyland1}. | ||
| 65 : | |||
| 66 : | \subsection{Graphical fault finding} | ||
| 67 : | |||
| 68 : | Each promise is associated with a topic or a theme and a constraint, | ||
| 69 : | the details of which have been largely suppressed in this paper for | ||
| 70 : | clarity. Thus each edge or link in the promise graph is labelled. | ||
| 71 : | Promises with different labels are not directly comparable, but it is | ||
| 72 : | useful to see the extent of larger classes of promise within the | ||
| 73 : | graph, in order to model the collective behaviour of the agents or see | ||
| 74 : | the penetration of certain promises. | ||
| 75 : | |||
| 76 : | Any non-labelled graph can be represented by its adjacency matrix | ||
| 77 : | $A_{ij}$ in which the indices $i,j$ of the matrix run over the agents | ||
| 78 : | in the graph. A non-zero element $A_{ij}\not= 0$ means that there is | ||
| 79 : | an edge or link in the graph from $i\rightarrow j$. The value of the | ||
| 80 : | element is a weight associated with that edge. Often these weights are | ||
| 81 : | simply 1 or 0. A labelled graph can, of course, be represented as a | ||
| 82 : | matrix of labels, but this limits the ability to use the matrix for | ||
| 83 : | numerical reasoning. | ||
| 84 : | |||
| 85 : | By removing labels, we invoke a common `currency' in any connected | ||
| 86 : | policy graph\cite{burgessbook2}, which evaluates how much a promise is | ||
| 87 : | `worth' in some context to our management model. This currency might | ||
| 88 : | be measured in money or as an expectation value of reliability, or in | ||
| 89 : | any convenient function of the promises. All variables are expressed | ||
| 90 : | in terms of a common scale of measurement, i.e. one forms an | ||
| 91 : | equivalent graph of directed relationships, at each moment, that has | ||
| 92 : | no labels, only weighted edges. | ||
| 93 : | \bigskip | ||
| 94 : | \begin{definition}[Common Currency Equivalent Graph] | ||
| 95 : | A common currency equivalent graph (CCEG) is a transformation of the | ||
| 96 : | labelled promise graph, in which each promise is reduced to a single | ||
| 97 : | dimensionless value that can be summed. A currency value can be | ||
| 98 : | defined as any linear combination of functions which takes a promise | ||
| 99 : | body as an argument and maps it into the real numbers, e.g. the | ||
| 100 : | probability of the promise being kept. Then the common | ||
| 101 : | currency graph has an adjacency matrix of the general form: | ||
| 102 : | \beq | ||
| 103 : | 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\\ | ||
| 104 : | &=& \alpha_1 f_1(A^1_{ij}) + \alpha_2 f_2(A^2_{ij}) + \ldots | ||
| 105 : | \eeq | ||
| 106 : | where the $A_{ij}^k$ is the adjacency matrix for promises | ||
| 107 : | of type $k$ and agents $i,j$. | ||
| 108 : | \end{definition} | ||
| 109 : | \bigskip | ||
| 110 : | One can formulate a precise definition of how {\em constrained} | ||
| 111 : | autonomous agents are by their voluntary promises to the neighbours, | ||
| 112 : | using the topology of the graph as a guide. In particular, the concept | ||
| 113 : | known as {\em eigenvector centrality} is a useful perspective for | ||
| 114 : | management, which ranks the nodes in a graph according to the | ||
| 115 : | recursively counted involvement in the | ||
| 116 : | network\cite{bonacich1,bonacich2,burgessbook2}. | ||
| 117 : | |||
| 118 : | If one multiplies a row of the adjacency matrix, of ones and zeroes, | ||
| 119 : | by a column vector of ones, this simply counts the number of promises | ||
| 120 : | which that node exchanges with its neighbours. One can use this fact | ||
| 121 : | to self-consistently sum the promises from the entire graph and see | ||
| 122 : | which agents are most entangled. By rescaling, this leads to a unique | ||
| 123 : | ranking in terms of the connectivity. | ||
| 124 : | |||
| 125 : | Since the labelled edges of the promises lead to many typed graphs, | ||
| 126 : | one must decide how to deal with the different labels: whether to separate | ||
| 127 : | them or remove them (see next section). | ||
| 128 : | |||
| 129 : | Let $v_i$ denote a vector for the cooperative ranking of each node $i$. Then, the | ||
| 130 : | importance of node $i$ is proportional to the sum of the importances | ||
| 131 : | of all of $i$'s nearest neighbours ${\cal N}(i)$: | ||
| 132 : | \beq | ||
| 133 : | v_i \propto\sum_{j={\cal N}(i)} v_j . | ||
| 134 : | \label{pevc1} | ||
| 135 : | \eeq | ||
| 136 : | Writing this more compactly gives | ||
| 137 : | \beq | ||
| 138 : | v_i \propto \sum_j A_{ij} v_j \ , | ||
| 139 : | \label{pevc2} | ||
| 140 : | \eeq | ||
| 141 : | where | ||
| 142 : | $A$ is the adjacency matrix, and hence: | ||
| 143 : | \beq | ||
| 144 : | {A}\,\vec{v} =\lambda \vec v \ . | ||
| 145 : | \label{pevcfin} | ||
| 146 : | \eeq | ||
| 147 : | The ranking vector is seen to be an eigenvector of the adjacency | ||
| 148 : | matrix $A$. If $A$ is an $N\times N$ matrix, it has $N$ eigenvectors | ||
| 149 : | (one for each agent in the network), and correspondingly many | ||
| 150 : | eigenvalues. The eigenvalue of interest is the principal eigenvector, | ||
| 151 : | i.e. that with highest eigenvalue, since this is the only one that | ||
| 152 : | results from summing all of the possible pathways with a positive | ||
| 153 : | sign. The components of the principal eigenvector rank how | ||
| 154 : | self-consistently `central' a node is in the graph. Here, it signifies | ||
| 155 : | how many promises an agent is involved in. The highest valued | ||
| 156 : | component is the most ``central'', i.e. the most entangled in | ||
| 157 : | promises. | ||
| 158 : | |||
| 159 : | Applications of the centrality have been | ||
| 160 : | given in refs. \cite{archipelago,roles,burgessbook2} and further | ||
| 161 : | applications for directed graphs are studied in ref. \cite{burgessroles}. | ||
| 162 : | We note some further points: | ||
| 163 : | \begin{itemize} | ||
| 164 : | |||
| 165 : | \item Sources and sinks, signifying incomplete agreements, show up readily | ||
| 166 : | in these graphs and are thus easily identifiable with a simple method. | ||
| 167 : | |||
| 168 : | \item $A^{\rm T}$ gives a higher ranking to the recipient of a | ||
| 169 : | promise, whereas $A$ gives a high ranking to the provider of a | ||
| 170 : | promise. | ||
| 171 : | |||
| 172 : | \item If one takes the undirected common currency graph of all collaborative ``$C(b)$'' promises, | ||
| 173 : | this shows us the collaborations, social structures or roles amongst | ||
| 174 : | the agents. Tightly bound regions will form topological | ||
| 175 : | roles\cite{roles} and the highest ranking node will be that which is | ||
| 176 : | most important in binding the collaborative structure. This is both an | ||
| 177 : | agent that one should be wary of and which should have enough | ||
| 178 : | resources to fulfill its contractual obligations. | ||
| 179 : | |||
| 180 : | \item If one takes the common currency graph of all promises of type $b$ and $U(b)$ | ||
| 181 : | together, these represent bindings. Even though the | ||
| 182 : | promises only have meaning between pairs of nodes, the viewpoint | ||
| 183 : | offered by the eigenvector is the level of entanglement of the agents | ||
| 184 : | in a collaborative network. Again, this allows one to focus attention | ||
| 185 : | on agents where problems more likely will arise. One now has a choice | ||
| 186 : | between ranking by $A^{\rm T}$ or by $A$. | ||
| 187 : | |||
| 188 : | \end{itemize} | ||
| 189 : | |||
| 190 : | \section{Further applications: software management} | ||
| 191 : | |||
| 192 : | Let us draw another parallel with pervasive computing management, | ||
| 193 : | namely software engineering management, and suggest how promise theory | ||
| 194 : | can offer insights into the structure of programming objects. This has | ||
| 195 : | been developed at length in ref. \cite{aredo1}. | ||
| 196 : | |||
| 197 : | A service view of software has been developed in detail, especially | ||
| 198 : | since the example of object orientation, in particular Smalltalk. | ||
| 199 : | Software is a collection of objects, including storage and methods, | ||
| 200 : | which perform services for one another like `granting access' or | ||
| 201 : | `transfer data'. The theory of object orientation has been built up | ||
| 202 : | very much around the tree-like hierarchy, but developments such as | ||
| 203 : | Aspect Oriented Programming underlines the fact that computer programs | ||
| 204 : | are not well modelled by strict hierarchies. | ||
| 205 : | |||
| 206 : | Our theory of promises can be applied to programming by treating every | ||
| 207 : | addressable item in a program as a node in a graph\cite{aredo1}. By | ||
| 208 : | explicitly adding arrows for the services that bind the objects | ||
| 209 : | together, one obtains a graph of the necessary and sufficient | ||
| 210 : | relationships between the objects. The traditional approach to | ||
| 211 : | deciding encapsulation is one of doctrine, but our approach yields an | ||
| 212 : | answer to the natural boundaries based only on the roles in the | ||
| 213 : | promise graph. This graph is constructed only with the principle that | ||
| 214 : | {\em all} objects are private (autonomous) unless they promise to give | ||
| 215 : | up that autonomy in order to cooperate with another. We provide only | ||
| 216 : | the smallest example here as a taster of this approach, to be | ||
| 217 : | expounded elsewhere. | ||
| 218 : | |||
| 219 : | The management of program design involves making a large number of | ||
| 220 : | organizational decisions about objects and their levels of privacy and | ||
| 221 : | encapsulation. Promise theory offers a method for addressing this | ||
| 222 : | issue based on minimalism. We call the result a {\em policy} for | ||
| 223 : | design. One sees that computer programs are examples of pervasive | ||
| 224 : | services. This idea must be explored further elsewhere. | ||
| 225 : | |||
| 226 : | \section{Conclusions and discussion} | ||
| 227 : | |||
| 228 : | As a management tool for understanding and designing policy, promises | ||
| 229 : | have attractive properties; they make hidden assumptions explicit and | ||
| 230 : | thus help one to unravel the requirements for solving different | ||
| 231 : | problems. Promises assist us in assessing the uncertainties | ||
| 232 : | remaining, since they take a more realistic view of cooperation within | ||
| 233 : | a network than many `software driver' models. | ||
| 234 : | |||
| 235 : | There is a close similarity between the promise approach and the | ||
| 236 : | operator approach used by the autonomous agent cfengine, in | ||
| 237 : | configuration management. Although cfengine is not explicitly | ||
| 238 : | concerned with network management, its modus operandi is to build a | ||
| 239 : | policy from atomic promises about certain resources available on | ||
| 240 : | computers that are optionally linked by a network\cite{burgessC1}. | ||
| 241 : | |||
| 242 : | By translating the detailed graph into a graph of common currency, we | ||
| 243 : | can make certain approximations and predictions about their meaning. | ||
| 244 : | For example, research on eigenvectors of directed graphs suggests | ||
| 245 : | that one might be able to reduce some complex questions to very simple | ||
| 246 : | tests\cite{burgessroles}. We hypothesize the following: | ||
| 247 : | \bigskip | ||
| 248 : | \begin{hype}[CCEG minimum requirement] | ||
| 249 : | The minimum requirement for a network policy to be sustainable across | ||
| 250 : | all affected nodes is the existence of a positive definite principal | ||
| 251 : | eigenvector for the adjacency matrix of the common currency equivalent | ||
| 252 : | graph. | ||
| 253 : | \end{hype} | ||
| 254 : | \bigskip | ||
| 255 : | Further work is required to answer this question. However, if true it | ||
| 256 : | would be remarkable, because there is a second motivation for the | ||
| 257 : | common currency graph, namely the economic or cooperative | ||
| 258 : | motivation\cite{siri2}. Our preliminary studies do not contradict this | ||
| 259 : | hypothesis. | ||
| 260 : | |||
| 261 : | We are now in a position to be able to attempt to answer vital | ||
| 262 : | questions in future work. How stable is the network to cooperation? | ||
| 263 : | Could it ever be completely stable or completely unstable? The | ||
| 264 : | models of voluntary cooperation indicate that policy should be | ||
| 265 : | formulated in a way that builds both rewards and punishments into | ||
| 266 : | interactions between peers in order to secure stability. | ||
| 267 : | |||
| 268 : | In this paper we are afforded just enough space to lay the | ||
| 269 : | foundations for studying the uncertainties inherent in pervasive | ||
| 270 : | computing `management'. It remains to be seen how easily these | ||
| 271 : | concepts can be harnessed to develop stable rule-based cooperatives in | ||
| 272 : | the real world. We return to these details in the subsequent papers. | ||
| 273 : |
| Administrator | ViewVC Help |
| Powered by ViewVC 1.0.3 |