Distributed Algorithms Contents Index

Consistent Cuts of Dataflow Graphs

This page introduces the concept of a consistent cut of a dataflow graph. This concept is the basis of global snapshot algorithms and algorithms that detect deadlock and termination

Definition of a Cut of a Computation

A computation is a sequence of states where there exists a transition from each state in the sequence to the next. A computation can be specified as a sequence of steps, including initialization and finalization steps, as described in the page on data flow. A cut of a computation is a partition of the steps of the computation into subsets past and future.

A consistent cut of a computation is a partition of the steps of the computation into subsets past and future in which, in the dataflow graph of the computation,
all paths to steps in past are from steps in past.

Equivalent definitions of a consistent cut are:

  1. There are no edges in the dataflow graph from future steps to past steps.
  2. All edges in the dataflow graph to past steps are from past steps.
  3. All edges in the dataflow graph from future steps are to future steps.

A cut of a dataflow graph is an instance of a cut of a flow network.

Example of a Consistent Cut

The top diagram of figure 1 shows a consistent cut in which vertices in past are colored red and vertices in future are green. The curved black line is the boundary separating past from future.

Fig1
Fig.1: Example - A Consistent Cut of a Dataflow Graph
Pictorial Example of a Consistent Cut

Pictorially, the state S* at a consistent cut (past, future) is given by the labels of edges that cross the boundary separating past from future. In the upper diagram of figure 1, these are are the edges that cross the curved black line.

In the lower diagram of figure 1, the state S* at the cut is shown as labels to final vertices (labeled N) of past. S* is also shown as labels from initial vertices ( labeled 0) of future.

A Point at an Agent's Computation

A point in the computation of an agent in a dataflow graph is an edge between steps at the agent.

The figure below shows a dataflow graph with agents \(X, Y, Z\) and a computation with steps [0_x, 0_y, 0_z, 1, 2, .. 13] where 0_x, 0_y, 0_z represent the initial states of agents \(X, Y, Z\) and their outgoing channels, respectively. The final states are not shown. In the dataflow graph, the computation of agent \(X\) is [0_x, 3, 5, 8, 11, 12]; the computation of agent \(Y\) is [0_y, 2, 6, 7, 10, 13]; and the computation of agent \(Z\) is [0_z, 1, 4, 9].

The figure shows points at agents as yellow circles. The figure shows a point in the computation of agent \(X\) after step 5 and before step 8 -- this point is the edge (5, 8). Points in the computations of agents \(Y\) and \(Z\) are the edges (2, 6) and (1, 4), respectively.

Fig1
Fig.2: Example - Points at Agent Computations
A set of points, with a point at each agent, specifies a cut (past, future). For a point \((e, e')\) at an agent \(x\), the set of events at \(x\) in past consists of event \(e\) and events that appear before \(e\) in \(x\)'s computation. The set of events at \(x\) in future consists of event \(e'\) and events that appear after \(e'\) in \(x\)'s computation.
For example, for the point (5, 8) the steps at agent \(x\) in past are 0_x, 3, 5, and the steps at agent \(x\) in future are 8, 11, 12.

In the figure past is the set of steps {0_x, 0_y, 0_z, 1, 2, 3, 5} and future consists of the remaining steps.

Fig2
Fig.3: Example - Consistent Cut through Points at Agent Computations

Given a cut specified by points at each agent, by construction, every agent edge to a step in past is from a step in past. So:

A cut specified by points at each agent is consistent exactly when:
every message received in past is sent in past.

The figure below shows an inconsistent cut. The cut is specified by points (0, 3), (6, 7) and (4, 9) at agents \(X, Y, Z\) respectively. past consists of steps 1, 2, 4, 6, and future consists of the remaining steps. The cut is inconsistent because a message sent in a step in future is received in a step in past. For example, step 3 is in future and step 4 is in past.

Fig3
Fig.4: Example - Inconsistent Cut through Points at Agent Computations

Numbers of Messages Sent and Received

Consider a cut (past, future) specified by a point \((e_{u}, e'_{u})\) for each agent \(u\) in a dataflow graph. For a channel \(c\) from an agent \(u\), let \(c_{sent}\) be the number of messages sent on the channel by \(u\) in the dataflow graph before the point \((e_{u}, e'_{u})\), i.e. before step \(e_{u}\). Likewise, for a channel \(c\) to an agent \(v\), let \(c_{rcvd}\) be the number of messages received on the channel by \(v\) in the dataflow graph before the point \((e_{v}, e'_{v})\), i.e. before step \(e_{v}\).
The cut is consistent exactly when:
For all channels \(c\): \(c_{sent} \geq c_{rcvd}\).
This result follows directly from the previous one.
Next
The next page describes global snapshot algorithms by which agents record the states of distributed systems.

K. Mani Chandy, Emeritus Simon Ramo Professor, California Institute of Technology