#Number
TR-PDS-1994-004

#Title
An efficient decentralized algorithm for detecting 
properties of distributed computations

#Author
Vijay K Garg
Alex Tomlinson
Eddy Fromentin
Michel Raynal

#Abstract
This paper presents a simple yet powerful logic for expressing
properties of distributed computations, and an efficient
decentralized algorithm for detection of these properties
concurrent with the underlying computation.  A class of
detection algorithms is defined which are efficient and
passive.  By our definition, a passive algorithm can only
observe the underlying computation; that is, it cannot alter
the control flow and cannot initiate or inhibit any message
activity.

The properties are expressed as formulas on the global past of
local states.  Several motivating examples of the logic are
presented.  A detection algorithm which uses message tags is
presented and proven correct.  The following result is also
proven: our algorithm can detect everything that any other
efficient passive detection algorithm can detect.

#Bib
@TechReport{,
  author = 	 "V.K. Garg and A.I. Tomlinson and E. Fromentin and
		  M. Raynal", 
  title = 	 "An efficient decentralized algorithm for detecting
		  properties of distributed computations", 
  institution =  "Parallel and Distributed Systems Laboratory, The
		  University of Texas at Austin", 
  year =	 1994,
  number =	 "TR-PDS-1994-004",
  note =	 "available via ftp or WWW at maple.ece.utexas.edu"
}