Testing Concurrent Code Deterministically

Concurrent failures are often reproducible in theory and evasive in practice. A test passes ten thousand times, fails once under load, and passes again when logging is enabled. The usual response is to add sleeps or repeat the test more aggressively. That may increase the chance of one interleaving, but it neither states which interleaving matters nor makes a failure replayable.

Deterministic concurrency testing takes a different view: the schedule is test input. The harness controls selected execution points, records each scheduling choice, and checks invariants after or during every execution. A failing choice sequence can then be replayed like an ordinary data fixture. This does not eliminate the need for race detectors or stress tests; it gives those techniques a precise center by turning known concurrency boundaries into enumerable, explainable cases.

The goal is not to simulate every instruction. It is to control the decisions that can change a component’s observable state: reads and writes, lock operations, message delivery, timer firing, task wakeups, and cancellation. Good tests expose those boundaries without rewriting the algorithm into a different one.

Make the Schedule a First-Class Input #

A sequential test supplies values and expects an output. A deterministic concurrent test also supplies an order in which enabled actions may proceed. For two tasks A and B, a schedule might be A, A, B, B, A, B. Each symbol permits one task to run until its next controlled yield point.

This model separates three concerns:

• Scenario input: initial records, messages, capacities, and requested operations.
• Schedule input: which enabled task or event advances at each choice point.
• Oracle: invariants and allowed terminal outcomes.

The oracle should rarely require one exact final ordering unless ordering is part of the contract. A queue may legally return either producer’s item first while still requiring no loss or duplication. Testing only an expected sequence can reject valid executions and miss an invalid state that happens to produce familiar output.

A controlled scheduler needs stable task identities and explicit choice points. It should record the set of enabled tasks at every step, the selected task, and a compact state digest. If a replay requests a task that is no longer enabled, the harness must fail with a schedule-divergence report rather than silently choosing another task. Silent fallback destroys reproducibility.

Virtual time belongs in the same input. Advancing a fake clock should enable expired timers without deciding automatically which timer callback or ready task runs next. Time and scheduling are related choices, not one opaque sleep() operation. A test can then express “both the completion and timeout are enabled; run timeout first” and replay the opposite order separately.

Control only meaningful boundaries. Yielding after every arithmetic instruction creates an enormous search space and tests a synthetic program. Yielding around shared-state access, publication, waits, wakeups, and external effects usually captures the decisions that matter.

Define State Machines and Invariants Before Schedules #

A schedule has value only when the test knows what must remain true. Start by expressing the component as a state machine: states, commands, transition preconditions, and observable results. Concurrent execution may reorder or overlap commands, but it must preserve the component’s safety properties.

Useful invariant classes include:

Conservation. Items are neither created nor lost. For a bounded queue, produced items equal queued plus consumed items, accounting for rejected submissions.

Uniqueness. A job, lease, or message has at most one active owner. Duplicate delivery may be allowed at a boundary, while duplicate committed processing is not.

Bounds. Counts and capacities remain within valid ranges. An inventory value is never negative; outstanding permits never exceed the configured limit.

State-transition legality. A future settles once, a resource is not used after close, and shutdown cannot transition back to running.

Progress under stated assumptions. If an operation remains enabled and the scheduler is fair, it eventually completes. Progress requires assumptions about fairness and dependencies; a finite test cannot prove that an arbitrary runtime will schedule a thread eventually.

Check invariants at intermediate states, not only at the end. A component may briefly violate a bound and repair it before return, while another task can observe the invalid state in between. Conversely, avoid asserting private representation details that are intentionally transient but unobservable under the component’s synchronization.

For APIs intended to be linearizable, define a sequential reference model. Each completed concurrent operation must appear to take effect at some point between invocation and response. The checker searches for a sequential ordering consistent with real-time precedence and compares it with the model. This is stronger than comparing only final state because different histories can end identically after returning impossible intermediate results.

Worked Example: Reproduce an Oversold Reservation #

Consider an in-memory reservation operation with one remaining seat. The naive implementation reads availability, checks it, and writes the decremented value. Two calls can both read 1, both report success, and both write 0. The final count looks valid, but two reservations were granted for one seat.

A small generator model makes the relevant interleaving explicit:

type Inventory = { available: number };
type Result = { taskId: string; reserved: boolean };

