Determinism concerns for lockstep/rollback simulation

[Eragon-Brisingr]

Determinism concerns for lockstep/rollback simulation

flecs version: 4.1.3 (C, single-threaded pipeline)

We're building a deterministic lockstep simulation on flecs: multiple machines must produce bit-identical results given the same initial state + the same inputs. A client also restores a serialized world snapshot and re-simulates forward, and that re-simulation must match what the authoritative peer computed. We've hit two flecs behaviors that make this hard, and I'd like to know the recommended way to handle them (or whether they're considered bugs).

---

Problem 1 — a system that activates mid-frame runs in the same frame, so per-frame results depend on world history

We use a level-of-detail pattern that splits one logical per-entity update into mutually-exclusive systems gated by a tag, all in the same phase:

SysLow : (Position, !FastTag)   // handles entities WITHOUT the tag
SysHigh: (Position,  FastTag)   // handles entities WITH the tag

Both run in EcsOnUpdate (SysLow first), and both do the same kind of per-entity work. The design assumes each entity is handled by exactly one of them per frame.

A separate system in an earlier phase (EcsPreUpdate) adds FastTag to an entity on some frame (like a relevance/interest system re-classifying it). The add is deferred, so it's still pending when the OnUpdate variants run.

Observed: whether the entity is processed once or twice on the transition frame depends only on whether SysHigh was already active (i.e., whether any other entity already had FastTag), because:

• If SysHigh is dormant (its query matches no non-empty table), adding FastTag mid-progress makes it match → the pipeline is rebuilt → the newly-active SysHigh runs in the same progress, after SysLow already processed the just-tagged entity → double-processed.
• If SysHigh was already active, the entity is processed once.

So the same per-frame inputs produce a different result depending on world history. In lockstep this desyncs: a client that restored a snapshot in which SysHigh happened to be dormant computes a different result than a peer where it was active.

Minimal repro (attached repro.c)

Runs the identical scenario twice, differing only in whether a dummy entity keeps SysHigh active:

--- Scenario A: target alone (SysHigh initially DORMANT) ---
frame 3: target->count = 4  (delta this frame = 2  <<< DOUBLE-PROCESSED)
...
--- Scenario B: dummy present (SysHigh initially ACTIVE) ---
frame 3: target->count = 3  (delta this frame = 1)
...
==== RESULT ====
Total count Run A (SysHigh dormant): 7
Total count Run B (SysHigh active) : 6
>>> NON-DETERMINISTIC: identical per-frame inputs, different result (7 vs 6),
>>> solely because of whether SysHigh was already active (world history).

Questions

1. Is a just-activated system running in the same frame (after a sibling that the now-transitioned entity previously matched) intended behavior?
2. For deterministic sims, is there a supported way to make a system's presence in the pipeline schedule independent of whether its query currently matches — i.e., keep it always scheduled so the op structure is history-independent? (We tried EcsQueryMatchEmptyTables, but flecs_pipeline_build still marks a system inactive when its matched tables are EcsEmpty.)
3. Or is there a recommended pattern for LOD/rate-limited split systems that stays deterministic? (Our current fallback is to fold the variants into a single system that reads the "rate" as a component field instead of gating multiple systems by a tag, or to add a per-entity "already updated this frame" guard.)

---

Problem 2 — table iteration order is not stable across machines after deserialization

