How SynState Solved the Glitch

What Is a Glitch?

In reactive programming, a glitch is a phenomenon where derived values temporarily enter inconsistent intermediate states during propagation. When a single source value changes, Observables that depend on it may update one at a time rather than all at once. If a downstream Observable depends on multiple upstream values that share a common ancestor, it can observe a state where some inputs have already updated while others have not — producing a value that should never logically exist.

A Simple Example

Consider the following Observable graph:

In SynState code:

import { collectToArray, combine, counter, map, take } from 'synstate';

const counterObservable = counter(1000 /* ms */);
// 0, 1, 2, 3, ...

const multipliedBy10 = counterObservable.pipe(map((count) => count * 10));
// 0, 10, 20, 30, ...

const multipliedBy1000 = counterObservable.pipe(map((count) => count * 1000));
// 0, 1000, 2000, 3000, ...

const sum = combine([multipliedBy10, multipliedBy1000]).pipe(
    map(([a, b]) => a + b),
);
// 0, 1010, 2020, 3030, ...

const resultPromise = collectToArray(sum.pipe(take(5)));

counterObservable.start();

const result = await resultPromise;

assert.deepStrictEqual(result, [0, 1010, 2020, 3030, 4040]);

Both multipliedBy10 and multipliedBy1000 (the two inputs to combine) originate from the same source (counterObservable). Whenever counterObservable emits a new value, both inputs to combine should update together — and sum should always equal counter * 1010.

What Happens in RxJS (Glitch)

In RxJS, combineLatest propagates a new value as soon as any one input changes. When counterObservable emits a new value, the update propagates through the graph in a depth-first manner. Since combineLatest subscribes to its inputs in order, the typical sequence when the counter changes from 0 to 1 is:

counterObservable emits 1
combineLatest’s subscription to multipliedBy10 (first input) fires — multipliedBy10 recalculates to 10, but multipliedBy1000 (second input) is still 0 (the old value)
combineLatest emits [10, 0] → sum emits 10 — a glitch
multipliedBy1000 (which also subscribes to counterObservable) recalculates to 1000
combineLatest sees that multipliedBy1000 changed to 1000
combineLatest emits [10, 1000] → sum emits 1010 — correct

This pattern repeats every time the counter increments:

counter:     0     1           2              3
             │     │           │              │
sum (RxJS):  0     10, 1010    1020, 2020     2030, 3030   ...
                   ↑           ↑              ↑
                   glitch      glitch         glitch

The full output sequence of sum in RxJS is:

0, 10, 1010, 1020, 2020, 2030, 3030, ...

The values 10, 1020, 2030, … are glitches — they represent states where one derived observable has already updated but the other has not yet recalculated. These values should never exist logically (sum should always be a multiple of 1010), yet they are emitted to subscribers, potentially causing incorrect UI rendering, invalid API calls, or subtle bugs.

Note: The order in which glitches appear depends on the order in which counterObservable notifies its subscribers. In the example above, combineLatest subscribes to multipliedBy10 first and then multipliedBy1000, so counterObservable’s subscriber list has the same order and multipliedBy10 is updated first. If multipliedBy1000 had subscribed to counterObservable before multipliedBy10, the glitch values would be 1000, 2010, 3020, … instead. Either way, the glitch occurs because the two derived observables update one at a time rather than atomically.

You can verify this behavior by running the following RxJS sample code:

import {
    combineLatest,
    interval,
    lastValueFrom,
    map,
    take,
    toArray,
} from 'rxjs';

const counterObservable = interval(100);
// 0, 1, 2, 3, ...

const multipliedBy10 = counterObservable.pipe(map((count) => count * 10));
// 0, 10, 20, 30, ...

const multipliedBy1000 = counterObservable.pipe(map((count) => count * 1000));
// 0, 1000, 2000, 3000, ...

const sum = combineLatest([multipliedBy10, multipliedBy1000]).pipe(
    map(([a, b]) => a + b),
);
// 0, 10, 1010, 20, 2020, 30, 3030, ...

const result = await lastValueFrom(sum.pipe(take(7), toArray()));

assert.deepStrictEqual(result, [0, 10, 1010, 1020, 2020, 2030, 3030]);

Timeline

Step	`counterObservable`	`multipliedBy10`	`multipliedBy1000`	`sum` (`multipliedBy10 + multipliedBy1000`)	Consistent?
1	0	0	0	0 ✓	Yes
2	1	10	0	10 ✗	Glitch
3	1	10	1000	1010 ✓	Yes
4	2	20	1000	1020 ✗	Glitch
5	2	20	2000	2020 ✓	Yes
6	3	30	2000	2030 ✗	Glitch
7	3	30	3000	3030 ✓	Yes

Is This Just a Contrived Example?

