#Number
TR-PDS-1997-011


#Title
Addressing False Causality while Detecting Predicates in Distributed Programs


#Author
Ashis Tarafdar
Vijay K. Garg


#Abstract
The partial-order model of distributed computation based on the
"happened before" relation has been criticized for allowing "false
causality" between events in distributed programs. To address this
problem, we extend this model to "strong causality diagrams" which
allow independent local events, and capture the semantics of multiple
local threads of control.

This paper addresses the "predicate detection problem" in the strong
causality model of a distributed computation. Our focus is on the
useful class of "weak conjunctive predicates". We show that, in
general, the problem is NP-complete. However, an efficient solution is
demonstrated for a useful class of strong causality diagrams.  Further,
we 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.


#Bib
@TechReport{,
  author =   "Ashis Tarafdar and Vijay K. Garg",
  title =    "Addressing False Causality while Detecting Predicates in Distributed Programs",
  institution =  "Parallel and Distributed Systems Laboratory, ECE
                  Dept. University of Texas at Austin",
  year =         "1997",
  number =    "ECE-PDS-1997-011",
  note =     "available via ftp or WWW at maple.ece.utexas.edu
          as technical report TR-PDS-1997-011"
}