For determinism, every peer must iterate entities in the same order each frame (order affects any order-sensitive logic, and it affects our per-frame state hashing). After we deserialize a world snapshot on a client, the table order (and therefore the order in which a system's query visits tables/entities) can differ from the authoritative peer, because table creation order depends on the order components/tags were added during load, which isn't guaranteed to match.

Current workaround: we sort tables (impose a deterministic ordering on the tables a query visits) so iteration order is stable across peers. This works but feels like fighting the

framework.

Questions

1. Is there a supported/first-class way to get a deterministic, machine-independent table iteration order for a query (e.g., a stable sort key, order_by on a component, or a serialization mode that reproduces table order)?
2. Does flecs guarantee anything about table order being reproducible after ecs_world deserialization if entities/components are restored in the same order?
3. Any recommended approach for deterministic iteration order in a lockstep/rollback context that avoids a manual per-frame table sort?

---

Thanks! Happy to provide more detail or additional repros. Overall flecs has been great to build on; these are the two spots where determinism needs extra care and we'd like to align with the intended approach.

[Eragon-Brisingr]

• repro.c

/*
 * Minimal repro: pipeline system-activation makes per-frame results depend on world history,
 * which breaks deterministic (lockstep / rollback) simulation.
 *
 * Setup mirrors a common "level-of-detail" pattern where ONE logical per-entity update is split
 * into mutually-exclusive systems gated by a tag:
 *     SysLow : (Position, !FastTag)   // handles entities WITHOUT the tag
 *     SysHigh: (Position,  FastTag)   // handles entities WITH the tag
 * Both run in the same phase (OnUpdate), SysLow before SysHigh, and both do the SAME kind of
 * per-entity work (here: bump entity->count). The design assumes each entity is handled by
 * exactly ONE of them per frame.
 *
 * A third system (Promoter, in the EARLIER EcsPreUpdate phase) adds FastTag to the entity on a
 * chosen frame -- like a relevance/interest system re-classifying an entity. The tag add is
 * deferred, so it is still pending when the OnUpdate variants run.
 *
 * We run the SAME scenario twice, differing ONLY in world history:
 *   Run A: the entity is the ONLY entity        -> SysHigh has no matching table => INACTIVE/dormant.
 *   Run B: a dummy entity already has FastTag    -> SysHigh always has a match    => ACTIVE.
 *
 * Observed: on the promotion frame, Run A double-counts the entity (SysLow AND SysHigh both run it
 * in the same frame, because adding FastTag activates the dormant SysHigh mid-frame and flecs runs
 * the newly-active system in the same progress), while Run B counts it once. Same inputs, different
 * result -- purely because of whether SysHigh was already active. In lockstep, a client that
 * restored a snapshot where SysHigh happened to be dormant computes a different result than the
 * server where it was active -> desync.
 */
#include "flecs.h"
#include <stdio.h>

typedef struct { int count; } Counter;

static ECS_COMPONENT_DECLARE(Counter);
static ecs_entity_t FastTag;
static ecs_entity_t g_target;   /* the entity we watch */
static int g_promote_frame;     /* frame on which Promoter adds FastTag to g_target */
static int g_frame;

/* SysLow: entities WITHOUT FastTag */
static void SysLow(ecs_iter_t *it) {
    Counter *c = ecs_field(it, Counter, 0);
    for (int i = 0; i < it->count; i++) {
        if (it->entities[i] == g_target) c[i].count++;
    }
}
/* SysHigh: entities WITH FastTag */
static void SysHigh(ecs_iter_t *it) {
    Counter *c = ecs_field(it, Counter, 0);
    for (int i = 0; i < it->count; i++) {
        if (it->entities[i] == g_target) c[i].count++;
    }
}
/* Promoter: on the promotion frame, add FastTag to the target (deferred, like a relevance system) */
static void Promoter(ecs_iter_t *it) {
    if (g_frame == g_promote_frame) {
        ecs_add_id(it->world, g_target, FastTag);
    }
}

static int run_scenario(int with_dummy) {
    ecs_world_t *world = ecs_init();
    ECS_COMPONENT_DEFINE(world, Counter);
    FastTag = ecs_new(world);

    /* SysLow / SysHigh in OnUpdate (SysLow declared first => runs first). */
    ecs_system(world, {
        .entity = ecs_entity(world, { .name = "SysLow",
            .add = ecs_ids(ecs_dependson(EcsOnUpdate)) }),
        .query.terms = {{ .id = ecs_id(Counter) }, { .id = FastTag, .oper = EcsNot }},
        .callback = SysLow });
    ecs_system(world, {
        .entity = ecs_entity(world, { .name = "SysHigh",
            .add = ecs_ids(ecs_dependson(EcsOnUpdate)) }),
        .query.terms = {{ .id = ecs_id(Counter) }, { .id = FastTag }},
        .callback = SysHigh });
    /* Promoter in an EARLIER phase (PreUpdate) so its tag-add is pending when the OnUpdate
     * variants run -- this is the case that can activate a dormant SysHigh mid-progress. */
    ecs_system(world, {
        .entity = ecs_entity(world, { .name = "Promoter",
            .add = ecs_ids(ecs_dependson(EcsPreUpdate)) }),
        .query.terms = {{ .id = ecs_id(Counter) }},
        .callback = Promoter });

    if (with_dummy) {
        /* A dummy entity that always has FastTag -> keeps SysHigh's query matched (ACTIVE). */
        ecs_entity_t dummy = ecs_new(world);
        ecs_set(world, dummy, Counter, { 0 });
        ecs_add_id(world, dummy, FastTag);
    }

    g_target = ecs_new(world);
    ecs_set(world, g_target, Counter, { 0 });   /* starts WITHOUT FastTag */

    g_promote_frame = 3;
    printf("--- Scenario %s (SysHigh initially %s) ---\n",
        with_dummy ? "B: dummy present" : "A: target alone",
        with_dummy ? "ACTIVE" : "DORMANT");
    int prev = 0;
    for (g_frame = 1; g_frame <= 6; g_frame++) {
        ecs_progress(world, 0);
        const Counter *c = ecs_get(world, g_target, Counter);
        int delta = c->count - prev; prev = c->count;
        printf("frame %d: target->count = %d  (delta this frame = %d%s)\n",
            g_frame, c->count, delta, (delta > 1) ? "  <<< DOUBLE-PROCESSED" : "");
    }
    int total = ecs_get(world, g_target, Counter)->count;
    ecs_fini(world);
    return total;
}

int main(void) {
    int a = run_scenario(0);
    printf("\n");
    int b = run_scenario(1);
    printf("\n==== RESULT ====\n");
    printf("Total count Run A (SysHigh dormant): %d\n", a);
    printf("Total count Run B (SysHigh active) : %d\n", b);
    if (a != b) {
        printf(">>> NON-DETERMINISTIC: identical per-frame inputs, different result (%d vs %d),\n", a, b);
        printf(">>> solely because of whether SysHigh was already active (world history).\n");
        return 1;
    }
    printf(">>> results equal (issue not reproduced in this configuration)\n");
    return 0;
}

[SanderMertens]

Problem 1: I don't think this should be an issue with deterministic simulation. Flecs will run systems if they match entities, and the mechanism through which this happens is deterministic. The difference you describe happen on different initial states, so it's expected that the result is different.

SysLow already processed the just-tagged entity → double-processed.

That is not double processing. You have two systems that match the same entity. They should both run for the entity.

Problem 2: I don't make guarantees about the order in which tables are iterated, though there is nothing undeterministic in the code that would cause different ordering if the state of the world is the same. However, if you populate the world in different order (as can happen during serialization) then the iteration order will be different.

The builtin JSON serialization doesn't guarantee that table order is the same (it likely won't be). If you need deterministic ordering, you'll have to build a custom serializer that creates tables in the same order as in the original world.

