Past, Future and Cuts in Dataflow: Review
Answer these questions to review the webpage on past, future and
cuts in dataflow.
-
What is the concept of time in dataflow? What do before and after
mean in a dataflow graph?
-
What is a cut in a dataflow graph?
-
What is the relationship between a cut in a dataflow graph and a
cut in a flow network?
-
What is the state of a cut?
-
Draw a dataflow graph. Identify two or more cuts in the graph.
-
For the cuts in the previous example, give examples of dataflows
consisting only of
past events, and only of
future events.
-
For the cuts in the previous example, give examples of
computations in which
past events precede
future events.
-
Give an example of a partition of the set of vertices of a
dataflow graph into subsets
past and
future where a message from future is
received in past.
Explain why this partition is not a cut.
-
A property of a cut is that for each channel \(c\), the number of
messages sent on the channel in
past is at least the
number of messages received on the channel.
Consider a partition (past, future) of the set of vertices,
specified by a vector \(n\) where past consists of
the first \(n[k]\) events of agent \(k\).
Is this partition necessarily a cut if the total number of
messages sent in past is at least the total number of
messages received in past?
Next
The properties of cuts in dataflow, and the concepts of before - after,
past - future are central for
algorithms by
which agents record the
states of distributed systems discussed in the next chapter.
K. Mani Chandy,
Emeritus Simon Ramo Professor,
California Institute of Technology