Cyclic Floes — Internal Developer Reference

This document is an internal developer reference for the cyclic-floe subsystem. It covers how cycle detection, ranking, and execution work under the hood, and gives a detailed account of how CubeGroup objects interact with cycles, including all current limitations and the validation logic that enforces them.

For a user-facing introduction and a working TTL-based example, see cyclic-workfloes.

Overview

A cyclic floe is a WorkFloe whose cube connection graph contains at least one directed cycle — that is, a path from cube X back to itself through one or more other cubes.

┌──┐  ┌──┐  ┌──┐  ┌──┐  ┌──┐
│ A├─►│ B├─►│ C├─►│ D├─►│ E│
└──┘  └──┘▲ └──┘  └─┬┘  └──┘
          └─────────┘

Cycles are useful for iterative algorithms (optimization, simulation, multi-pass processing) but carry inherent risks of deadlock and livelock.

The WorkFloe ordering and sorting framework detects and characterizes cycles automatically at floe-sort time and tags every cube with a CycleDetails object describing its role in the cycle. The runtime then uses this metadata to drive termination detection without relying on centralized state in the controller or any cube.

Cycle Detection and Ranking

CycleDetails

Every cube has a CycleDetails field (floe/api/cubes.py) with the following slots:

Field

Description

in_cycle

True if this cube is a member of a cycle.

cycle_head

Reference to the lowest-ranked cube in the cycle (the entry point used by termination detection to initiate_probe()).

size

Number of logical nodes in the cycle. For floes containing CubeGroup objects, groups count as a single node regardless of how many cubes they contain.

next_cube

The next cube in cycle order. Termination detection follows the next_cube chain to walk the full cycle.

Cubes that are not in a cycle have in_cycle=False and all other fields left at their defaults (None / 0).

Termination Detection

Non-cyclic cube termination

A non-cyclic cube terminates when three conditions are simultaneously true:

  1. It has received EOF from every upstream connection.

  2. It has finished processing.

  3. It has emitted all buffered output.

Each cube determines this entirely from its own local state.

Cyclic cube termination

Cyclic cubes cannot use the same logic. Because a cube inside a cycle can emit data that loops back and becomes new input for itself or its neighbors, there is no simple chain of exhausted upstream inputs to wait for. Instead, termination is assessed at the level of the cycle as a whole when:

  1. Every non-cyclic input to the cycle is exhausted.

  2. No cube in the cycle is actively processing.

  3. No cube holds buffered output waiting to be emitted.

The token-passing algorithm (floe/runtime/runner.py, floe/runtime/transport/client.py, pegasus/scheduler/brokering.go)

Termination is detected using a token probe that circulates around the cycle via the next_cube chain. The approach is based on the token-ring termination detection algorithm described in:

E.W. Dijkstra, W.H.J. Feijen, and A.J.M. van Gasteren, “Derivation of a Termination Detection Algorithm for Distributed Computation”, Information Processing Letters, 16(5):217–219, 1983. (EWD840 manuscript)

  1. Initiation — When the cycle head (cycle_details.cycle_head) detects that its local idle conditions are met — all non-cyclic input buffers have received EOF, no cyclic output is buffered, and no writes are pending — it sends a white token to cycle_details.next_cube (initiate_probe()).

  2. Propagation — Each subsequent cube periodically checks its own idle conditions and forwards the token onward along next_cube. If the cube has been active since the probe started, it marks itself COLOR_BLACK and sends a black token instead (propagate_token()).

  3. Termination decision — When the white token returns to the cycle head and the head’s own color is also white, the entire cycle was idle throughout the full circuit. All cubes in the cycle terminate (service_receive_token()). If the token returns black, the probe restarts on the next idle opportunity.

Note

A CubeGroup whose cubes form the entire cycle (no non-group cubes in the cycle) does not use the token probe. It terminates as soon as all of its input buffers have received EOFs, matching normal non-cyclic termination behavior. (Source: runner.py::detect_termination())

DefaultFloeSorter — the Strongly Connected Component (SCC) pipeline

Cycle detection lives in DefaultFloeSorter (floe/api/ordering.py). Calling sort() on a floe runs the following pipeline:

