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

# Annotation of /trunk/chap_reliability.tex

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 :