Observation of Distributed Programs

I believe that many problems in concurrent and distributed computing can be cast in the framework of observation and control. My research lab has done a pioneering work in setting up this framework. We initiated and developed a general theory for efficient observation of distributed programs. We proved that even unstable predicates can be detected quite efficiently. This was previously considered impossible. The algorithms for observation of distributed programs have wide applicability in testing and monitoring of distributed programs. I have given several invited talks in this area (keynote speaker at AADEBUG'97, a distinguished speaker at SEKE'96, lecturer at IBM Innovation series, etc.) Some specific accomplishments are given below.

• First algorithm for detecting weak conjunctive predicates: Some examples of weak conjunctive predicates are ``P1 has the write lock and P2 has the read lock'', and ``Both P1 and P2 are in the critical section''. The initial algorithm developed was centralized. First efficient decentralization techniques for the above algorithm were presented in (IEEE ICDCS, June 95). (IEEE Trans. on Parallel and Distributed Systems, 94).
• First algorithm for detecting channel predicates: Many problems studied earlier such as termination detection, deadlock detection, detection of loss of token etc. are special cases of the conjunctive channel predicates and can be solved by the algorithm. (Journal of Parallel and Distributed Computing 97, ).
• Efficient algorithms for relational predicates: These are predicates of the form x1 + x2 + ... + xn < C. These predicates are useful for monitoring resource allocation in distributed systems. The algorithms use Dilworth's Theorem and Max-flow techniques for predicate detection. More recently we have developed online algorithms for this problem. (Journal of Parallel and Distributed Computing, 97, ICDCS 06).
• Lower bound results for Predicate Detection: For example, it was shown that any algorithm based on comparisons must be quadratic in the number of processes. It was also shown that the boolean predicate detection problem is NP-complete (Workshop on Distributed Algorithms, Sept 95).
• Linearity and semi-linearity in predicate detection: Semi-linear predicates form the most general class of predicates for which efficient algorithms for detection are known. They subsume stable predicates and observer-independent predicates defined by earlier researchers. (Distributed Computing, 96)
• Strong unstable predicates: Provided necessary and sufficient conditions to detect strong conjunctive predicates. This class of predicates has applications in testing of distributed programs. (IEEE Trans. on Parallel and Distributed Systems, Dec 96).
• Control-Flow Expressions: In collaboration with INRIA in France, developed the first algorithm to detect a regular expression of local predicates in a distributed program. Also demonstrated applications of computational geometric algorithms for detecting conjunction of global predicates. (IEEE SPDP, October 95, IPL 97)