function* reserve(
  taskId: string,
  inventory: Inventory,
  results: Result[],
): Generator<string, void> {
  yield `${taskId}:before-read`;
  const observed = inventory.available;
  yield `${taskId}:after-read`;

  if (observed === 0) {
    results.push({ taskId, reserved: false });
    return;
  }

  yield `${taskId}:before-write`;
  inventory.available = observed - 1;
  results.push({ taskId, reserved: true });
  yield `${taskId}:after-write`;
}

function runSchedule(schedule: ReadonlyArray<'A' | 'B'>): {
  inventory: Inventory;
  results: Result[];
  trace: string[];
} {
  const inventory = { available: 1 };
  const results: Result[] = [];
  const tasks = {
    A: reserve('A', inventory, results),
    B: reserve('B', inventory, results),
  };
  const trace: string[] = [];

  for (const taskId of schedule) {
    const step = tasks[taskId].next();
    if (!step.done) trace.push(step.value);
  }

  return { inventory, results, trace };
}

The schedule below drives both calls past their reads before allowing either write:

const execution = runSchedule(['A', 'A', 'B', 'B', 'A', 'A', 'B', 'B']);
const successes = execution.results.filter((result) => result.reserved).length;

if (successes > 1) throw new Error('More reservations succeeded than capacity');
if (execution.inventory.available !== 1 - successes) {
  throw new Error('Inventory and successful reservations disagree');
}

The important schedule states are:

The conservation invariant fails even though available never becomes negative. This demonstrates why an oracle based only on a final bounds check is incomplete.

The generator is a specification harness, not a proposed production implementation. A real repair makes reservation one atomic state transition, for example under a mutex, in a database conditional update, or with a compare-and-set loop. The deterministic integration test should then control execution immediately before and after that actual synchronization boundary and verify that every explored schedule permits at most one success.

A compare-and-set repair may cause the losing task to retry after its first update fails. The test oracle should allow that retry and require it eventually to observe zero. It should not require task A specifically to win, because either winner is legal.

Control Real Code with Barriers and Injectable Effects #

Generator models are excellent for algorithms, but integration tests need to coordinate ordinary async or threaded code. Use barriers, latches, and controllable test doubles to pause operations at semantic boundaries. A fake store can expose “read started,” wait for the test to release it, and then return a chosen version. A fake transport can queue deliveries until the harness selects one. A fake timer service can expose all expired callbacks as enabled events.

Hooks should be inert in production and should not carry correctness. For example, an optional test probe can observe beforeCommit and await a barrier, while the transaction remains protected by its real synchronization. If removing the hook changes the algorithm, the test is exercising an alternate implementation.

Avoid sleeps as coordination. sleep(20) says nothing about whether another task reached the intended point. On a fast machine it wastes time; on a loaded machine it races. A barrier says “do not continue until both operations have completed their reads,” which is deterministic and self-checking. Give barriers a test-level watchdog so a broken test fails with the names of tasks and barriers still waiting rather than hanging indefinitely.

Dependency injection is especially useful for clocks, random sources, executors, and I/O. The production implementation receives the real dependency; tests receive one whose events are recorded and advanced explicitly. Keep the abstraction narrow. Replacing an entire database with an unconstrained map may erase transaction behavior that the test is supposed to verify.

Controlled schedulers should also model cancellation and failure. At any enabled yield point, inject an exception, cancellation, or task termination where the API permits it. Then assert resource and state invariants: locks released, waiters notified, counters restored, and futures settled exactly once.

Explore Interleavings with Bounded Model Checking #

Handwritten schedules capture known bugs, but humans are poor at enumerating all meaningful interleavings. A bounded scheduler can explore the choice tree automatically. At each step it selects each enabled task in turn, snapshots or reconstructs state, and continues until all tasks finish, an invariant fails, or a bound is reached.

Naive enumeration grows exponentially. Two tasks with several yield points are manageable; dozens of tasks are not. Several reductions preserve useful coverage:

• Bound the number of tasks, steps, preemptions, retries, and virtual-time advances.
• Explore small capacities such as zero, one, and two, where boundary bugs concentrate.
• Treat consecutive thread-local operations as one transition.
• Use partial-order reduction to avoid exploring permutations of independent actions.
• Hash abstract states and avoid revisiting an equivalent state with an equal or worse bound.
• Prioritize schedules that switch tasks around shared accesses or wakeups.

Independence must be conservative. Two operations on separate keys may still contend through a shared capacity counter or eviction policy. An incorrect reduction can prune the only failing schedule. Start with fewer reductions and validate each independence rule against the component’s real state.