The counter × 1000 + counter + 10 formula above is clearly artificial, but the underlying pattern — diamond dependencies — is surprisingly common in everyday UI code. Any time two or more pieces of derived state share a common ancestor, you have a diamond.

Real-World Example: Data Table with Filters

The interactive table below is a typical data-browsing UI: a list of records with per-column text filters (debounced) and pagination controls. Try typing in the filter inputs — every keystroke triggers a chain of derived state updates:

The three inputs to TableSliced — ItemsPerPage, TableFiltered, and CurrentPage — form multiple overlapping diamonds. For example, TableFiltered is both a direct input to TableSliced and an indirect ancestor of CurrentPage (via PageLength). Similarly, ItemsPerPage feeds into both PageLength (which influences CurrentPage) and TableSliced directly. Whenever a filter input or ItemsPerPageInput changes, several of TableSliced’s inputs share a common ancestor and must all be resolved before TableSliced can be evaluated consistently.

In a push-based library like RxJS, combineLatest would emit intermediate states where some inputs have already updated while others still hold stale values. Whether this causes a visible bug depends on the application, but the inconsistency is always there — and it scales: with $N$ inputs to combineLatest, a single source update produces $N+1$ emissions instead of 1, leading to the $O(N^2)$ performance cliff demonstrated in the deep chain demo.

How Can We Eliminate Glitches?

The root cause of glitches is that child observables can be evaluated before all of their ancestors have finished updating. If we could guarantee that every observable is updated only after all of its ancestors have been updated, glitches would be impossible.

The Priority Queue Approach

A well-known solution is to assign each observable a level (or depth) — the length of the longest path from a root source to that observable — and use a priority queue to process updates in ascending level order.

This approach is described in detail in, for example, the paper Deprecating the Observer Pattern with Scala.React (Maier & Odersky, 2012). The algorithm works as follows:

When a source observable changes, it does not immediately notify its children. Instead, all invalidated nodes are placed into a priority queue ordered by level.
The propagation loop dequeues the node with the lowest level, validates (evaluates) it, and enqueues its dependent nodes (which are on greater levels) into the queue.
This continues until the queue is empty.

Because the queue always processes lower-level nodes first, by the time a combine (or any multi-parent node) is dequeued, all of its parents are guaranteed to have already been updated in this cycle. The intermediate state — where one parent has updated but another has not — is never observed by any downstream node.

Let’s trace the priority queue approach step by step using the diamond example. Each node has a level based on its position in the graph:

counter             → level 0
multipliedBy10      → level 1
multipliedBy1000    → level 1
sum (combine + map) → level 2

When counter changes from 0 to 1, the propagation proceeds as follows:

Step	Action	Priority Queue (after)
1	`counter` updates to `1`. Its dependents `multipliedBy10` and `multipliedBy1000` are enqueued.	`[multipliedBy10 (L1), multipliedBy1000 (L1)]`
2	Dequeue `multipliedBy10` (level 1). Evaluate: `1 * 10 = 10`. Its dependent `sum` is enqueued.	`[multipliedBy1000 (L1), sum (L2)]`
3	Dequeue `multipliedBy1000` (level 1). Evaluate: `1 * 1000 = 1000`. Its dependent `sum` is already in the queue — skip.	`[sum (L2)]`
4	Dequeue `sum` (level 2). Evaluate: `10 + 1000 = 1010`. Both inputs are up-to-date. No more dependents.	`[]` (empty)

The queue is empty — propagation is complete. sum emits 1010, the correct value. No glitch occurred because sum was only evaluated after both of its parents had been updated.

reactivelib/reactive is a TypeScript library that implements this topologically-ordered propagation, directly inspired by the Scala.React paper.

The Cost of Each Approach

The priority queue approach correctly eliminates glitches, but it introduces overhead on every update. Each time a source emits, every descendant must be enqueued into and dequeued from the priority queue — each operation costing $O(\log n)$ where $n$ is the number of observables in the graph. For a graph with $n$ descendants, the total propagation cost per source emission becomes $O(n \log n)$ .

RxJS’s depth-first propagation avoids this overhead — each node is visited with just a function call. However, RxJS treats the dependency graph as a tree, not a DAG (directed acyclic graph). When a diamond dependency exists, RxJS traverses both branches independently: the shared descendant (e.g., combine) is evaluated once for each branch that reaches it.

The cost depends on the diamond topology:

Wide diamond — a fan-out of $n$ branches merging back into a single combineLatest. Each source emission triggers $n+1$ combineLatest evaluations, each processing $n$ inputs → $O(n^2)$ per source emission.
Cascaded diamonds — a chain of $n$ diamonds in series, where each combineLatest’s output feeds into the next diamond. If each diamond has a fan-out of $D$ (i.e., $D$ branches merging into one combineLatest), each level multiplies the number of emissions by $D$ : level 1 fires $D$ times, level 2 fires $D^2$ times, …, level $n$ fires $D^n$ times → $O(D^n)$ per source emission. For a binary fan-out ( $D = 2$ ), this becomes $O(2^n)$ .

