Module timely::progress::reachability

Manages pointstamp reachability within a timely dataflow graph.

Timely dataflow is concerned with understanding and communicating the potential for capabilities to reach nodes in a directed graph, by following paths through the graph (along edges and through nodes). This module contains one abstraction for managing this information.

Examples

use timely::progress::{Location, Port};
use timely::progress::frontier::Antichain;
use timely::progress::{Source, Target};
use timely::progress::reachability::{Builder, Tracker};

// allocate a new empty topology builder.
let mut builder = Builder::<usize>::new();

// Each node with one input connected to one output.
builder.add_node(0, 1, 1, vec![vec![Antichain::from_elem(0)]]);
builder.add_node(1, 1, 1, vec![vec![Antichain::from_elem(0)]]);
builder.add_node(2, 1, 1, vec![vec![Antichain::from_elem(1)]]);

// Connect nodes in sequence, looping around to the first from the last.
builder.add_edge(Source::new(0, 0), Target::new(1, 0));
builder.add_edge(Source::new(1, 0), Target::new(2, 0));
builder.add_edge(Source::new(2, 0), Target::new(0, 0));

// Construct a reachability tracker.
let (mut tracker, _) = builder.build(None);

// Introduce a pointstamp at the output of the first node.
tracker.update_source(Source::new(0, 0), 17, 1);

// Propagate changes; until this call updates are simply buffered.
tracker.propagate_all();

let mut results =
tracker
    .pushed()
    .drain()
    .filter(|((location, time), delta)| location.is_target())
    .collect::<Vec<_>>();

results.sort();

println!("{:?}", results);

assert_eq!(results.len(), 3);
assert_eq!(results[0], ((Location::new_target(0, 0), 18), 1));
assert_eq!(results[1], ((Location::new_target(1, 0), 17), 1));
assert_eq!(results[2], ((Location::new_target(2, 0), 17), 1));

// Introduce a pointstamp at the output of the first node.
tracker.update_source(Source::new(0, 0), 17, -1);

// Propagate changes; until this call updates are simply buffered.
tracker.propagate_all();

let mut results =
tracker
    .pushed()
    .drain()
    .filter(|((location, time), delta)| location.is_target())
    .collect::<Vec<_>>();

results.sort();

assert_eq!(results.len(), 3);
assert_eq!(results[0], ((Location::new_target(0, 0), 18), -1));
assert_eq!(results[1], ((Location::new_target(1, 0), 17), -1));
assert_eq!(results[2], ((Location::new_target(2, 0), 17), -1));

Modules

• logging
  Logging types for reachability tracking events.

Structs

• Builder
  A topology builder, which can summarize reachability along paths.
• PerOperator
  Target and source information for each operator.
• PortInformation
  Per-port progress-tracking information.
• Tracker
  An interactive tracker of propagated reachability information.