Dataflow: FAQ
What are the edges incident on a vertex in
a dataflow graph? Does each vertex have two input edges and two
output edges?
A vertex, other than a vertex representing a fictitious
initialization step or a final step, has
-
one input agent edge which is labeled with the state of the agent
before the event, and
-
one input message edge which is labeled with the pair
(m,
w) where m is the message received in the event
and m is the sender of the message, and
-
If the step sends messages to k agents then the step has k
output message edges. The label of the output message edge to an
agent x is the sequence of messages sent in the step to agent x.
An initialization vertex has no input edges; it only has output
edges.
The output edges of an initialization vertex are exactly the same as
the output edges of the vertices that represent real (as opposed to
fictional) steps.
A final vertex has no output edges; it only has input edges.
The input edges of a final vertex are exactly the same as
the input edges of the vertices that represent real (as opposed to
fictional) steps.
Exactly how are initial states of channels
represented? If there are two messages m1, m2 in a channel from u to
v and the messages are received by v in steps 1 and 2 then how is
this represented in a dataflow graph?
The initial states of channels from an agent u are represented by
message edges from the vertex representing the fictitious
initialization step of agent u.
In the example, there are two message edges from the initialization
vertex of u. The first message edge is to the
vertex representing step 1 of v, and this edge is labeled m1.
The second message is to the vertex representing step 1 of v.
How many dataflow graphs are associated
with a computation? How many computations are associated with a
dataflow graph?
A computation has exactly one dataflow graph that shows the flow of
data in the computation.
All topological sorts of dataflow graphs are computations.
The number of computations that a dataflow graph represents is the
number of topological sorts of the dataflow graph.
What is the number of topological sorts of a dataflow graph? That
depends on the graph.
You can construct a graph with 1 topological sort and a graph with
n! topological sorts where n is the number of vertices.
Next
The next pages describes
Cuts in Dataflow Graphs
which are used in developing detection algorithms such as termination
detection and deadlock detection.
Examples
Frequenty Asked Questions
Review
K. Mani Chandy,
Emeritus Simon Ramo Professor,
California Institute of Technology