Approach	No diamond (tree)	With diamond (worst case)
RxJS (depth-first)	$O(n)$	$O(D^n)$
Priority queue (Scala.React)	$O(n \log n)$	$O(n \log n)$

( $D$ = fan-out per diamond stage)

For graphs without diamond dependencies, RxJS is faster by a $\log n$ factor. But once diamonds are present, RxJS’s cost grows exponentially in the worst case (cascaded diamonds), while the priority queue approach remains $O(n \log n)$ . Neither achieves the ideal of $O(n)$ glitch-free propagation.

This matters in performance-sensitive scenarios such as mousemove or pointermove events, animation frames, or any high-frequency stream where updates fire dozens or hundreds of times per second. The repeated heap operations of the priority queue approach add up, and RxJS’s redundant evaluations in diamond graphs scale even worse.

SynState solves both problems: it achieves glitch-free propagation in $O(n)$ — the same asymptotic cost as RxJS’s tree traversal, but without glitches and without the exponential worst case ( $D$ = fan-out per diamond). You can observe the slowdown in practice in the deep dependency chain demo, where RxJS’s throughput collapses as the chain depth increases while SynState remains flat.

What Happens in SynState (Glitch-Free, O(n))

SynState’s key insight is that the dependency graph’s topology is static — it is determined when observables are constructed and does not change between updates. This means the propagation order can be computed once when the graph is built, rather than re-derived on every emission.

Pre-sorted propagation order

When an observable is created via .pipe() or a combinator (combine, merge, zip), SynState computes its depth — the length of the longest path from any root source:

Root observables: depth = 0.
Child observables: depth = 1 + max(parent depths).

Each root observable maintains a flat array called propagationOrder — a list of all its descendants, kept in ascending depth order via binary search insertion at construction time. When a source emits, propagation is a simple linear scan through this pre-sorted array:

// Simplified from RootObservableClass
startUpdate(nextValue) {
    const updateToken = issueUpdateToken();
    this.setNext(nextValue, updateToken);

    // propagationOrder is pre-sorted by depth (ascending)
    for (const child of this.propagationOrder) {
        child.tryUpdate(updateToken);
    }
}

This is a key architectural difference from RxJS. In RxJS, each observable is responsible for updating its own value and propagating to its children — propagation is distributed across the graph. In SynState, a manager observable centrally manages the update of all its descendants in a single loop. This centralized control is what makes depth-ordered propagation possible without a priority queue.

SynState’s Observable types are RootObservable, SyncChildObservable, and AsyncChildObservable. Of these, RootObservable and AsyncChildObservable act as managers. A RootObservable is the entry point of a graph, while an AsyncChildObservable is created by time-shifting operators such as debounce — since their emissions are asynchronous and cannot be coordinated by the upstream root, they take over as managers for their own downstream subgraph.

Because the array is sorted by depth, every parent is guaranteed to have been updated before any of its children — the same correctness guarantee as the priority queue approach, but with $O(n)$ propagation cost and zero runtime allocation. The only cost paid is at construction time ( $O(\log n)$ binary search insertion), which is a one-time operation.

Applying this to the diamond example:

depth 0:  counter            ← source emits
depth 1:  multipliedBy10     ← updated first  (depth 1)
depth 1:  multipliedBy1000   ← updated next   (depth 1)
depth 2:  sum (combine)      ← updated last   (depth 2); both inputs are up-to-date

The output of sum in SynState is:

0, 1010, 2020, 3030, 4040, ...

No intermediate states. No glitches. Every value emitted to subscribers is consistent.

Timeline

Step	`counterObservable`	`multipliedBy10`	`multipliedBy1000`	`sum` (`multipliedBy10 + multipliedBy1000`)	Consistent?
1	0	0	0	0 ✓	Yes
2	1	10	1000	1010 ✓	Yes
3	2	20	2000	2020 ✓	Yes
4	3	30	3000	3030 ✓	Yes

Handling skipped updates: the update token

The depth-ordered linear scan eliminates glitches when every node updates. But not every node updates on every cycle — operators like filter and skipIfNoChange can skip an emission. This introduces a subtlety: how does a downstream node know whether its parent was intentionally skipped in the current cycle, or simply hasn’t been reached yet?

Consider the following graph where D applies a filter:

const A = counter(1000);
// 0, 1, 2, 3, 4, ...

const B = A.pipe(map((n) => n * 10));
// 0, 10, 20, 30, 40, ...

const D = A.pipe(filter((n) => n % 2 === 0));
// 0, 2, 4, ...  (odd values are skipped)

