Propagators -- Brief ☧

Deep version -> | Back to Domains ->

Q: Picture the walls of ancient Jerusalem. Watchmen are stationed all

around -- one facing north, another east, another south. If the northern

watchman spots dust rising from an approaching army, what does he do?

A: He shouts a warning. The other watchmen hear the cry, and now they

know something new: "Threat from the north." They adjust -- maybe the

eastern watchman shifts his focus, the southern one signals the gate

to close. Information rippled outward from one observation.

Q: So a propagator is like one of these watchmen?

A: Exactly. A propagator watches one or more variables. When one

variable's domain changes -- when new information arrives -- the

propagator wakes up and may narrow the domains of the other variables

it watches. It enforces a rule.

Q: Can you walk me through a concrete example?

A: Sure. Suppose three tribal leaders must sit at a council, and the

constraint is "no two leaders can be the same person." Each seat starts

with the same possibilities:

Seat A: {Judah, Dan, Ephraim}   -- could be any of three
Seat B: {Judah, Dan, Ephraim}   -- same possibilities
Seat C: {Judah, Dan, Ephraim}   -- same possibilities

Constraint: "Seat A != Seat B"  (a propagator watches A and B)

Now we assign Seat A = Judah. The propagator that watches the

"A != B" constraint wakes up and fires -- it removes Judah from

Seat B's domain:

Seat A: {Judah}           -- assigned
Seat B: {Dan, Ephraim}    -- Judah removed by propagator
Seat C: {Judah, Dan, Ephraim}  -- unaffected (different constraint)

Q: That's neat. But isn't it slow to check each value one by one?

A: Not when we use bitmasks. In hardware, the propagator is an

AND gate. When Seat A becomes 001 (only Judah), the "not-equal"

propagator ANDs Seat B's domain with 110 (everything except Judah).

One clock cycle. Done.

Propagator Anatomy

With the watchman metaphor in mind, let us name the four key components and

see how they fit together.

Here is the flow in plain language: each cell stores what we currently know

about one variable (its domain of possible values).

A propagator watches two or more cells and enforces a rule between them --

when one cell changes, the propagator wakes up and may narrow the others.

The scheduler manages the queue of propagators that need to fire. It pulls

them off one at a time and runs them. When the queue empties, we have reached

fixpoint -- nothing more can be deduced, and the watchmen fall silent.

Think of the scheduler like a queue: propagators that need to fire get

added, and the scheduler pulls them off one at a time until the queue is

empty. On our FPGA, the M6B scheduler takes this idea further -- it dispatches

work to 8 lanes in parallel, so many propagators fire simultaneously rather

than one at a time. This is the hardware advantage: where a CPU processes

the queue sequentially, the FPGA processes it in parallel.

graph LR
    A[Cell A<br/>Seat domain] -->|watches| P["Propagator<br/>(A != B)"]
    B[Cell B<br/>Seat domain] -->|watches| P
    P -->|narrows| A
    P -->|narrows| B
    style P fill:#f9f,stroke:#333

Propagators ARE Circuits

The Forge-Chirho compiler takes this idea to its limit: a propagator

specification compiles to raw AArch64 machine code with no stack,

no function calls, no interpreter. Each rule becomes a sequence of

loads, compares, and conditional stores -- the exact same operations

that our FPGA implements in hardware:

Propagator concept   → CPU instruction     → FPGA equivalent
event binding        → LDR (load)          → input pin
guard (when)         → FCMP + branch       → comparator gate
propagation (<-)     → STR (store)         → flip-flop write
watch trigger        → TST + branch        → AND gate on status

A complete CRDT merge propagator (2 rules, guards, watches, observer

notifications) compiles to 64 instructions, 256 bytes -- fits in

4 cache lines. Our M6B lane pipeline is the same trace, executed in

silicon rather than on a CPU.

Learn more about propagators, native traces, and the FPGA connection

Related: Fixpoint | Lattices | Edward's Lenses

Soli Deo Gloria