The question this answers
When is "the output differs between runs" acceptable, and when is it the symptom I am chasing?
A fan-out that fetches eight product records concurrently and assembles them into a response list, alongside a parallel sum of eight floating-point partial results.
The results array the eight tasks write into, and the accumulator the partial sums are combined into. Both are shared; only one of them has an invariant that ordering can break.
The response contains exactly the eight requested products, one entry each, with the correct data — *regardless of the order the fetches complete in*. The sum equals the total, to within the precision the caller was promised.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
Two runs, two orders, and only one of them matters
Concurrency introduces nondeterminism by construction: the scheduler is free to run ready tasks in any order it likes, and the order it picks depends on core count, load, cache state, interrupt timing and the phase of whatever else is running on the machine. Two runs of the same binary on the same input are two different schedules.
The important move is to separate *nondeterminism of the schedule*, which you cannot eliminate and should not try to, from *nondeterminism of the result*, which is a design choice you make and should be able to defend. The schedule below shows the same eight-way fetch completing in two different orders. If the code appends results as they arrive, the output list order differs between runs — a result-level nondeterminism that is a bug if the API promised a stable order and a non-event if it did not. If the code writes each result into its own slot, the output is byte-identical in both runs despite the schedule differing wildly.
That is the general technique and it is worth stating as a rule: make the result a function of the inputs, not of the completion order. Indexed writes instead of appends, sorting before returning, keying by request rather than by arrival. Each costs almost nothing and converts an unstable output into a stable one without constraining the scheduler at all.
| # | fetch(sku-1) | fetch(sku-2) | fetch(sku-3) | State |
|---|---|---|---|---|
| 1 | RUN A: completes first; results.append(sku-1) | · | · | results=[sku-1] |
| 2 | · | · | RUN A: completes second; results.append(sku-3) | results=[sku-1, sku-3] |
| 3 | · | RUN A: completes third; results.append(sku-2) | · | results=[sku-1, sku-3, sku-2] |
| 4 | · | RUN B: completes first; results.append(sku-2) | · | results=[sku-2] |
| 5 | RUN B: completes second; results.append(sku-1) | · | · | results=[sku-2, sku-1] |
| 6 | · | · | RUN B: completes third; results.append(sku-3) | results=[sku-2, sku-1, sku-3] ✕ The invariant said "in request order". Run A returned [1,3,2] and Run B returned [2,1,3]; neither is request order, and the client's pagination cursor is now meaningless. |
| 7 | FIX: results[0] = sku-1 (indexed write, any order) | · | · | results=[sku-1, _, _] |
| 8 | · | · | FIX: results[2] = sku-3 | results=[sku-1, _, sku-3] |
| 9 | · | FIX: results[1] = sku-2 | · | results=[sku-1, sku-2, sku-3] |
append made the *result* a function of completion order; the indexed write made it a function of the request. Same concurrency, same performance, one stable output — and no synchronization was added, because each task writes a different slot.Acceptable, or a bug?
Not all result nondeterminism is wrong. A work-stealing scheduler assigning tasks to different cores on each run, a load balancer choosing a different replica, a Promise.race returning whichever finished first, a set iterated in unspecified order — all of these vary between runs and all of them are fine, because nothing promised otherwise.
The test is contractual, not aesthetic: did anything promise this would be stable? An API response schema, a paginated cursor, a log ordering used for debugging, a reduction whose result feeds a financial report, a hash used as a cache key. If yes, the variation is a bug. If no, forcing determinism costs performance and buys nothing.
One case deserves its own row because it surprises people: floating-point reduction. Addition is not associative in floating point, so summing eight partials in a different order gives a different last bit. That is not a race, not a bug in the usual sense, and not fixable by locking — the values are all correct and the order is legitimately variable. Whether it matters depends entirely on what the number is for. See Reduction Ordering: The Sum Changed When the Worker Count Did and Determinism: Same Input, Same Output?.
| What varies | Cause | Promised stable? | Verdict | What to do |
|---|---|---|---|---|
| Order of a result list | appended in completion order | yes — the API documents request order | BUG | Write into indexed slots, or sort before returning. Costs nothing. |
| Which replica served the request | load balancer choice | no | FINE | Nothing. Record it in the trace so a bad replica is still identifiable. |
| Last bits of a floating-point total | parallel reduction, addition is not associative | depends — a financial total usually is | DEPENDS | Fix the reduction tree shape, use a deterministic order, or use exact decimal arithmetic. See Reduction Ordering: The Sum Changed When the Worker Count Did. |
| Counter value after a fixed number of increments | lost update on a read-modify-write | yes — always | BUG | This is a race condition, not benign nondeterminism. See Interleavings: The Schedule Is Part of the Program. |
| Interleaving of log lines from concurrent tasks | scheduler | no, unless you promised a total order | FINE | Add a correlation id per task so lines can be reassembled. See What to Instrument in a Concurrent System. |
| Whether the test passes | the schedule that happened to occur | yes — a test must be a decision procedure | BUG | A flaky test is a real defect report about the code or the test. Never retry it away. |
What this does to testing
Here is the uncomfortable consequence. A test executes one schedule out of a space the scheduler chose, non-uniformly, on your machine, under your load. When it passes, it has established that *that* schedule is correct. It has established nothing about the other schedules, and the scheduler is under no obligation to ever show you them locally while producing them constantly on a loaded 64-core host.
Which is why a flaky concurrency test must never be retried away. A test that passes 999 times in 1000 is not a flaky test; it is a *correct* test reporting a bug that occurs about once in a thousand schedules. Adding a retry deletes the only evidence you have and converts a reproducible-at-1-in-1000 defect into an unreproducible production incident. See Heisenbugs: The Bug That Leaves When You Look at It.
The output below is what taking this seriously looks like: the same assertion run a hundred thousand times with the scheduler deliberately perturbed, reporting how many schedules broke the invariant rather than pass/fail. That number is a measurement, it can be tracked over time, and it goes to zero when the bug is fixed rather than when the retry count is raised. See Stress Testing: A Test That Passed Once Proves Nothing and Deterministic Replay: Making the Schedule Reproducible.
$ ./stress --scenario two-increments --iters 100000 --threads 8 --perturb
scenario : two-increments invariant: counter == 2 after both tasks
iterations : 100000 threads: 8 perturb: random yield after each shared access
baseline (no perturbation)
violations 3 / 100000 (0.003%) <-- passes almost always
first violation at iteration 24,918
wall time 1.9 s
with scheduler perturbation
violations 41,207 / 100000 (41.2%) <-- the same bug, made visible
first violation at iteration 2
wall time 14.6 s
after fix (atomic fetch_add)
violations 0 / 100000 (0.000%)
with perturbation 0 / 100000 (0.000%)
wall time 2.1 s
interpretation
- 0.003% is why the test suite is green. It is not evidence of correctness;
it is a measurement of how rarely the scheduler produces the bad schedule
on THIS machine under THIS load.
- perturbation does not create the bug. It changes the sampling distribution
of schedules so that the existing bug is sampled often.
- the number to track in CI is "violations under perturbation", not pass/fail.
A retry policy would have turned all three lines into "PASS".
CAVEAT (SIMULATED): these counts illustrate the shape of such a report.
Real rates depend on the machine, the scheduler and the load, and differ
between runs on identical hardware.Key points
- Schedule nondeterminism is inherent to concurrency and cannot be removed. Result nondeterminism is a design choice you make, usually accidentally.
- The rule that fixes most of it: make the result a function of the inputs, not of the completion order. Indexed writes instead of appends; sort before returning.
- Whether varying output is a bug is a contractual question — did anything promise stability? — not a matter of taste.
- Floating-point reduction varies with order because addition is not associative. It is not a race, and locking does not fix it.
- A passing test proves one schedule was correct and says nothing about the rest of the space.
- A test that fails 1 time in 1000 is a correct test reporting a real defect. Retrying it deletes the evidence and ships the bug.
- The useful CI signal is violations-per-N-iterations under deliberate perturbation, not pass/fail.
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.
- • The runtime maintains a set of runnable tasks and picks one; the choice depends on the OS scheduler, core availability, cache state and interrupt timing, none of which the program controls.
- • Each distinct choice sequence is a distinct schedule, and the program's observable output is a function of both the input and the schedule.
- • If every observable output is identical across schedules, the program is deterministic in result despite being nondeterministic in execution — which is the property to aim for.
- • If the output depends on completion order, arrival order or thread identity, the result varies with the schedule and every consumer of that output inherits the variation.
- • Testing samples this space non-uniformly, biased by the machine it runs on, which is why local and production sampling differ so sharply.
- • Run A completes 1, 3, 2 and appends in that order; Run B completes 2, 1, 3. The response list order differs — a bug only if request order was promised.
- • The same two runs writing into indexed slots produce byte-identical output despite completely different schedules, with no synchronization added.
- • Two increments interleaved as read-read-write-write produce 1 instead of 2 — result nondeterminism that is unambiguously a bug at every layer.
- • A parallel sum reducing as
((a+b)+(c+d))in one run and(a+(b+(c+d)))in another produces two totals differing in the last bits, with no race and no incorrect step. - •
Promise.racereturning a different winner on each run: nondeterministic by definition, correct by contract, and the reason the function exists.
- • The runtime guarantees each task's own steps run in program order. It guarantees nothing about the relative order of two tasks' steps.
- • A stable result is guaranteed only by construction — indexed writes, sorting, deterministic reduction trees. No primitive provides it for you.
- • A lock guarantees mutual exclusion, not fairness or order. Which waiter acquires next is unspecified in most implementations. See Fairness.
- • A passing test guarantees the executed schedule was correct. It provides no coverage measure over the schedule space, and no mainstream test runner reports one.
- • Deterministic replay guarantees a *recorded* schedule can be re-executed. It does not make the program deterministic and does not find schedules that were never recorded. See Deterministic Replay: Making the Schedule Reproducible.
- • Forcing result determinism sometimes forces ordering, and ordering forces waiting: a barrier so that stage N completes before stage N+1 costs you the tail of the slowest task. See Barriers.
- • Deterministic reduction constrains the combining tree, which can prevent the scheduler from balancing work. That is a real cost, paid for reproducibility.
- • Indexed writes cost nothing at all — each task writes a different slot — unless the slots share a cache line, in which case they cost a great deal. See False Sharing: Different Variables, Same Cache Line.
- • Heisenbug — the failure vanishes under a debugger, a log statement or a slower build, because each of those changes the schedule distribution. See Heisenbugs: The Bug That Leaves When You Look at It.
- • Flaky test — a real defect misclassified as tooling noise and retried away, then reported months later as an unreproducible incident.
- • Order-dependent output that a downstream consumer depends on, discovered when a client's pagination or diff breaks rather than when your test fails.
- • Reduction drift — a total that differs in the last decimal between runs, which fails reconciliation against a system doing the arithmetic sequentially.
- • Works-on-my-machine — two cores locally, sixty-four in production, and a schedule space that is barely sampled on the developer's laptop.
- • Accepting nondeterminism where nothing promised order is what lets a scheduler balance work; forcing determinism there is pure cost.
- • Deliberate nondeterminism is sometimes the point: randomised retry jitter exists precisely to make timing vary and break up synchronised herds. See Thundering Herd.
- • Perturbed stress testing turns rare schedules into common ones and is the single most effective way to find this class of bug before production.
- • When output feeds a system that assumes stability: a cache key, a diff, a checksum, a paginated cursor, a financial reconciliation.
- • When it makes debugging non-repeatable — you cannot bisect a failure you cannot reproduce, which is why replay tooling exists at all.
- • When it is used as an excuse: "concurrency is nondeterministic" is true of the schedule and false of the result, and the phrase is regularly used to close a bug that should have been fixed.
- • Run the same input N times and diff the outputs byte-for-byte. Any difference is either a promise you are breaking or a promise you should document.
- • Track violations per N iterations under perturbation as a CI metric, not pass/fail. It trends, it can regress, and it distinguishes "fixed" from "made rarer".
- • Vary the environment deliberately: thread count above core count, a random yield injected after each shared access, an artificially slowed dependency. Each shifts the sampling distribution.
- • Record schedules for failing runs so they can be replayed. A failure you can replay is an ordinary bug; one you cannot is a research project. See Deterministic Replay: Making the Schedule Reproducible.
- • Count flaky-test retries in CI. A rising retry count is a concurrency defect budget being spent silently.
- • Deterministic-by-construction output requires design attention on every path that assembles a result — one
appendadded later reintroduces it. - • Replay and record tooling is a real system with its own overhead and its own failure modes, and it typically only covers the runtime it was built for.
- • Perturbed stress tests are slow — the run above took 14.6 s against 1.9 s — so they usually live in a separate, less frequent CI stage, and separate stages get ignored.
- • Explaining to a stakeholder why a test that passes 99.997% of the time indicates a defect is organisational work that recurs every time it comes up.
- • Remove the concurrency where it buys little. A sequential loop over eight fast local lookups is deterministic, simpler, and often not measurably slower. See Concurrency Is Always Bought With Complexity.
- • Keep the concurrency and make the assembly deterministic: indexed writes, then a single ordered pass at the end. Usually a one-line change.
- • Use exact arithmetic where the last bits matter — integers of minor units, or a decimal type — rather than trying to order floating-point additions. See Reduction Ordering: The Sum Changed When the Worker Count Did.
- • Use structured concurrency so results are collected in a defined order by the framework rather than by whoever finishes first. See Structured Concurrency and Promise.all & gather.
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 |
Scheduler timeline
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 |
What people believe, and what is true
Concurrent programs are nondeterministic, so unstable output is expected.
The *schedule* is nondeterministic. The *result* is only nondeterministic if you let the result depend on the schedule, which is almost always avoidable and usually free to avoid.
The test is flaky, so we should retry it.
A test failing 1 in 1000 has found a defect that occurs in 1 in 1000 schedules. Retrying converts a caught bug into an uncaught one and destroys the only reproduction you had.
It works on my machine, so the schedule must be fine.
Your machine samples a narrow part of the schedule space — few cores, little load. Production samples a different part, constantly.
Different totals from a parallel sum means there is a race.
Floating-point addition is not associative. Every partial is correct and the combining order legitimately varies. Fix the reduction order or the number type, not the synchronization.