The question this answers
The same input produced two different outputs. Is that a bug, or did I promise something I never actually specified?
A batch that transforms 10,000 documents across a worker pool and writes them to an output file, plus a report line summarizing them.
The output collection being appended to as tasks complete, and any counters, id generators or caches the tasks touch. In the corrected version, nothing is shared: each task writes a preallocated slot.
The output contains exactly one transformed record per input record. Whether the output *sequence* matches the input sequence is a separate promise — and the entire lesson is that you must decide, explicitly, whether you are making it.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
Five sources, and only some of them are bugs
Determinism means: same input, same output, every time. Concurrency undermines it in several distinct ways, and lumping them together is what makes the topic feel unmanageable. Separate them and each becomes a decision with a clear answer.
The critical division in the matrix is the last column. Nondeterminism in *timing* is inevitable and almost always acceptable — nobody promised which worker would handle document 4,000. Nondeterminism in *output* is only acceptable if you declared the output to be a set rather than a sequence. And nondeterminism arising from unsynchronized access to shared state is never acceptable: it is a race, and it can produce values that no sequential execution could ever produce.
The commonest real-world case is the middle one, and it is worth naming precisely: completion order is not submission order. A pool that returns results as they finish produces output in an order determined by how long each item took, which depends on the data, the machine, and what else was running. Nothing raced. The set of results is correct. But if a downstream consumer, a diff, a checksum or a human reviewer expects the input order, the output is wrong — and it is wrong in a way that is stable enough to pass tests on small inputs and appear only in production.
- Ask what you promised: a set, a sequence, or an exact byte stream. Most arguments about determinism are really arguments about an undeclared contract.
- A race can produce values no sequential run could produce. Nondeterministic ordering only produces values some sequential run could.
- That distinction is the practical test for "is this a bug or a shape".
| Source | Example | Varies per run? | Verdict |
|---|---|---|---|
| Scheduling / timing | Which worker gets which chunk; interleaving of unrelated tasks | Yes | Acceptable — inherent, and you never promised otherwise |
| Completion order | Results appended as tasks finish | Yes | Depends: fine for a set, a bug for a sequence. Decide and declare it |
| Reduction association | Floating-point sum at different worker counts | Stable per W | Usually acceptable with a tolerance — see Reduction Ordering: The Sum Changed When the Worker Count Did |
| Unsynchronized shared state | Two tasks incrementing a counter | Yes | Always a bug — a lost update, not a scheduling artifact |
| Environmental | Timestamps, random seeds, hash iteration, object addresses | Yes | Acceptable only if excluded from the output contract |
Two runs, both correct, both different
The schedule shows the same three documents processed twice by the same pool. Every step is correct, nothing is shared unsafely, and the two runs produce different files. Whether this is a defect depends entirely on a sentence someone should have written down and did not.
Notice what is stable and what is not. The *multiset* of outputs is identical across runs — every document appears exactly once, transformed correctly. The *sequence* is not. So the invariant "the output contains one record per input" holds under every schedule, while the invariant "the output is in input order" holds under some schedules and not others. Two different promises, one of which the code accidentally kept during testing because with three small documents the fast path always won.
This is also the point at which nondeterminism stops being an abstraction and becomes an operational cost. A nondeterministic output cannot be diffed between runs, cannot be checksummed for a cache key, cannot be used to prove a refactor changed nothing, and makes every flaky-test investigation start from scratch. Those costs are usually larger than the cost of fixing the order, which is why the fix is worth reaching for even when the ordering itself does not matter to any consumer.
| # | Worker 1 | Worker 2 | Output (append on completion) | State |
|---|---|---|---|---|
| 1 | RUN A: take doc1 (small) | · | · | out=[] |
| 2 | · | RUN A: take doc2 (large, embedded image) | · | out=[] |
| 3 | finishes doc1, appends | · | · | out=[doc1] |
| 4 | takes doc3, finishes, appends | · | · | out=[doc1, doc3] |
| 5 | · | finishes doc2, appends | · | out=[doc1, doc3, doc2] ✕ Output order is 1,3,2 — the multiset is right, the sequence is not. |
| 6 | RUN B (same input, colder cache): take doc1 | · | · | out=[] |
| 7 | · | RUN B: take doc2 | · | out=[] |
| 8 | · | finishes doc2 first this time, appends | · | out=[doc2] |
| 9 | finishes doc1, appends | · | · | out=[doc2, doc1] |
| 10 | takes doc3, finishes, appends | · | · | out=[doc2, doc1, doc3] |
Restoring order for free, and what real determinism costs
The cheapest fix in this whole file is the one below: stop appending on completion and start writing into a preallocated slot indexed by input position. The tasks still run in any order, still complete in any order, and still share nothing — index i is written only by the task for item i — and the output is deterministic. No lock, no ordering constraint on execution, no loss of parallelism. If you take one mechanical habit from this lesson, take this one.
That handles output ordering. Full determinism — same bytes out, every time, on every machine — is a bigger commitment and needs the other sources controlled too: a fixed chunk count so reductions associate identically (Reduction Ordering: The Sum Changed When the Worker Count Did), seeded randomness passed explicitly rather than drawn from a global, timestamps and ids injected rather than generated, and no dependence on iteration order of any hash-based collection. Each is small; together they are a design constraint that has to be maintained.
The strongest form — reproducing an exact interleaving for debugging — costs the most: it means recording scheduling decisions and replaying them (Deterministic Replay: Making the Schedule Reproducible), which is a tool investment justified only when Heisenbugs: The Bug That Leaves When You Look at It are costing more than the tooling. In between sits the practical middle ground most teams should aim for: deterministic outputs, nondeterministic execution. Let the scheduler do whatever it likes; make the observable result independent of what it chose. That is achievable with slot-indexed writes, fixed chunking and injected environment, and it is enough to make outputs diffable, cacheable and testable.
1const results: Doc[] = []2 3await Promise.all(docs.map(async (doc) => {4 const out = await transform(doc)5 results.push(out) // order = whoever finished first6}))7 8await writeFile(path, serialize(results))9// same input, different file, depending on how long each doc took1const results: Doc[] = new Array(docs.length)2 3await Promise.all(docs.map(async (doc, i) => {4 const out = await transform(doc)5 results[i] = out // index i is written only by task i6}))7 8await writeFile(path, serialize(results))9// same input, same file, every run -- diffable and cacheableBoth versions run every transform concurrently and neither takes a lock. The first makes output order a function of execution timing; the second makes it a function of input order, because each task owns exactly one index and no two tasks write the same slot. The cost is preallocating the array — and a map that already returns values in order (await Promise.all(docs.map(transform))) gets the same guarantee for free, which is why the combinator is almost always the better tool than a hand-rolled collector.
Key points
- Nondeterminism has five distinct sources and only one of them — unsynchronized shared state — is always a bug.
- Completion order is not submission order. Whether that matters depends on whether you promised a set or a sequence, and that promise is usually undeclared.
- The practical test: a race can produce values no sequential run could; nondeterministic ordering only produces values some sequential run could.
- Writing results into preallocated slots indexed by input position restores deterministic output at zero cost to parallelism.
- Aim for deterministic outputs with nondeterministic execution; full replay-level determinism is a tooling investment, not a default.
- Determinism buys diffable, cacheable, testable outputs — usually worth more than the ordering itself.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • A scheduler chooses which task runs when; that choice depends on load, cache state, data size and other processes, and is not reproducible.
- • If results are collected as tasks complete, the collection order is a function of those durations and therefore varies.
- • If results are written to positions derived from the input, the collection order is a function of the input and does not vary.
- • Reductions over floating point associate differently at different worker counts, adding a second, W-dependent source of variation.
- • Environmental inputs — clock, entropy, hash seeds, addresses — vary per process and leak into output unless injected explicitly.
- • Run A: W1 takes doc1, W2 takes doc2, W1 finishes and appends, W1 takes doc3 and appends, W2 appends. Output [1,3,2].
- • Run B, same input: W2 finishes first, appends; W1 appends; W1 does doc3 and appends. Output [2,1,3]. Both correct as multisets, neither ordered, and they disagree.
- • With slot writes: any of the above orderings produces [1,2,3], because each task writes only its own index and the reader reads by index.
- • The genuine race, for contrast: W1 reads processed (41); W2 reads processed (41); W1 writes 42; W2 writes 42 — one document processed and not counted. That is a value no sequential execution could produce, which is what distinguishes it.
- • The environmental one: each output record embeds
new Date(), so even with perfect ordering the two files differ. Determinism requires injecting the clock, not just fixing the order.
- • Slot-indexed writes guarantee output order equals input order, with no synchronization and no constraint on execution order.
- • An all/gather combinator guarantees results are returned in submission order regardless of completion order — the reason to prefer it over a hand-rolled collector.
- • Nothing guarantees the same worker handles the same item across runs, or that timing is reproducible. Those are not obtainable and rarely needed.
- • Deterministic output does NOT imply a deterministic schedule, and does NOT mean concurrency bugs are absent — a program can produce ordered output and still have a lost update on a counter.
- • Fixing ordering does NOT fix reduction association; those are separate sources needing separate fixes.
- • Cross-machine determinism additionally requires controlling floating-point behaviour, library versions and any hash-order dependence.
- • A shared append-on-completion collection is a contention point as well as an ordering problem: every completing task takes the same lock or touches the same cache line.
- • Slot-indexed writes have neither problem — disjoint indices, no lock — so the deterministic version is also the faster one, which is unusual and worth noticing.
- • Enforcing output order *at execution time* (making task i wait for task i-1) would serialize the pool completely. Order the output, not the execution.
- • Deterministic replay tooling adds recording overhead on every scheduling decision, which is why it lives in a debugging build rather than production.
- • Output files that differ between identical runs, breaking diffs, content-addressed caches and reproducible-build claims.
- • Tests that pass on small inputs — where the fast path always wins — and fail intermittently on large ones.
- • Downstream consumers silently depending on an order that was never guaranteed, and breaking when the pool size changes.
- • A real race misdiagnosed as "just nondeterministic ordering" and left in, producing values no sequential run could produce.
- • Timestamps and generated ids embedded in output, defeating determinism even after ordering is fixed.
- • Serializing execution to obtain ordering, discarding the parallelism the pool existed for.
- • Any batch producing an artifact that will be diffed, cached by content, audited or compared between releases.
- • Test suites: deterministic output turns flaky assertions into stable ones and makes a failure reproducible on the first attempt.
- • Incident investigation: a reproducible run is the difference between an afternoon and a week.
- • Content-addressed caching and reproducible builds, where a deterministic output is the entire mechanism.
- • When determinism is pursued by serializing execution, trading all the parallelism for an ordering nobody consumes.
- • When it is demanded of quantities that are inherently continuous, forcing exact-equality assertions on floats.
- • When replay tooling is built before the cheaper fixes — slot writes, fixed chunking, injected clocks — have been tried.
- • When the pursuit spreads to timing determinism, which is not achievable on a shared machine and not needed.
- • Run the job twice on the same input and diff the outputs. Byte-identical or not is the whole measurement, and almost nobody runs it.
- • Vary the worker count and diff again: differences that appear only when W changes point at reduction association rather than completion order.
- • Run repeatedly at fixed W: variation here means a real race or environmental leakage, not ordering.
- • Grep the output path for clock, entropy and identity sources — the usual reason a correctly-ordered output still differs.
- • Track flaky-test rate as the outcome metric; it is what determinism work is actually buying.
- • Determinism becomes a property you must state and defend: which parts of the output are ordered, which are sets, and what tolerance applies to numbers.
- • Environmental inputs must be injected rather than read from globals, which touches call signatures throughout the code.
- • Fixed chunking constrains load balancing slightly, and rules out naive dynamic partitioning for the reduction.
- • Replay-level determinism requires recording infrastructure with real overhead and its own maintenance burden.
- • The guarantee must be tested, or it decays — one
pushin a completion callback reintroduces the problem silently.
- • Declare the output unordered and sort at the end when order is needed. Simple, honest, and correct if the sort key is stable.
- • Sort the output by a key derived from the input, which gives determinism without touching the concurrency at all.
- • Compare outputs as sets or with a canonical serialization, rather than as byte streams, when the ordering genuinely has no meaning.
- • Use the runtime's ordered combinator instead of collecting manually — the guarantee comes free and cannot be accidentally lost.
- • Accept nondeterminism and invest in tolerant assertions and good observability, when the artifact is never diffed or cached.
The lost update, step by step
| # | Task A — counter++ | Task B — counter++ | State |
|---|---|---|---|
| 1 | rA ← counter | · | counter=0 rA=0 rB=— |
| 2 | · | rB ← counter | counter=0 rA=0 rB=0 |
| 3 | rA ← rA + 1 | · | counter=0 rA=1 rB=0 |
| 4 | counter ← rA | · | counter=1 rA=1 rB=0 |
| 5 | · | rB ← rB + 1 | counter=1 rA=1 rB=1 |
| 6 | · | counter ← rB | counter=1 rA=1 rB=1 ✕ 2 increments completed, counter = 1 |
Two increments, twenty schedules: find the one that loses an update
| # | Task A — counter++ | Task B — counter++ | State |
|---|---|---|---|
| 1 | rA ← counter | · | counter=0 rA=0 rB=0 |
| 2 | rA ← rA + 1 | · | counter=0 rA=1 rB=0 |
| 3 | counter ← rA | · | counter=1 rA=1 rB=0 |
| 4 | · | rB ← counter | counter=1 rA=1 rB=1 |
| 5 | · | rB ← rB + 1 | counter=1 rA=1 rB=2 |
| 6 | · | counter ← rB | counter=2 rA=1 rB=2 |
Race detector lab
| task | access | location | holding |
|---|---|---|---|
| A | read | count | — |
| A | write | count | — |
| B | read | count | — |
| B | write | count | — |
| # | Task A | Task B | State |
|---|---|---|---|
| 1 | r1 = count | · | count=0 done=0 |
| 2 | · | r2 = count | count=0 done=0 |
| 3 | count = r1 + 1 | · | count=1 done=1 |
| 4 | · | count = r2 + 1 | count=1 done=2 ✕ count equals the number of increments that have completed — broken here |
What people believe, and what is true
Different output on the same input means we have a race.
It usually means completion order leaked into the output. A race produces values no sequential run could produce; ordering nondeterminism produces values some sequential run could.
To get deterministic output we have to process items in order.
Process in any order and *write* in input order. Slot-indexed writes give deterministic output with full parallelism and no synchronization.
Determinism is only needed in tests.
It is what makes outputs diffable, content-addressable and auditable. Reproducible builds and content-addressed caches are determinism arguments end to end.
Our output is ordered, so the computation is deterministic.
Ordering is one source. Embedded timestamps, generated ids, hash iteration order and floating-point association each break determinism independently.