Title:

Addressing False Causality while Detecting Predicates in Distributed Programs


Authors:

Ashis Tarafdar and Vijay K. Garg


Abstract: 

Partial-order models of distributed computation, based on the "happened
before" relation, have been criticized for allowing "false causality"
between events in distributed programs. We, therefore, extend this
model to "dependency diagrams", which allow independent local events,
and capture the semantics of multiple local threads of control.

We address the "predicate detection problem" in the dependency diagram
model of a distributed computation. We focus on the useful class of
"weak conjunctive predicates". We show that, in general, the problem is
NP-complete. However, we demonstrate an efficient solution for a useful
class of dependency diagrams.  We further show how this solution can be
used to achieve an exponential reduction in the time taken to solve the
general problem.

The main application of predicate detection is in debugging and testing
distributed programs. Our predicate detection algorithms in the extended
model can be applied to distributed debugging and testing when the
processes have independent events, as in the case of multi-threaded
processes.


Subject Areas:  

Distributed Software Engineering and Languages
Distributed Algorithms and Verification Techniques