Chapter11
28 pág.

Chapter11


DisciplinaAlgorítimos Distribuídos28 materiais272 seguidores
Pré-visualização4 páginas
Chapter 11: Global Predicate Detection
Ajay Kshemkalyani and Mukesh Singhal
Distributed Computing: Principles, Algorithms, and Systems
Cambridge University Press
A. Kshemkalyani and M. Singhal (Distributed Computing) Global Predicate Detection CUP 2008 1 / 26
Distributed Computing: Principles, Algorithms, and Systems
Introduction and Uses of Predicate Detection
Industrial process control, distributed debugging, computer-aided verification,
sensor networks
E.g., \u3c8 defined as xi + yj + zk < 100
Different from global snapshots: global snapshot gives one of the values that
could have existed during the execution
Stable predicate: remains true once it becomes true, i.e., \u3c6 =\u21d2 \u3c6
I predicate \u3c6 at a cut C is stable if:
(C |= \u3c6) =\u21d2 (\u2200C \u2032 |C \u2286 C \u2032,C \u2032 |= \u3c6)
I E.g., deadlock, termination of execution are stable properties
A. Kshemkalyani and M. Singhal (Distributed Computing) Global Predicate Detection CUP 2008 2 / 26
Distributed Computing: Principles, Algorithms, and Systems
Stable Properties
Deadlock: Given a Wait-For Graph G = (V ,E ), a deadlock is a subgraph
G \u2032 = (V \u2032,E \u2032) such that V \u2032 \u2286 V and E \u2032 \u2286 E and for each i in V \u2032, i remains
blocked unless it receives a reply from some process(es) in V \u2032.
I (local condition:) each deadlocked process is locally blocked, and
I (global condition:) the deadlocked process will not receive a reply from some
process(es) in V \u2032.
Termination of execution: Model active and passive states, and state
transitions between them. Then execution is terminated if:
I (local condition:) each process is in passive state, and
I (global condition:) there is no message in transit between any pair of
processes.
Repeated global snapshots is not practical!
Utilize a 2-phased approach of observing potentially inconsistent global states.
A. Kshemkalyani and M. Singhal (Distributed Computing) Global Predicate Detection CUP 2008 3 / 26
Distributed Computing: Principles, Algorithms, and Systems
Stable Properties
Deadlock: Given a Wait-For Graph G = (V ,E ), a deadlock is a subgraph
G \u2032 = (V \u2032,E \u2032) such that V \u2032 \u2286 V and E \u2032 \u2286 E and for each i in V \u2032, i remains
blocked unless it receives a reply from some process(es) in V \u2032.
I (local condition:) each deadlocked process is locally blocked, and
I (global condition:) the deadlocked process will not receive a reply from some
process(es) in V \u2032.
Termination of execution: Model active and passive states, and state
transitions between them. Then execution is terminated if:
I (local condition:) each process is in passive state, and
I (global condition:) there is no message in transit between any pair of
processes.
Repeated global snapshots is not practical!
Utilize a 2-phased approach of observing potentially inconsistent global states.
A. Kshemkalyani and M. Singhal (Distributed Computing) Global Predicate Detection CUP 2008 3 / 26
Distributed Computing: Principles, Algorithms, and Systems
Stable Properties
Deadlock: Given a Wait-For Graph G = (V ,E ), a deadlock is a subgraph
G \u2032 = (V \u2032,E \u2032) such that V \u2032 \u2286 V and E \u2032 \u2286 E and for each i in V \u2032, i remains
blocked unless it receives a reply from some process(es) in V \u2032.
I (local condition:) each deadlocked process is locally blocked, and
I (global condition:) the deadlocked process will not receive a reply from some
process(es) in V \u2032.
Termination of execution: Model active and passive states, and state
transitions between them. Then execution is terminated if:
I (local condition:) each process is in passive state, and
I (global condition:) there is no message in transit between any pair of
processes.
Repeated global snapshots is not practical!
Utilize a 2-phased approach of observing potentially inconsistent global states.
A. Kshemkalyani and M. Singhal (Distributed Computing) Global Predicate Detection CUP 2008 3 / 26
Distributed Computing: Principles, Algorithms, and Systems
Two-phase Observation of Global States
In each state observation, all local variables
used to define the local conditions, as well
as the global conditions, are observed.
Two potentially inconsistent global states
are recorded consecutively, such that the
second recording is initiated after the first
recording has completed. Stable property
true if:
I The variables on which the local
conditions as well as the global
conditions are defined have not
changed in the two observations,
as well as between the two
observations.
Recording 2 snapshots serially via
ring/tree/flat-tree based algorithms (Chap
8).
event at which local variables are sampled
P
P
P
P
2
1
n\u22121
n
phase 2phase 1
time
Figure 11.1: Two-phase detection of a stable
property.
None of the variables changes between the two
observations
\u21d2 after the termination of the first observation
and before the start of the second observation,
there is an instant when the variables still have
the same value.
\u21d2 the stable property will necessarily be true.
A. Kshemkalyani and M. Singhal (Distributed Computing) Global Predicate Detection CUP 2008 4 / 26
Distributed Computing: Principles, Algorithms, and Systems
Unstable Predicates: Challenges in Detection
Challenges:
unpredictable propagation times, unpredictable process scheduling \u21d2
I multiple executions pass through different global states;
I predicate may be true in some executions and false in others
No global time \u21d2
I monitor finds predicate true in a state but predicate may never have been true
(at any instant)
I even a true predicate may be undetected due to intermittent monitoring
Observations:
examine all states in an execution \u21d2 define predicate on observation of entire
execution
Multiple observations of same program may pass thru\u2019 different global states;
predicate may be true in some observations but not others \u21d2 define
predicate on all the observations of the distributed program
A. Kshemkalyani and M. Singhal (Distributed Computing) Global Predicate Detection CUP 2008 5 / 26
Distributed Computing: Principles, Algorithms, and Systems
Modalities on Predicates
Possibly(\u3c6): There exists a consistent
observation of the execution such that predicate
\u3c6 holds in a global state of the observation.
Definitely(\u3c6): For every consistent observation
of the execution, there exists a global state of it
in which predicate \u3c6 holds.
(0, 0), e12 , (0, 1), e
1
1 , (1, 1), e
2
2 , (1, 2), e
2
1 , (2, 2), e
3
2 , (2, 3),
e42 , (2, 4), e
3
1 , (3, 4), e
4
1 , (4, 4), e
5
2 , (4, 5), e
5
1 ,
(5, 5), e61 , (6, 5), e
6
2 , (6, 6), e
7
2 , (6, 7)
(a)
1
2
2
local
var.
var.
local
time
e e e e e e
e e e ee ee2 2 2 2 2 2
2
3 5 6 7
1 1 1 1 1 1
1 3 4 5 6
4
a = 3 a = 8 a = 0
b = \u22123b = 2 b = 5 b = 7 
1
2
p
p
Definitely(a + b = 10)
Possibly(a + b = 5)
(b)
0,0
0,1
0,2
1,2
2,2
2,0
1,0
1,1
2,1
6,2
5,2
4,2
3,2
2,5
2,4
2,3
3,3
4,4
5,5
6,6
3,5
4,56,3
5,3
4,3
6,4
5,4
3,4
6,5 5,6
5,7
6,7final state
initial state
a+b = 10
a+b = 5
a+b = 5a+b = 5
a+b = 10
P2P1
Complexity: O(mn), where
there are m events at each of
the n processes.
A. Kshemkalyani and M. Singhal (Distributed Computing) Global Predicate Detection CUP 2008 6 / 26
Distributed Computing: Principles, Algorithms, and Systems
Centralized Algorithm for Relational Predicates
Assume state lattice is available.
Global state GS = {sk11 , sk22 , . . . , sknn } is
abbreviated GSk1,k2,...kn .
Level of a global state \u3008skii (\u2200i)\u3009 is
\u2211i=n
i=1 ki .
Possibly(\u3c6): examine the state lattice
level-by-level, from the initial state at level
0 up to the final state. If \u3c6 is true,
return(1).
Definitely(\u3c6): Sufficient but not necessary
that all states at some level satisfy \u3c6.