Hierarchical Event-Based Behavioral Abstraction in Interactive Distributed Debugging: A Theoretical Approach

A distributed computation can be modelled by a partially ordered set of primitive events. Hierarchical event-based behavioral abstraction can be used to reduce the apparent complexity of a computation. Events are grouped together into abstract events, constructing a hierarchy of abstract descriptions of program behavior. Four aspects are studied: a computational model describing primitive observed behavior, a formalism to specify expected behavior, abstract descriptions of the observed behavior, and algorithms to verify primitive or abstract observed behavior against specified behavior. This research is the first integrated study of all four aspects.

Primitive observed behavior is described in terms of events and their causal relationships. Vector time is shown to be an efficient integer representation of the causality structure.The theory of pomset languages is proposed as a simple, powerful formalism to specify behavior in terms of activity and causality. Based on this theory, the notion of behavioral patterns is introduced. A condition is given that a set of events in the observed behavior must satisfy to match a behavioral pattern. Such a set of events forms an abstract event. Concurrent regular expressions, which extend regular expressions to true concurrency, provide a basis for a concise specification language for behavioral patterns. The analogy with string language theory suggests ways for automatic verification of observed against specified behavior.

Causality is defined for abstract events and its representation in vector time is investigated. It is shown that vector time is not sufficient. Reversed vector time is introduced to overcome this problem. Several tests are derived in terms of vector time and reversed vector time to determine causal relationships among abstract events.

For the purpose of automatic verification of observed against specified behavior, so-called pomset grammars are defined. Based on this type of grammars, the PLR-parsing formalism is introduced to recognize pomset languages.

Although considerable progress is made in each of these four aspects, the integration of the computational model and the pomset model needs further study, as does the application of PLR parsing in hierarchical behavioral abstraction.

The full version is not available because the thesis is superseded by the following publications:
  1. T. Basten, T. Kunz, J.P. Black, M.H. Coffin, and D.J. Taylor. Vector Time and Causality among Abstract Events in Distributed Computations. Distributed Computing, 11(1):21-39, December 1997. (abstract / postscript / pdf)

  2. T. Basten. Parsing Partially Ordered Multisets. International Journal of Foundations of Computer Science, 8(4):379-407, December 1997. (abstract / postscript / pdf)

  3. T. Basten. Event Abstraction in Modeling Distributed Computations. In K. Ecker and M. Krämer, editors, Workshop on Parallel Processing, Proceedings, pages 46-65. Lessach, Austria, September 1993. Informatik-Bericht 94/1, Technische Universität Clausthal, Clausthal-Zellerfeld, Germany, 1994. (abstract / postscript / pdf )

Back to the list of publications.