Monitoring Multithreaded Distributed Computations

Monitoring Multithreaded Distributed Computations

Vijay K. Garg

Department of Electrical and Computer Engineering

The University of Texas at Austin Austin, TX 78712 email: garg@ece.utexas.edu

Motivation: Software Faults

• Software faults are dominant reasons for system outages

• Approx 2 to 3 bugs per 1000 lines of code! [Gray and Reuter 93]

Testing and Debugging: • Distributed programs are prone to errors.

• Traces need to be analyzed to locate bugs.

Software Fault-Tolerance: • Software fault detection

• Rollback Recovery

Monitoring Multithreaded Distributed Computations

Our Approach

• Three abstractions defined: predicate detection, predicate control and slicing.

Talk Outline

• Motivation

• Predicate Detection

• Computation Slicing

• Predicate Control

• Ongoing and Future Work

Monitoring Multithreaded Distributed Computations

System Model

Y  X p_{1} p_{2}  a  b  d c  m

computation: a set of events ordered by “happened before” relation consistent cut: subset of events that have been executed so far

e.g., X is a consistent cut but Y is not

Predicate Detection Problem

Predicate: A global condition expressed using variables on processes e.g., more than one process is in critical section, there is no token in the system Problem: find a consistent cut that satisfies the given predicate Exponential algorithm for general predicate [Cooper and Marzullo 91] Polynomial algorithm for conjunctive predicate [Garg and Waldecker 91]

X  Y p_{1} p_{2}  critical sections
January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 6

Motivation for Predicate Detection

Dear Watson, you see but you do not observe...

• Distributed Debugging, Testing

– stop when the predicate q is true predicate q = (P1 is in critical section) and (P2 is in critical section).

– Detect if the program violates any invariant

• Fault-tolerance – Monitoring while the program is operational

• Distributed Active Rules – On global condition p, trigger rule a

• General paradigm for observing Distributed Algorithms – Termination detection, deadlock detection, loss of token

The Main Difficulty

a  b p_{1}  c  d  e p_{2}  {a}  {}  {c} {a, c} {a, b} {a, b, c} {a, b, c, d} {a, c, d} {a, c, d, e} {a, b, c, d, e}

• NP-complete for a conjunction of clauses such that each clause is a disjunction of at most two variables [Mittal and Garg 01]

e.g., (x_{1} ∨ x_{2}) ∧ (x_{3} ∨ x_{4}) ∧ ⋯ ∧ (x_{n−1} ∨ x_{n})

Problem: Too many consistent cuts (global states)

A computation may contain as many as O(k^{n}) consistent cuts k: maximum number of events on a process, n: number of processes

Predicate Detection for Special Cases

Exploit the structure of the predicate:

• stable predicate: [Chandy and Lamport 85] once the predicate becomes true, it stays true e.g., deadlock

• unstable predicate:

– observer independent predicate [Charron-Bost et al 95] occurs in one interleaving ⇒ occurs in all interleavings e.g., any local predicate

– relational predicate: x_{1} + x_{2} + ⋯ + x_{n} ⩾ k [Chase and Garg 95] e.g., violation of mutual exclusion

– linear predicate [Chase and Garg 95] closed under intersection, e.g., conjunctive predicates such as there is no leader in the system

Conjunctive Predicates

A predicate that can be expressed as l_{1} ∧ l_{2} ∧ … ∧ l_{n}, where l_{i} is local to P_{i}.

Examples:

• mutual exclusion problem: (P1 in CS) and (P2 in CS)

• missing primary: (P1 is secondary) and (P2 is secondary) and (P3 is

secondary) Detect errors that may be hidden in some run due to race conditions.

Importance of Conjunctive Predicates

Sufficient for detection of any global

• boolean expression of local predicates which can be expressed as a disjunction of a small number of conjunctions.

Example: x, y and z are in three different processes. Then, even(x) ∧ ((y < 0) ∨ (z > 6)) ≡ (even(x) ∧ (y < 0))∨ (even(x) ∧ (z > 6))

• predicate satisfied by only a small number of values Example: x and y are in different processes. (x = y) is not a local predicate but x and y are binary.

Monitoring Multithreaded Distributed Computations