Before SCC detection, a set of structural checks run on the floe (floe/api/floes.py):

  • check_unadded_cubes() — every cube referenced in a connection must have been added to the floe via add_cubes() or add_group().

  • check_no_cube_is_connected_to_itself() — self-loops (a cube connected directly to itself) are forbidden.

  • check_cube_group_membership() — a cube may belong to at most one group.

  • check_parallel_groups() — parallel group membership rules are satisfied.

  1. Strongly Connected Component (SCC) detection (populate_and_rank_components → depth_first_scc_search)

    A path-based SCC algorithm is applied to the cube connection graph. Each SCC with more than one cube is a cycle; single-cube SCCs are acyclic nodes. Every SCC is represented by a Component object and assigned a preliminary rank.

    Reference: Path-based SCC, Princeton COS 423

  2. Topological sort of the condensation graph (populate_and_rank_components continued)

    Once SCCs are found, they are treated as single nodes in a new acyclic directed graph — the condensation. A topological sort of that graph gives each SCC a rank such that every SCC always has a lower rank than the SCCs it feeds into.

    Reference: Topological Sort, Wikipedia / SCCs form an acyclic diGraph, Stanford

  3. Per-component cube ranking (assign_cube_ranks → Component.assign_cube_ranks)

    • Acyclic component (single cube): the cube’s rank equals the component rank.

    • Cyclic component: a depth-first traversal of the component (_rank_cycle) produces an ordered list of cubes. Each cube is assigned component_rank + i, and CycleDetails is populated with cycle_head, size, and next_cube.

After step 3, every cube has a rank and every cyclic cube has a populated CycleDetails. Steps 4–8 below normalize CycleDetails for CubeGroup objects.

CubeGroups Within Cycles

A CubeGroup groups cubes together for execution purposes. When any cube in a group participates in a cycle, the framework collapses the entire group into a single logical node within that cycle. Five normalization steps (steps 4–8 of sort()) perform this collapsing.

Group representative

The representative of a cyclic group is its lowest-ranked cyclic cube, returned by CubeGroup.get_lowest_rank_cyclic_cube(), otherwise known as the group’s head cube. All cycle-graph traversals use the representative when they encounter the group.

Normalization pipeline (steps 4–8 of sort())

These steps run after initial SCC ranking and operate on CycleDetails pointers in place.

Step 4 — ``configure_cycle_details_connections()``

Walks every cyclic cube’s next_cube chain. If next_cube points to a non-representative cube inside a group, the pointer is advanced along the chain until it lands on a cube that is either outside a group or is a group representative.

Effect: next_cube for cyclic cubes in a group always points outside the group or to its own group head (if cycle only contains that group).

Step 5 — ``configure_group_aware_cycle_heads()``

If the detected cycle_head is a non-head group cube (i.e., it was ranked inside the group but is not the group’s lowest-ranked cube), all cubes in the cycle have their cycle_head pointer reset to the group’s actual head cube (CubeGroup.get_head_cube()).

Effect: cycle_head always refers to a group head, never a buried member.

Step 6 — ``configure_group_aware_cycle_size()``

Recounts the cycle size so that each group contributes 1 to the size, regardless of how many cubes it contains. The adjustment is:

new_size = old_size - (num_cyclic_cubes_in_group) + 1

Effect: CycleDetails.size reflects logical node count, not raw cube count.

Step 7 — ``point_cyclic_group_entries_to_head_cube()`` If the cycle enters a group at a non-head cube, the preceding cube’s next_cube is updated to point to the group’s head cube instead.

Effect: Adjusts the next_cube for any cyclic cube that points to a non-head cube in a group, so that it points to the group’s head cube instead.

Step 8 — ``set_uniform_cycle_details_for_groups()``

All cubes in a cyclic group are given the same CycleDetails as the group’s representative.

Effect: Uniform cycle metadata across the whole group.

Placement rules

  • A CubeGroup may be placed entirely inside a cycle (all cubes in the group are cyclic nodes) or entirely outside it (no cubes in the group are cyclic).

  • A group that straddles the cycle boundary — where some cubes are cyclic and others are not — is a bad pattern and should not be used.

CubeGroup Limitations in Cycles

Not every invalid pattern is caught at floe-sort time. The subsections below distinguish between constraints that are actively enforced (raising a ValidationError) and patterns that are known to be broken but are not currently validated against.

Enforced constraints

Limitation 1 — A CubeGroup may only belong to one cycle

A single CubeGroup cannot span two different cycles.

Enforced by: WorkFloe.check_group_with_multiple_cycles() (floe/api/floes.py)

Error message:

CubeGroup '<name>' has multiple different cycles: {...}'