[Eragon-Brisingr]

Thanks for the detailed reply, and I agree with your core point — flecs itself is deterministic: the same world state produces the same schedule. Our problem lives precisely in the seam where two peers reach the same logical state via different paths. Let me pull out the one point in Problem 1 that actually causes our desync, since I don't think I stated it clearly before.

Problem 1

I think the key premise I failed to make clear: our two systems are mutually exclusive.

// One logical per-entity update, split into two mutually-exclusive variants, same phase:
ECS_SYSTEM(world, SysLow,  EcsOnUpdate, Counter, !FastTag); // handles entities WITHOUT the tag
ECS_SYSTEM(world, SysHigh, EcsOnUpdate, Counter,  FastTag); // handles entities WITH    the tag

At any given instant an entity can satisfy only one of the two predicates. The invariant of this pattern is "each entity is processed by exactly one variant, once per frame." So when — within a single frame — an entity is processed by SysLow first, then the tag commits mid-frame and it is processed again by SysHigh, that is double-processing from the "once per entity per frame" standpoint. Your "both systems should run for it" holds for systems whose queries overlap, but here the two queries can never match the same entity at the same instant.

The thing that actually causes the desync is this: target's computed result depends on whether an unrelated entity exists.

// Identical target, identical per-frame inputs. The ONLY difference is whether an
// unrelated dummy is present in the world.
Scenario A: world = { target }                    // SysHigh has no matching table -> DORMANT
Scenario B: world = { target, dummy(FastTag) }    // dummy keeps SysHigh's table non-empty -> ACTIVE