Conditions for Conjunctive Predicates

Possibly (l_{1} ∧ l_{2} ∧ … l_{n}) is true iff there exist s_{i} in P_{i} such that l_{i} is true in state s_{i}, and s_{i} and s_{j} are incomparable for distinct i, j.

January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 12

Monitoring Multithreaded Distributed Computations

Tracking Causality: Clocks in a Distributed System

Result: s happened before t iff the vector at s is less than the vector at t. Vector Clocks [Fidge 89, Mattern 89]

January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 13

Monitoring Multithreaded Distributed Computations

Dynamic Chain Clocks

Problem with vector clocks: scalability Idea: Computing the “chains” in an online fashion [Aggarwal and Garg 04]

Figure 1: (a) A computation with 4 processes (b) The relevant subcomputation

January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 14

Experimental Results

Simulation of a computation with 1% relevant events Measured

• number of components vs number of threads • total time overhead vs number of threads

Weak Conjunctive Predicates: Centralized Algorithm

[Garg and Waldecker 92] Each non-checker process maintains its local vector and sends to the checker process the chain clock whenever

• local predicate is true

• at most once in each message interval.

January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 16

Overhead: Checker processes

Space complexity: n queues, each containing at most m vectors

Time complexity:

• The algorithm for checker requires at most O(n^{2}m) comparisons.

• Any algorithm which determines whether there exists a set of incomparable vectors of size n in n chains of size at most m, makes at least mn(n − 1)/2 comparisons. [Garg and Waldecker 94]

Predicate Detection in General

{a}  {}  {c} {a, c} {a, b} {a, b, c} {a, b, c, d} {a, c, d} {a, c, d, e} {a, b, c, d, e} Construct the state-space (need to examine all consistent cuts)

• breadth first manner [Cooper and Marzullo 91] space-complexity: number of consistent cuts

• depth first manner [Alagar and Venkatesan 94] space-complexity: number of events

• lexical order [Garg 03]

space-complexity: number of processes

January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 18

Talk Outline

• Motivation

• Predicate Detection Problem • Computation Slicing

• Predicate Control

• Ongoing and Future Work

Monitoring Multithreaded Distributed Computations

The Main Idea of Computation Slicing

slicing computation slice  retain all red consistent cuts
January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 20

Monitoring Multithreaded Distributed Computations

How does Computation Slicing Help?

slicing  cuts that satisfy b_{1} computation slice for b_{1} detect b_{1} ∧ b_{2} detect b^{2}  retain all consistent satisfy b_{1}
January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 21

Monitoring Multithreaded Distributed Computations

Example

Detect predicate (x_{1} ∗ x_{2} + x_{3} < 5) ∧ (x_{1} ≥ 1) ∧ (x_{3} ≤ 3)

Slice with respect to (x_{1} ≥ 1) ∧ (x_{3} ≤ 3)

January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 22

Computation Slice

computation slice: a sub-computation such that: [Mittal and Garg 01]

(1) it contains all consistent cuts of the computation satisfying the given predicate, and

(2) it contains the least number of consistent cuts

sub-computation e.g. computation e.g.  {b} {c} {a, d} a  b c  d  e.g. all sent messages have been received predicate Slicer
January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 23

Monitoring Multithreaded Distributed Computations

Example: Conjunctive Predicate

{e, f} 2 −1 1 y = 0 −1 2  1 x = 0  c e  (x ⩾ 0) ∧ (y ⩾ 0) slicing  {d} {a, b} {c} p_{1} p_{2}  a  b  f d

Monitoring Multithreaded Distributed Computations

Example: Channel Predicate

{d, f} slicing no messages in transit d  f  {b} {a, c} {e} a c e p_{1} p_{2} p^{3}  b

Monitoring Multithreaded Distributed Computations

Third Example

2 −1 1 y = 0 −1 2  1 x = 0  c e  slicing x + y ⩽ 2 p_{1} p_{2}  a  b  f d

Monitoring Multithreaded Distributed Computations

Slicing Example

d  f  ⟹ a c e p_{1} p_{2} p_{3}  b  {e} {} {a}  {a, c}  {a, e} {a, b} {a, b, c}  {a, b, e}  {a, c, d}  {a, c, e} {a, c, d, e} {a, b, c, d} {a, b, c, d, e}  {a, c, d, e, f} {a, b, c, e} {a, b, c, d, e, f}
January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 27

