From kapil@cs.utexas.edu Tue May 7 19:11:21 1996 Return-Path: kapil@cs.utexas.edu Received: from mail.cs.utexas.edu (root@mail.cs.utexas.edu [128.83.139.10]) by pine.ece.utexas.edu (8.6.9/8.6.5) with ESMTP id TAA04226 for ; Tue, 7 May 1996 19:11:20 -0500 Received: from jeckle.cs.utexas.edu (kapil@jeckle.cs.utexas.edu [128.83.143.207]) by mail.cs.utexas.edu (8.7.1/8.7.1) with ESMTP id TAA10253 for ; Tue, 7 May 1996 19:11:17 -0500 (CDT) Received: by jeckle.cs.utexas.edu (8.7.1/Client-1.4) id TAA48340; Tue, 7 May 1996 19:11:15 -0500 Message-Id: <199605080011.TAA48340@jeckle.cs.utexas.edu> From: kapil@cs.utexas.edu (Kapil Gupta) Date: Tue, 7 May 1996 19:11:15 -0500 X-Mailer: Mail User's Shell (7.2.5 10/14/92) To: vijay@pine.ece.utexas.edu Subject: bibliography for global predicate detection ... Status: R Hi Dr. Garg, Thanks for letting me borrow those two papers. They were a big help. I am attaching a postscript version of the bibliography below. Kapil ------------------------------------------------------------------- \documentstyle[11pt]{article} \bibliographystyle{plain} \thispagestyle{empty} \title{Annotated Bibliography on Global Predicate Detection} \author{Kapil Gupta} \begin{document} \maketitle \section* {\bf Chandy and Lamport 1985} K.M. Chandy and L. Lamport. Distributed snapshots: Determining global states of distributed systems. {\it ACM Transactions on Computer Science}, Vol 3, No. 1, 63-75, February 1985. \\ \\ Chandy and Lamport were the first to give an algorithm for computation of a meaningful global snapshot. This paper presents the classic ``distributed snapshot'' algorithm which is intended to provide a general purpose framework which can be adapted to specific implementation requirements. However the approach works only for stable predicates and does not give any indication as to when the snapshot needs to be taken. \section* {\bf Spezialetti and Kearns 1986} M. Spezialetti and P. Kearns. Efficient Distributed Snapshots. In {\it Proceedings of the $6^{th}$ International Conference on Distributed Computing Systems}, 382-388, 1986. \\ \\ This paper presents efficient algorithms to disseminate a global snapshot to processes initiating the snapshot computation. The authors have modified the algorithm proposed by Chandy and Lamport so that the earlier phase can provide useful information to the later phase which may be utilized to advantage by the later phase. This modified algorithm is more efficient for repeated snapshots and is thus suitable for stable predicate detection. \section* {\bf Miller and Choi 1988} B.P. Miller and J. Choi. Breakpoints and halting in distributed programs. In {\it Proceedings of the $8^{th}$ IEEE International Conference on Distributed Computing Systems}, San Jose, 316-323, July 1988. \\ \\ This paper discusses detection of linked predicates, basically a causal sequence of local states verifying some predicates. This was the first paper describing such a behavioral pattern in the system. The algorithm proposed does not require building the lattice or using a centralized manager and uses a simple piggy-backing technique to ensure consistency in the detection. \section* {\bf Spezialetti and Kearns 1989} M. Spezialetti and P. Kearns. Simultaneous Regions: A Framework for the Consistent Monitoring of Distributed Systems. In {\it Proceedings of the $9^{th}$ International Conference on Distributed Computing Systems}, Newport Beach, 61-68, July 1989. \\ \\ In this paper the authors have define a notion of simultaneity which is used to combine local states into a globally consistent state. Predefined predicates are evaluated for each global state, and if the predicate holds, a so-called {\it global event occurrence} is recognized. However there is a basic flaw in their definition of simultaneity, due to which the algorithm may fail to detect a global event occurrence. \section* {\bf Fowler and Zwaenepoal 1990} J. Fowler and W. Zwaenepoal. Causal Distributed Breakpoints. In {\it Proceedings of the $10^{th}$ International Conference on Distributed Computing Systems}, Paris, France, 134-141, May 1990. \\ \\ This paper proposes an algorithm to compute {\it causal distributed breakpoint}. When one process of a distributed computation is halted at a breakpoint, the causal distributed breakpoint shows the other processes in the computation in their earliest state that reflects all events that happened before the breakpoint. \section* {\bf Cooper and Marzullo 1991} R. Cooper and K. Marzullo. Consistent detection of global predicates. In {\it Proceedings of the ACM/ONR Workshop on Parallel and Distributed Debugging}, Santa Cruz, CA, 163-173, May 1991. \\ \\ Cooper and Marzullo were the first to use the construction of the lattice of global states to detect arbitrary global predicates. This approach allows the user to detect {\it definitely}: q and {\it possibly}: q where q is any predicate defined on a single global state. This approach works even for unstable predicates. However given $n$ processes each with $m$ ``relevant'' local states, their off-line algorithm requires exploring $O(m^n)$ possible global states in the worst case. \section* {\bf Garg and Waldecker 1992} V.K. Garg and B. Waldecker, Detection of Unstable Predicates in Distributed Programs. In {\it Proceedings of the 12th Conference on the Foundations of Software Technology \& Theoretical Computer Science}, New Delhi, India, Springer-Verlag, 253-264, 1992. \\ \\ This paper discusses detection of strong global predicates in a distributed system, where a strong predicate is defined as one which is definitely true in all possible executions. The authors present algorithms to detect strong linked predicates (a chain of predicates linked by a causal relationship) as well as strong conjunctive predicates (predicates formed by conjunction of local predicates). \section* {\bf Venkatesan and Dathan 1992} S. Venkatesan and B. Dathan. Testing and debugging distributed programs using global predicates. In {\it Thirtieth Annual Allerton Conference on Communication, Control and Computing}, Allerton, Illinois, 137-146, October 1992. \\ \\ This paper discusses completely distributed algorithms for off-line evaluation of conjunctive global predicates. The algorithm proposed in this paper has the same time complexity as the on-line algorithm proposed by Garg and Waldecker. The algorithm deals with predicates which are possibly true as well as those which are definitely true in the execution. \section* {\bf Hurfin, Plouzeau and Raynal 1993} M. Hurfin, N. Plouzeau and M. Raynal. Detecting atomic sequences of predicates in distributed computations. In {\it Proceedings of the ACM/ONR Workshop on Parallel and Distributed Debugging}, San Diego, CA, 32-42, Dec 1993. \\ \\ This paper discusses detection of a particular class of behavioral patterns in a distributed system. The authors have generalized the {\it linked predicate} introduced by Miller and Choi to a more general {\it atomic sequence of predicates} in which some events can be forbidden between each pair of consecutive relevant events. The algorithm proposed uses a message piggy-backing technique to ensure consistency of the detection. \section* {\bf Tomlinson and Garg 1993} A.I. Tomlinson and V.K. Garg. Detecting Relational Global Predicates in Distributed Systems. In {\it Proceedings of ACM/ONR Workshop on Parallel and Distributed Debugging}, San Diego, California, 21-31, May 1993. \\ \\ In this paper the authors discuss how to efficiently monitor a program to determine if there exists a global state in which the sum $X_1 + X_2 + \ldots + X_N$ exceeds some constant $K$, where e$X_i$ is defined in process $i$. Thus this paper extends the class of global functions which can be efficiently detected in a distributed program. \section* {\bf Babao\u{g}lu and Marzullo 1993} \"{O}. Babao\u{g}lu and K. Marzullo. Consistent global states of distributed systems: Fundamental concepts and mechanisms. In Sape Mullender, editor, {\it Distributed Systems}, chapter 5, 97-145. Addison Wesley, $2^{nd}$ ed., 1993. \\ \\ This paper is a survey of the concepts and mechanisms useful in understanding the problem of ``Global Predicate Evaluation''. The authors discuss distributed deadlock detection and distributed debugging as examples where the above concepts can be applied. \section* {\bf Garg and Waldecker 1994} V.K. Garg and B. Waldecker. Detection of Weak Unstable Predicates in Distributed Programs. {\it IEEE Transactions on Parallel and Distributed Systems}, Vol 5, No. 3, 299-307, March 1994. \\ \\ This paper discusses detection of weak global predicates formed by conjunction of local predicates. The author defines a weak predicate to be one which is possibly true in the system. The algorithm proposed exploits the structure of the predicate and has message complexity bounded by the number of messages in the system. \section* {\bf Tomlinson and Garg 1994} A. I. Tomlinson and V. K. Garg. Maintenance of Global Assertions in Distributed Systems. In {\it Proceedings of the International Conference on Computer Science and Education}, Bangalore, India, Tata McGraw-Hill Publishing Company Limited, 257-272, June 1994. \\ \\ This paper develops a method for maintaining global assertions in a distributed system. The global assertion has the form $(X_1^1X_2^1 \ldots X_{N_1}^1) + \ldots + (X_1^MX_2^M \ldots X_{N_M}^M) \geq K$, where $X_i^j$ is a variable which is local to one process and $K$ is a constant. This form is more general than the summation form considered earlier by the same authors, and solves many classical synchronization problems including mutual-exclusion. \section* {\bf Jard, J\'{e}ron, Jourdan and Rampon 1994} C. Jard, T J\'{e}ron, G.V. Jourdan and J.X. Rampon. A General Approach to Trace-Checking in Distributed Computing Systems. In {\it Proceedings of the $14^{th}$ International Conference on Distributed Computing Systems}, Poznan, Poland, 396-403, June 1994. \\ \\ This paper suggests that a relevant model for on-line detection of properties is the partial order of message causality and the associated state graph. The authors discuss two different codings of the causal poset, vector clocks and direct dependency clocks, and give algorithms for on-line construction of the covering digraphs. \section* {\bf Schwartz and Mattern 1994} R. Schwartz and F. Mattern. Detecting causal relationships in distributed computations: In search of the holy grail. {\it Distributed Computing}, vol 7, No. 3, 149-174, 1994 \\ \\ This paper surveys the work done on the detection of causal relationships in distributed computing. The relative merits and limitations of the different approaches are discussed, and their general feasibility is analyzed. The paper also discusses some fundamental problems in the particular research area including lack of a well established formalism leading to substantially different system models in the literature. It is a very comprehensive survey paper and a very valuable source of information for understanding this topic. \section* {\bf Fromentin, Raynal, Garg and Tomlinson 1994} E. Fromentin, M. Raynal, V.K. Garg and A.I. Tomlinson. On The Fly Testing of Regular Patterns in distributed computations. In {\it Proceedings of the $23^{rd}$ International Conference on Parallel Processing}, St. Charles, IL, 73-76, August 1994. \\ \\ This paper discusses the detection of regular patterns in a distributed system. The author defines regular patterns as causal sequences of relevant events defined by a finite state automaton and is therefore more generalized than {\it linked predicates} or {\it atomic sequences}. The detection algorithm is on-line and does not involve the construction of lattice. \section*{Garg, Chase, Mitchell and Kilgore 1995} {\bf } V. K. Garg, C. Chase, J. R. Mitchell and R. Kilgore. Detecting conjunctive Channel Predicates in a Distributed Programming Environment. In {\it $28^{th}$ Hawaii International Conference on System Sciences}, 232-241, January 1995.\\ \\ This paper discusses detection of global predicates in a distributed program which might also include the state of channels. The authors have introduced the notion of monotonicity for channel predicates (the predicate is guaranteed to be false in one direction) which allows for efficient detection of the predicates; the message complexity is bounded by the number of messages used by the program. \section*{Babao\u{g}lu, Fromentin and Raynal 1995} {\bf } \"{O}. Babao\u{g}lu, E. Fromentin and M. Raynal. A Unified Framework for the Specification and Run-time Detection of Dynamic Properties in Distributed Computations. Research Report 967, IRISA, Campus de Beaulieu 35042 Rennes Cedex, France, February 1995. \\ \\ This report attempts to unify a large body of work on distributed debugging and property detection by formulating it as a language recognition problem. The authors presents a general framework to express a large class of properties for distributed computations as languages over alphabets of predicates. Some examples of properties that can be expressed as regular grammar through finite automata have been included. \section*{J\'{e}gou, Medina and Nourine 1995} {\bf } R. J\'{e}gou, R. Medina and L. Nourine. Linear space algorithm for on-line detection of global predicates. In {\it Proceedings of the International Workshop on Structures in Concurrency Theory (STRICT '95)}, Berlin, Germany, 175-189, 1995. \\ \\ This paper proposes an algorithm for on-line detection of an arbitrary global predicate possibly true in a distributed system. This is the first on-line algorithm which uses space linear in the total number of global states in the causality order. The algorithm presented is based on a particular spanning tree of the ideal lattice. \section*{Stoller and Schneider 1995} {\bf } S.D. Stoller and F.B. Schneider. Faster Possibility Detection by Combining Two Approaches. In {\it Distributed algorithms : 9th international workshop, WDAG '95}, Le-Mont-Saint-Michel, France, 318-332, September 1995. \\ \\ This paper presents a new algorithm to detect if an arbitrary global predicate is possibly true in a distributed system. The algorithm is a generalization of the one proposed by Garg and Waldecker, which only works for boolean combinations of local predicates, and is a significant improvement over the existing algorithms which construct the entire lattice to detect the predicate. \section*{Hurfin, Mizuno, Raynal and Singhal 1995} {\bf } M. Hurfin, M. Mizuno, M. Raynal and M. Singhal. Efficient Distributed Detection of Conjunction of Local Predicates. Research Report 967, IRISA, Campus de Beaulieu 35042 Rennes Cedex, France, November 1995. \\ \\ This paper presents efficient distributed algorithms to detect conjunctive form of global predicates in a distributed system. In the proposed algorithm the worst case volume of control information is identical to that of the distributed algorithm proposed by Garg and Chase, however all or most of the control information is piggy-backed on computational messages. \end{document}