When exploration finds a failure, minimize the schedule. Remove unnecessary task switches, commands, and injected faults while preserving the invariant violation. A short counterexample such as A.read, B.read, A.write, B.write is much easier to understand than a trace with hundreds of choices.

Bounded checking proves only the explored model and bounds. It can establish that no violating schedule exists for two clients and three operations under the modeled semantics, not that an unbounded production system is universally correct. Its value is high because many concurrency defects have small counterexamples, but reports must state the bound honestly.

Combine Determinism with Race Detection and Seeded Stress #

Controlled yields can miss a shared memory access that was never instrumented. Race detectors cover that gap by observing actual reads, writes, and synchronization in an instrumented run. Run deterministic scenarios under the race detector when possible: the schedule reaches the intended boundary, while the detector checks lower-level accesses within it.

Race freedom is necessary in many memory models but not sufficient for logical correctness. The reservation bug can occur through individually race-free database operations that form a non-atomic read-modify-write sequence. Invariants and history checking catch the protocol failure; a memory race detector may correctly report nothing.

Seeded stress tests add scale and runtime realism. Generate operation sequences, delays, failures, and scheduling hints from a recorded seed. On failure, save the seed, scenario, runtime configuration, and event trace. Replay should first reproduce the exact generated scenario; then deterministic barriers can isolate the critical ordering.

Stress is most useful when assertions remain strong. Counting crashes alone misses lost updates and duplicate effects. Continuously check conservation, uniqueness, legal state transitions, and response histories. Vary worker counts, queue capacities, cancellation points, and resource limits. Run long stress suites outside latency-sensitive unit-test lanes, while keeping minimized deterministic regressions in the fast suite.

Neither random sleeps nor an unrecorded runtime schedule are valid seeds. Seed every pseudo-random source the harness owns, but acknowledge that operating-system and hardware scheduling may still vary. Record event traces so a non-replayable stress failure still provides evidence for constructing a controlled case.

Avoid Testing a Friendlier Program Than Production #

Instrumentation can accidentally serialize operations. A single global logging mutex around every yield point may remove the race. Heavy tracing changes timing and memory layout. Test-only implementations of locks, queues, or stores may offer stronger guarantees than their production counterparts.

Other common failure modes are:

• Exploring only one task count or capacity and missing boundary behavior.
• Assuming every yield is always enabled, even when the real task would block.
• Declaring deadlock when all tasks are legitimately waiting for an external event not modeled.
• Treating unfair schedules as product failures when progress requires documented fairness.
• Checking only final state and ignoring impossible returned histories.
• Keeping enormous failing traces instead of minimizing and promoting them to regressions.
• Mocking atomicity into a dependency that does not provide it in production.
• Using deterministic execution to claim absence of uninstrumented memory races.

Validate the harness itself with deliberately broken components. Confirm it finds a known lost update, duplicate completion, missed wakeup, and leaked permit. Confirm the fixed versions pass all explored schedules. Test schedule replay and divergence reporting. A concurrency test framework is infrastructure; a bug in its enabled-task accounting can create false confidence.

Keep scheduler decisions separate from assertions. An assertion callback that advances another task can introduce hidden scheduling. Trace data should be immutable snapshots or stable identifiers, not references to state that later changes and rewrites the apparent history.

Build a Layered Verification Workflow #

Use the cheapest precise layer first. Pure state-machine tests validate transition rules. Handwritten deterministic schedules cover each known race boundary. Bounded exploration searches small configurations. Race detection checks instrumented memory behavior. Seeded stress exercises scale, integration, and runtime mechanisms. Production telemetry then watches invariant violations, stuck operations, duplicate outcomes, and unexpected recovery paths without pretending to be a proof.

For every concurrency defect, preserve four artifacts: the initial scenario, minimized schedule, violated invariant, and repaired synchronization rule. A regression test should fail for the original reason, not because it expects incidental task names or timing.

Review test coverage by choice point rather than line. Ask whether completion can race cancellation, close can race send, timeout can race wakeup, and two owners can contend for the final item. Exercise both orders at each boundary, plus injected failure between resource acquisition and publication.

Deterministic testing makes concurrency explainable. The harness chooses among enabled events, virtual time exposes timers, and invariants judge outcomes independent of a favored winner. Model checking broadens the schedule set; race detectors and seeded stress cover what the model omits. Together they replace “run it until it fails” with a reproducible argument about which executions were tested, what must remain true, and exactly how a counterexample violates the contract.