Promise Theory - Computer Networks and Distributed Systems

1 downloads 194 Views 284KB Size Report
Feb 27, 2007 - Computing devices mutate into objects that users own. A policy is ... of type τ, which describes the dom
Promise Theory [1, 3] Vladislav Marinov

February 27, 2007

Vladislav Marinov

Promise Theory [1, 3]

1

Outline 1

Motivation

2

Definitions

3

Promise Types

4

Promise Rules

5

Roles

6

A Theory of Network Management

7

Conclusion

8

References

Vladislav Marinov

Promise Theory [1, 3]

2

Motivation

How do we arrange for a consistent policy among the nodes in a distributed system? A policy is imposed by a central authority ”Only that which is programmed happens” Computing devices mutate into objects that users own

A policy is negotiated using autonomous decisions ”Only that which is promised can be predicted” Consistency and consensus about a policy is achieved by voluntary cooperation among nodes Basic foundation of Promise Theory

Vladislav Marinov

Promise Theory [1, 3]

3

Motivation

How do we arrange for a consistent policy among the nodes in a distributed system? A policy is imposed by a central authority ”Only that which is programmed happens” Computing devices mutate into objects that users own

A policy is negotiated using autonomous decisions ”Only that which is promised can be predicted” Consistency and consensus about a policy is achieved by voluntary cooperation among nodes Basic foundation of Promise Theory

Vladislav Marinov

Promise Theory [1, 3]

3

Some Definitions

Policy Based Management - Systems are configured by specifying constraints on their allowable states and behavior. A policy is a set of rules expressing some constraints.

Autonomy - No agent can force any other agent to accept or transmit information, alter its state, or otherwise change its behavior. Agent Node - an autonomous entity in a graph An autonomous agent takes decisions on its own. An sutonomous agent is concerned only with controlling of ONLY its own policy, resources, states etc.

Vladislav Marinov

Promise Theory [1, 3]

4

Promise Definition Promise - A promise is a labelled edge < n1 , π, n2 > in a graph whose nodes ni are agents. A promoise is denoted by n1 →π n2 which is interpreted as ”n1 asserts its compliance with a policy constraint π to n2 ”. The promise body consists of type τ , which describes the domain of possibility, and a constraint χ which specifies the restriction imposed by the policy. No promise constraints should refer to the identities of agents in a graph Example (Service Level Agreement) - An agent X promises π : χ ⊆ τ to agent Y , i.e. to provide service type ”database access in time q”, τ is the type domain q ∈ [0, ∞] and the constraint χ(q) : 0 < q < 10ms

Vladislav Marinov

Promise Theory [1, 3]

5

Types of Promise

service promise - denotes a restriction of the behavior by the promising agent in the manner of a service. a →π b

usage or acceptance promise - promise to receive or use a service π promised by another agent. a →U(π) b

coordination or subordination promise - promise to do the same as another agent w.r.t. a promise body π a →C (π) b

Vladislav Marinov

Promise Theory [1, 3]

6

Cooperative Promise Rule n1 promises p to n3 n2 promises n1 to collaborate about p n1 promises n2 to collaborate about p n2 promises p to n3

Vladislav Marinov

Promise Theory [1, 3]

7

Conditional Dependency

n1 : database server n2 : web server n3 : client p1 : n1 promises to n2 ”will send database data in less than 5ms” Can n2 now promise to n3 ”will send data in less than 10ms”? n2 has no obligation to use the data promised by n1 n2 promises its web service no matter what n1 promises Neither n1 nor n3 can force n2 to act as a conduit

Vladislav Marinov

Promise Theory [1, 3]

8

Conditional Dependency’contd

A promise to uphold p1 from n1 → n2 An acceptance promise from n2 → n1 to use p1 A conditional promise from n2 → n3 to uphold p2 iff p1 is both present and accepted.

Vladislav Marinov

Promise Theory [1, 3]

9

Transfer of Responsibility

Consider agents a, b and c and b has resource B How does b express to a: ”You may have access to B but don’t pass it to c” Refers to the identity of c Refers to potential promise from a to c Refers to B which a has no access to or prior knowledge of

Vladislav Marinov

Promise Theory [1, 3]

10

Transfer of Responsibility’contd b promises B along b → a (service promise) a promises that it will use B along a → b (usage promise) b makes a promise to not send B along b → c (service promise) a makes a promise to collaborate about the promise ”not B” along a → b (cooperative promise) This implies that a make a promise of ”not B” along a → c

Vladislav Marinov

Promise Theory [1, 3]

11

Roles appointed role - a node or a group of nodes that are being pointed to by a set of identical promise arrows cooperative role - a group of nodes that is united by making coordination/subordination promise to one another about a certain promise. association role - uncoordinated agents that happen to make the same promises All web servers promise http service to clients

Vladislav Marinov

Promise Theory [1, 3]

12

Simplification Using Roles

(a) Graph showing promises between (b) Simplified graph of promises by in15 agents troducing roles

Vladislav Marinov

Promise Theory [1, 3]

13

Management Using Promise Theory

Are there any logical errors or missing agreements in the network? Which nodes are providing services with acceptable SLAs? What roles are necessary to distinguish or extend functionality? Where are the vulnerable parts of the cooperative network? What is the probability that a failure will be fatal?

Vladislav Marinov

Promise Theory [1, 3]

14

Common Currency Equivalent Graph

Convert the labelled promise graph into a graph with link costs of common currency The common currency could be ”probability that a promise is kept” Compute the adjacency matrix Aij = α1 f1 (ni →π1 nj ) + α2 f2 (ni →π2 nj ) + ...

Vladislav Marinov

Promise Theory [1, 3]

15

Ranking Vector The more promises a node makes, the more important it is in the network vi - Cooperative ranking vector for node i - The importance of a node is proportional to the sum of importances of its neighbours N(i) Some math.... P vi ∝ vj j=N(i) P vi ∝ Aij vj j=N(i)

− → A→ v = λ− v The ranking vectors vi are the eigenvectors for the matrix A The node associated with the highest eigenvalue is the most entangled node in the network

Vladislav Marinov

Promise Theory [1, 3]

16

Conclusion

Promise Theory provides a framework for policy-based management of autonomous systems Agents negotiate policies voluntarily Can be used to manage services in a network Can be used to detect inconsistensies in policies

Can utilize the analysis and visualization techniques from graph theory Roles can be used to simplify a graph Can be used in many practical areas [2] BGP Game Theory Intelligent Swarms

Vladislav Marinov

Promise Theory [1, 3]

17

References M. Burgess and S. Fagernes. Pervasive computing management: A model of network policy with local autonomy. IEEE Transactions on Networking, page (submitted). M. Burgess and S. Fagernes. Promise theory - a model of autonomous objects for pervasive computing and swarms. Networking and Services, ICNS ’06, page (submitted), 2006. Mark Burgess. An approach to policy based on autonomy and voluntary cooperation. Lecture Notes on Computer Science, 3775:97–108, 2005.

Vladislav Marinov

Promise Theory [1, 3]

18