Invalid pattern (floe/tests/invalid/group_multiple_cycles.py):

┌──┐   ┌──┐   ┌──┐  ┌──┐    ┌──┐  ┌──┐    ┌──┐
│ A│   │ B│   │ C│  │ D│    │ E│  │ F│    │ G│
│  ├──►│  ├──►│  ├─►│G1├─E─►│G1├─►│  ├─E─►│  │
└──┘   └──┘   └──┘  └┬─┘    └──┘  └┬─┘    └──┘
               ▲    │        ▲    │
               └──C─┘        └──C─┘
# Group G1 contains both D and E, which are heads of two separate cycles

Limitation 2 — Initializer ports cannot be used inside a cycle

Initializer ports fire exactly once (when the first data item arrives), so they cannot participate in a repeating cycle. Any connection in the cyclic path that targets an initializer port is rejected.

Enforced by: WorkFloe.check_cyclic_initializers() → WorkFloe.check_cycle() (floe/api/floes.py)

Error message:

Initializer port '<port>' on cube '<cube>' cannot be used in a cycle

Also enforced: cubes.rst documents that initializer ports cannot be used within a cycle or a cube group.

Invalid patterns:

  • floe/tests/invalid/initializer_cycle.py — initializer port in the cycle body

  • floe/tests/invalid/initializer_cycle_head.py — initializer port on the cycle head cube

Limitation 3 — Deadlock re-entry detection is bypassed for cyclic groups

The cube group re-entry deadlock detector (which flags groups that can be entered from multiple upstream paths via check_cube_group_reentry_deadlock()) is explicitly skipped for groups that are part of a cycle. This is intentional — a cyclic group is, by definition, re-entered on every loop iteration, so the detector would always fire a false positive.

Introduced: v6.7.0 (OCOMP-1974)

Known bad patterns (not currently validated)

The following topologies are invalid but are not caught by a ``ValidationError`` at sort time. They may succeed but can cause incorrect results, deadlock, or livelock.

Partial group traversal (floe/tests/invalid/bad_group_cycle.py)

A cycle exits from a cube that is not the last cube in the group, leaving other group members only reachable via a non-cyclic (exit) path:

┌──┐    ┌──┐     ┌──┐
│ 0│    │ 1│     │ 2│
│  ├───►│GA├─┐E─►│GA│
└──┘ ▲  └──┘ │   └──┘
     │       C
     │  ┌──┐ │
     └──┤ 3│◄┘
        │  │
        └──┘
# Group contains [Cube 1, Cube 2]. The cycle exits from Cube 1 (skipping
# Cube 2), which means the group is only partially traversed by the cycle.

Multiple cyclic paths through a group (floe/tests/invalid/bad_group_cycle_multiple_paths.py)

The cycle fans out inside the group and reconverges, creating more than one cyclic path through the group’s members:

                ┌──┐
                │3 │
┌──┐     ┌──┐ ┌►│GA├─┐ ┌──┐     ┌──┐
│1 ├──┬─►│2 ├─┤ └──┘ ├►│5 ┼──┬─►│6 │
│  │  │  │GA│ │ ┌──┐ │ │  │  │  │  │
└──┘  │  └──┘ └►│4 ├─┘ └──┘  │  └──┘
      │         │GA│          │
      │         └──┘          │
      └──────────◄────────────┘
# Group contains [Cube 2, Cube 3, Cube 4]; Cube 2 fans out to both
# Cube 3 and Cube 4, creating two cyclic paths through the group.

Cycle entering/exiting from internal cubes across multiple groups (floe/tests/invalid/bad_multi_group_cycle.py)

A cycle traverses two groups but does not include all cubes in the groups:

┌──┐  ┌──┐   ┌──┐     ┌──┐
│ 0│  │ 1│   │ 2│     │ 3│
│  ├─►│G1├──►│G1├─┐E─►│G1│
└──┘  └──┘ ▲ └──┘ │   └──┘
           │      C
           │      └──────►┌──┐
           │              │ 4│
           │       ┌──────┴──┘
           │       │
     ┌──┐  │ ┌──┐  │ ┌──┐
     │ 7│  │ │ 6│  ▼ │ 5│
     │G2│◄─┴─┤G2│◄───┤G2│
     └──┘    └──┘    └──┘
# The cycle enters Group 1 at Cube 2 (not the head) and exits Group 2
# via multiple cubes.