Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
The Expressive Power and Complexity of Dynamic Process Graphs.
Technical report SIIM-TR-A-00-07,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
2000.
Show postscript | Show abstract
A model for parallel and distributed programs, the dynamic process graph,
is investigated under graph-theoretic and complexity aspects. Such graphs
are capable of representing all possible executions of a parallel or
distributed program in a very compact way. The size of this representation
is small -- in many cases only logarithmic with respect to the size of any
execution of the program. An important feature of this model is that
the encoded executions are directed acyclic graphs with a regular structure,
which is typical of parallel programs, and that it embeds constructors for
parallel programs, synchronization mechanisms as well as conditional branches.
In a previous paper we have analysed the expressive power of the general
model and various restrictions. Furthermore, from an algorithmic point
of view it is important to decide whether a given dynamic process graph can
be executed correctly and to estimate the minimal deadline given enough
parallelism. Our model takes into account communication delays between
processors when exchanging data.
In this paper we study a variant with output restriction. It is appropriate
in many situations, but its expressive power has not been known exactly.
First, we investigate structural properties of the executions of such dynamic
process graphs G. A natural graph-theoretic conjecture that executions must
always split into components isomorphic to subgraphs of G turns out to be
wrong. We are able to establish a weaker property. This implies a quadratic
bound on the maximal deadline in contrast to the general case, where
the execution time may be exponential. However, we show that the problem
to determine the minimal deadline is still intractable, namely this problem
is NEXPTIME-complete as is the general case. The lower bound is obtained by
showing that this kind of dynamic process graphs can represent certain
Boolean formulas in a highly succinct way.
This is an extended abstract to be presented at 26th International Workshop
on Graph-Theoretic Concepts in Computer Science, Konstanz, Germany, 2000.