Reproducible Randomness in Parallel Pipelines

Why Parallel Randomness Needs an Assignment Rule

A stochastic analysis may use randomness at several points: selecting cells for a diagnostic subset, drawing bootstrap samples, initializing a model, or simulating a null distribution. In a sequential script, one random-number generator can supply these draws in a fixed order. In a parallel pipeline, multiple tasks may request random numbers at the same time. If they share one mutable generator state, the order of requests can depend on scheduling, so the results can change when the worker count or execution order changes.

The relevant goal is not merely to set one starting seed. It is to make a reproducible assignment from each logical task to its own random-number stream. A logical task might be “bootstrap replicate 12 for cell type A” or “subsample cells from sample B.” Its stream should be determined by its identity, not by the worker that happens to execute it. This develops the subject of seed management and the earlier material on why a fixed seed does not guarantee reproducibility.

A pseudorandom generator is deterministic once its state is fixed: applying the same generator algorithm to the same initial state produces the same sequence. The stream assignment therefore has two distinct requirements:

• Reproducibility: the same task, inputs, generator, and assigned state produce the same random draws.
• Separation: different tasks receive streams designed not to repeat one another’s draws or introduce problematic dependence.

Pseudorandom streams are not literally independent random variables in the mathematical sense. Independence is a property of probability distributions; a computer generator produces deterministic values. In practice, stream-splitting methods are designed to provide streams with strong statistical properties. The strength of that design depends on the generator and the splitting method, so “use different integer seeds” is not, by itself, a universal guarantee of non-overlap or independence.

Assign Streams to Tasks, Not Workers

Suppose a pipeline has tasks \(T_1,\ldots,T_m\). Let \(K_i\) be a stable key identifying task \(T_i\), and let \(S_i\) be the generator state assigned to it. The assignment should be a deterministic function of a recorded master seed and the task key:

Here \(A\) is a documented stream allocator, such as a generator’s supported child-stream or substream mechanism. The task key should describe the work rather than its execution: for example, a replicate number, a sample identifier, and an operation name. A worker number is a poor key. If replicate 8 runs on worker 2 in one run and worker 5 in another, it should still receive the same stream.

For tasks with multiple stochastic stages, include a stable stage label or create a child stream for each stage. For example, a model-fitting task might separately assign streams to initialization and stochastic optimization. That prevents a change in the number of random draws during initialization from shifting every later draw used by optimization. The task’s inputs, cell ordering, generator family, and algorithm version also need to be controlled if identical results are expected.

The stream allocator must be selected and used according to its documented rules. A supported hierarchical splitting procedure is preferable to ad hoc arithmetic on seeds or to repeatedly seeding a generator with nearby integers. If keys are converted to seeds with a hash, use a stable, documented mapping with domain-separated keys, and recognize that a finite seed space can have collisions. A hash-based mapping is not automatically equivalent to a generator’s formal substream facility.

Why Task-Specific Streams Give Schedule-Invariant Results

The key justification is that a task’s random values no longer depend on the sequence of requests made by other tasks. Let \(F_i\) denote the deterministic computation for task \(i\), including its inputs and generator algorithm. With a task-specific initial state, its result can be written as:

Reordering tasks changes when each \(F_i\) runs, but it does not change \(\text{input}_i\) or \(S_i\). Therefore, under deterministic execution of the task, its result is unchanged. In contrast, with a single shared generator, the state supplied to a task depends on which task consumed random values first. Reordering requests can then change the task’s random values and its result.

This argument assumes that the task key and its inputs are stable, that the allocator deterministically assigns the same state to the key, and that no mutable generator is shared between tasks. It also assumes that the generator and the task’s random-number consumption behave deterministically in the relevant software environment. These conditions establish schedule invariance; they do not guarantee identical floating-point results across all software versions or hardware.

Common Failure Modes and Their Diagnostics

Parallel random-number errors can be difficult to notice because a pipeline may complete successfully and produce plausible-looking estimates. Use an explicit stream-assignment record and test the behavior of the pipeline, rather than relying only on a successful run.

• Giving every worker the same seed. Workers initialized identically can produce identical sequences. This is especially dangerous when each worker processes a different chunk: the chunks may receive repeated patterns of random choices.
• Using worker IDs as task keys. Results can change when tasks are assigned to different workers or the worker count changes. Give the random stream to the task, not to the worker.
• Sharing one mutable generator across tasks. Concurrent access can make the order of state updates depend on scheduling. Use isolated task streams rather than letting tasks draw from shared mutable state.
• Using unstable identifiers. Keys based on list position, temporary filenames, or an unordered collection can change when the pipeline is reorganized. Use canonical, persistent identifiers and a specified ordering.
• Assuming different seeds prove independence. Distinct seed values may still be a poor stream-allocation strategy for a particular generator. Check the generator documentation and use its recommended splitting approach.
• Changing task boundaries without noticing. If one task is split into several chunks, or several tasks are combined, the mapping from keys to random draws may change. Define logical task granularity deliberately and record it.

Useful diagnostics include verifying that every logical task key is unique, recording the generator family and allocator, and comparing outputs after changing task order and worker count. Inspecting initial values from each stream can reveal obvious duplication, but distinct initial values do not prove good stream separation. Likewise, passing a few schedule-invariance tests does not establish theoretical independence.

Choosing Among Stream-Management Approaches

For cell subsampling, define a stable task key for the dataset, cell group, and sampling purpose, and keep the cell ordering canonical. For bootstrap or other resampling procedures, replicate identifiers are natural keys: replicate 1 should retain its assigned stream if more replicates are added later. Avoid defining replicate streams by taking successive portions of a shared stream when the goal is to keep existing replicates unchanged as the pipeline expands.

Task-level streams improve control, but they do not remove every source of variation. Results may still change if the input cells change order, the sampling algorithm changes, the generator implementation changes, or a task consumes a different number of random values. Record the master seed, generator and splitting method, task-key scheme, software versions, inputs, and task granularity. Cross-version bit-for-bit identity should only be expected when the relevant software explicitly guarantees it.