Pip:detecting the unexpected in distributed systems.

title: Pip:detecting the unexpected in distributed systems
venue: nsdi 2006
authors: ucsd

Given a running distributed system, how to determine whether or not there is unexpected behavior so far and if yes, where it is? For pip, the basic idea is to capture necessary system behavior online and to run a offline algorithm to check them against user's expectation. (Of coz, there are some options in making such choice, like why not check the unexpected online? why not check all-possible behaviors?)

In such a framework, several detailed issues are posed:
- how to describe behavior of of a distributed system?
- how to express user's expectation for a distributed system?
- how to capture system behavior? what need to capture and what not? (This is left to users and automatic analysis tools (say, mace), by an annotation lib to indicate the PathId for an event.)

1. Behavior model - How to describe behavior of a distributed system?
System behavior is described by a series of path instances, each of which is raised by an outside input (say, a request). Each path instance portraits the internal procedure in the system to answer or to finish the task. It consists of a series of events, organized by their natural causality, (thereby forming a DAG). In a distributed setting, an event could be a task which resides on a single thread (thus on a single host), or a message which help communicate between threads or hosts.

2. Expressing expectation and checking algo.
Given a bunch of path instances and a set of user expectation, Pip checks whether each path could satisfy any of user expectations.

2.1)
Each expectation is a path-validator/invalidator. Each validator consists of several thread patterns, each indicating how a desired thread should run. Within a thread pattern, there are statements and some flexible descriptions of statement flow. A statement is the basic unit of user expectation, including tasks, messages, and notices. Those descriptions include xor and future primitives, flexible enough to capture various program/runtime flows.

The whole technical point is how to model distributed behavior and how to describe it by an expressive language. The difficulty is how to express the prevalent parallelism in every aspect of distributed systems. In essence, how to model a DAG in a language. In this respect, the expectation language is in natural parallel--- no particular order is imposed between thread patterns; within a thread, there are flexible primitives allowing expression of various runtime flow.

2.2) the checking algo.
Given a path instance and an expectation (expressed by a code snippet), checking algo. is to determine whether the path instance follows the expectation. The point here is that the expectation language is design to be expressive and flexible enough, making the matching difficulty. Specifically, the ...