Characterization of Consistent Cuts

The set of consistent cuts of a computation forms a distributive lattice

(1) The set forms a lattice • if X and Y are consistent cuts then so are X ∩ Y and X ∪ Y • meet (infimum, greatest lower bound) → intersection

• join (supremum, least upper bound) → union

(2) The lattice is distributive • meet distributes over join

Monitoring Multithreaded Distributed Computations

Join-irreducible Elements

A join-irreducible element has exactly one incoming edge

{e} {} {a}  {a, c}  {a, e} {a, b} {a, b, c}  {a, b, e}  {a, c, d}  {a, c, e} {a, c, d, e} {a, b, c, d} {a, b, c, d, e}  {a, c, d, e, f} {a, b, c, e} {a, b, c, d, e, f}
January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 29

Monitoring Multithreaded Distributed Computations

Birkhoff’s Representation Theorem

A distributive lattice can be recovered exactly from the set of its join-irreducible elements

Y  Z^{⟺}^{U}  ^{V}^{W}  ^{X}  ^{Y}^{Z}  W U X V^{{e}}^{{}}^{{a}}  ^{{a, c}}  ^{{a, e}}^{{a, b}}^{{a, b, c}}  ^{{a, b, e}}  ^{{a, c, d}}  ^{{a, c, e}}^{{a, c, d, e}}^{{a, b, c, d}}^{{a, b, c, d, e}}  ^{{a, c, d, e, f}}^{{a, b, c, e}}^{{a, b, c, d, e, f}}
January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 30

Monitoring Multithreaded Distributed Computations

What about a Subset of Consistent Cuts?

X  Y X ∩ Y X ∪ Y  {e} {} {a}  {a, c}  {a, e} {a, b} {a, b, c}  {a, b, e}  {a, c, d}  {a, c, e} {a, c, d, e} {a, b, c, d} {a, b, c, d, e}  {a, c, d, e, f} {a, b, c, e} {a, b, c, d, e, f}

X in subset and Y in subset ⇒ X ∩ Y in subset and X ∪ Y in subset

sublattice: subset of consistent cuts closed under intersection and union

January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 31

Monitoring Multithreaded Distributed Computations

Representing a Sublattice

A sublattice of a distributive lattice is also a distributive lattice

⇒ A sublattice has a succinct representation

{d, f} Z  ^{⟺}^{⟺}^{W}  ^{X}^{Z}^{Y}  {b} {a, c} {e} X  Y W^{{e}}^{{a, c}}^{{a, b, c}}  ^{{a, c, d, e, f}}^{{}}  ^{{a, c, e}}^{{a, b, c, e}}^{{a, b, c, d, e, f}}
January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 32

Monitoring Multithreaded Distributed Computations

What if the Subset is not a Sublattice?

Add consistent cuts to complete the sublattice

⟹ {e} {a, c} {a, b, c}  {a, c, d, e, f} {a, c, e} {}  {e} {a, c} {a, b, c}  {a, c, d, e, f} {a, b, c, e} {a, b, c, d, e, f}{a, c, e} {}
January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 33

Computing the Slice

Algorithm:

(1) Find all consistent cuts that satisfy the predicate

(2) Add consistent cuts to complete the sublattice

(3) Find the basis elements of the sublattice

Can we find the basis elements without computing the sublattice?

Regular Predicate

regular predicate: the set of consistent cuts satisfying the predicate is closed under intersection and union [Garg and Mittal 01]

Examples:

• conjunctive predicate—conjunction of local predicates

• there are at most (or at least) k messages in transit from process i to process j

• every “request” message has been “acknowledged” in the system

The class of regular predicates is closed under conjunction:

If b_{1} and b_{2} are regular predicates then so is b_{1} ∧ b_{2}

Monitoring Multithreaded Distributed Computations

Computing the Slice for Regular Predicate

x  z v u w y p_{1} p_{2} p^{3}

b = “no messages in transit”

Algorithm:

Step 1: Compute the least consistent cut L that satisfies b
L = {}
Step 2: Compute the greatest consistent cut G that satisfies b
G = {u, v, w, x, y, z}
January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 36