const C = combine([B, D]).pipe(map(([b, d]) => b + d));
// sum of B and D: 0, 10, 22, 32, 44, 54, 66, ...

const E = D.pipe(map((n) => n * 10));
// 0, 20, 40, ...

const resultC = collectToArray(C.pipe(take(7)));

const resultE = collectToArray(E.pipe(take(4)));

When A emits an even value (e.g., 2), all nodes update: B becomes 20, D passes 2, C emits 22, and E becomes 20. But when A emits an odd value (e.g., 1), D does not pass the predicate — so D and its descendant E should not update, while B does update to 10 and C should re-evaluate because B has changed. The challenge is that propagationOrder is a linearized list — the original parent–child relationships are flattened away. When the manager iterates this list, each node must be able to determine on its own whether its parents were updated or skipped in this cycle.

SynState solves this by giving every update cycle a unique identity — an update token. The token is a Symbol created at the start of each cycle via issueUpdateToken(), and it flows through the graph as follows:

The manager creates a fresh token and stamps itself via setNext(value, token).
The same token is passed to every descendant’s tryUpdate(token) method during the linear scan.
When a child successfully updates, it calls setNext(newValue, token), stamping itself with the current cycle’s token.
When a child skips (e.g., filter’s predicate returns false), it does not call setNext — so its updateToken remains the token from a previous cycle.

This creates a simple invariant: a node’s updateToken equals the current cycle’s token if and only if it was updated in this cycle. Each node checks this on its parents with a single reference comparison — $O(1)$ — to decide whether to update or skip:

Single-parent operators (e.g., map, scan): Check parent.updateToken === token. If the parent’s token doesn’t match, the parent was skipped — so the child skips too.
Multi-parent operators (e.g., combine): Check whether at least one parent’s token matches. If all parents were skipped, combine skips. If at least one updated, combine re-evaluates using the latest snapshot from every parent (whether updated in this cycle or not).

// Simplified from CombineObservableClass
override tryUpdate(updateToken: UpdateToken): void {
    // Skip only if ALL parents were skipped in this cycle
    if (this.parents.every((o) => o.updateToken !== updateToken)) return;

    const parentValues = this.parents.map((a) => a.getSnapshot());
    // ... emit combined value ...
}

// Simplified from FilterObservableClass
override tryUpdate(updateToken: UpdateToken): void {
    const par = this.parents[0];

    if (par.updateToken !== updateToken) {
        return; // parent was skipped → skip this node too
    }

    const sn = par.getSnapshot();

    if (this.predicate(sn.value)) {
        this.setNext(sn.value, updateToken); // stamp with token → "I updated"
    }
    // If predicate fails: no setNext → updateToken stays stale → descendants know to skip
}

Because each node’s skip-or-update decision is a constant-time token comparison, the overall cost of a single update cycle remains $O(n)$ where $n$ is the number of descendants — and each node pays amortized $O(1)$ per cycle.

Summary

Approach	No diamond (tree)	With diamond (worst case)	Glitch-free?
RxJS (depth-first)	$O(n)$	$O(D^n)$	No
Priority queue (Scala.React)	$O(n \log n)$	$O(n \log n)$	Yes
SynState	$O(n)$	$O(n)$	Yes

SynState achieves glitch-free propagation in $O(n)$ by exploiting two properties of the dependency graph:

Static topology — the graph structure is fixed at construction time, so the propagation order (propagationOrder) can be pre-computed once rather than re-derived on every emission.
Update tokens — a unique token per cycle lets each node determine in $O(1)$ whether its parents participated in the current cycle, enabling correct skip-or-update decisions even though propagationOrder is a flat list with no graph structure.

Cycle detection

SynState’s propagation model assumes the dependency graph is a DAG (directed acyclic graph). To guarantee this at runtime, SynState performs a cycle check at construction time — whenever a new observable is created via .pipe() or a combinator (combine, merge, zip), a depth-first traversal of the ancestor chain verifies that no node appears as its own ancestor. If a cycle is detected, an error is thrown immediately:

Circular dependency detected in observable graph:
a child observable cannot be its own ancestor.

This means that after the initial graph construction succeeds, all subsequent update cycles are guaranteed to operate on a DAG — no infinite loops, no corrupted propagation order.

Other libraries handle cycles differently:

RxJS does not perform cycle detection. In practice, pipe() and combineLatest() follow a forward-only construction pattern — you can only reference Observables that already exist — so cycles rarely arise in normal usage. However, RxJS provides no explicit validation as a safety net, unlike SynState’s construction-time DFS check.
Jotai does not detect cycles. Circular atom definitions (e.g., atomA reads atomB, atomB reads atomA) are silently accepted at definition time. The cycle only manifests when the atom is read, crashing with Maximum call stack size exceeded — a stack overflow rather than a clear diagnostic.

These behaviors are verified in the circular dependency comparison tests.