// On frame 3, a PreUpdate system adds FastTag to `target` (deferred).
// Result for the SAME target:
//   A: target.Counter = 4   // SysLow processed it; then SysHigh ACTIVATED mid-frame and processed it AGAIN
//   B: target.Counter = 3   // processed exactly once

dummy never interacts with target, yet its presence changes target's output — the only coupling path is the side effect of "dummy keeps SysHigh active." An entity's per-frame update should not depend on whether some unrelated entity keeps a system in the schedule. That is the determinism gap we care about, and it's independent of "A and B are different worlds": the issue is that the same target produces a different result because of an unrelated entity.

In our lockstep simulation, this is exactly the divergence between the authoritative path and the deserialization path:

• Server (authority, real-time, frame-by-frame): entities in the given rate band exist continuously, so SysHigh's matched tables are never empty → it is always active. When an entity transitions into the band, the variant is already scheduled; the transition merges at the frame boundary and the entity is processed by a single variant on the next frame → single fire.
• Client (restores a snapshot, then re-simulates forward): the snapshot it restored may contain no entities in that band at that moment → SysHigh is dormant. During catch-up, when the first entity crosses into the band, the variant activates mid-frame, after the mutually-exclusive SysLow has already processed that entity this frame → double fire.

In other words: identical snapshot content, identical forward inputs, but a different derived pipeline activation state ("a world built up frame-by-frame" vs "a world restored from a snapshot"), because whether a system is active is derived from the history of table-emptiness, not from the logical state the snapshot captures → the two peers desync.

What we need (the point here is scheduling consistency, not our specific game): we want frame-atomic scheduling — the set of "which systems run this frame, and which entities each visits" should be fixed at the start of the frame and not change due to a mid-frame structural change. Our current workaround freezes the pipeline op schedule at the start of the frame:

// pipeline.c, flecs_pipeline_update()
// Only (re)build the schedule at the start of a frame; a system that newly matches mid-frame
// does not activate and run this frame — it runs from the next frame instead.
bool rebuilt = start_of_frame ? flecs_pipeline_build(world, pq) : false;

This makes the per-frame system set history-independent, and in practice it fixes both the minimal repro above (A == B) and our real scenario. My questions:

1. Is deferring a system that "becomes matchable mid-frame" to the next frame a reasonable direction? Are there pitfalls we're not seeing?
2. Is there a supported, first-class way to keep a system always in the schedule regardless of whether its matched tables are empty, so the op structure is history-independent? (We tried EcsQueryMatchEmptyTables, but flecs_pipeline_build still marks the system inactive when its matched tables are EcsEmpty.)
3. Or, for this kind of "LOD / rate-limited mutually-exclusive split system," is there a deterministic pattern you'd recommend instead?

Problem 2

Thanks for confirming "same populate order → same iteration order," and for the custom-serializer suggestion.

For context on what we do today: rather than sorting query results each frame, we keep tables in a deterministic total order (primary key = table type hash, tie-break = lexicographic compare of the component-id array) at the point they're inserted into the table cache / query group, so iteration is naturally in a canonical order that is independent of table creation order, and it stays lock-free for multi-threaded systems. This works, but it's a source patch we maintain ourselves, and we'd prefer to achieve it through public API.

So my questions about the low-level API:

1. Is there a low-level API to enumerate all tables in the world — and the entities within each table — in a canonical, machine-independent order (for the serialization side)? For example, a stable table walk plus each table's entity list.
2. On the deserialization side, is there an API to create tables / restore entities in that same order in a controlled way, so the restored table order matches the source world? Concretely: what exactly determines table creation order — is it the order in which component ids are added? If we restore entities by adding their components in a fixed canonical order (e.g. sorted by component id), can we reliably reproduce the same table order as the source world?
3. Is there an existing first-class facility (order_by / group_by / sorting by table id) that yields a machine-independent iteration order, so we could drop the source patch above?

---

Overall flecs has been great to build on — these are the two spots where lockstep determinism needs extra care and we'd like to align with the intended approach.