Computing the Slice for Regular Predicate

Algorithm:

Step 3: For every event e ∈ G − L, compute L(e) defined as:

(1) L(e) contains e

(2) L(e) satisfies b

(3) L(e) is the least consistent cut satisfying (1) and (2)

x  z v u w y p_{1} p_{2} p_{3} L(u) = L(w)

L(u) = {u, w} L(v) = {u, v, w} L(w) = {u, w} (duplicate) L(x) = {u, w, x, y, z} L(y) = {y} L(z) = {u, w, x, y, z} (duplicate)

Results

Efficient polynomial-time algorithms for computing the slice for:

• regular predicate: [Garg and Mittal 01] time-complexity:

– general: O(n^{2}m)

– special cases (e.g., conjunctive predicate): O(m)

• general predicate:

Theorem: Given a computation, if a predicate b can be detected efficiently then the slice for b can also be computed efficiently. [Mittal, Sen and Garg 02]

n: number of processes m: number of events

Experimental Evaluation: Dining Philosophers Verification

POTA: Partial Order Trace Analyzer (based on slicing) [Sen and Garg 03] SPIN: A widely used model checking tool [Holzmann 97]

SPIN: 250 seconds for n = 6, runs out of memory for n > 6. POTA: can handle n= 200. Used 400 seconds. Predicate: Two neighboring dining philosophers do not eat concurrently

Talk Outline

• Motivation

• Predicate Detection Problem • Computation Slicing

• Predicate Control

• Ongoing and Future Work

Motivation for Control

Who controls the past controls the future, who controls the present controls the past...

George Orwell,

Nineteen Eighty-Four.

• maintain global invariants or proper order of events Examples: Distributed Debugging

– ensure that busy_{1} ∨ busy_{2} is always true

– ensure that m_{1} is delivered before m_{2}

• Resource Allocation – maintain ¬CS_{1} ∨ ¬CS_{2}

• Fault tolerance – On fault, rollback and execute under control

• Adaptive policies

Rollback Recovery for Software Faults

faulty state p_{3} p_{2} p_{1}  restored state

Re-execution Problem: To re-execute in order to avoid a recurrence of a previously detected failure

– Progressive Retry [Wang et al 97]

– Controlled Re-execution [Tarafdar and Garg 98]

Monitoring Multithreaded Distributed Computations

Controlled Re-execution

a c b d  a c b d p_{1} p_{2}  X  p_{1} p_{2}  X critical sections

Add the synchronization necessary to maintain safety property e.g., mutual exclusion

Monitoring Multithreaded Distributed Computations

The Main Difficulty

a  b d c  a  b d c  fault-free a  b c  d p_{1} p_{2}  p_{1} p_{2} p_{1} p_{2}  deadlock
January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 44

Results

Efficient algorithms for computing the synchronization for: • Locks [Tarafdar and Garg 98]

– time-complexity: O(nm)

• disjunctive predicate [Mittal and Garg 00] e.g., (n − 1)-mutual exclusion

– time-complexity: O(m^{2})

– minimizes the number of synchronization arrows

• region predicate [Mittal and Garg 00] e.g., virtual clocks of processes are “approximately” synchronized – time-complexity: O(nm^{2})

– maximizes the concurrency in the controlled computation

n: number of processes, m: number of events

January 3, 2005  ECE Dept., Univ. Texas at Austin  Page 45

Ongoing and Future Work

• Predicate Detection: Temporal logic predicates (Anurag Agarwal), Online relational predicates (Selma Ikiz)

• Slicing: Distributed and online algorithms (Vinit Ogale)

• Predicate Control: Controlling message order (Arindam Chakraborty)

• Model Checking: Based on predicate detection and slicing (Sujatha Kashyap)

Acknowledgments

Collaborators on various ideas Anurag Agarwal Craig M. Chase, Eddy Fromentin, Richard Kilgore, Ratnesh Kumar, James R. Mitchell, Neeraj Mittal, Venkat V. Murty, Michel Raynal, Alper Sen, Chakarat Skawratonand, Ashis Tarafdar, Alex I. Tomlinson, and Brian Waldecker