Deterministic Execution as a System Property

Scope

An execution is deterministic when identical inputs, under a fixed execution model, produce identical state transitions and identical observable results.

Logging records selected observations. It does not constrain the nondeterministic sources that produced them.

This note distinguishes three claims that are often collapsed:

Bitwise determinism. Identical bit patterns for intermediate and final state.

Numerical equivalence. Agreement within a stated tolerance under a stated rounding and reduction model.

Semantic equivalence. Agreement on externally meaningful outcomes, allowing internal divergence that does not affect the stated interface.

Systems often claim “determinism” while meaning only one of these. The distinction matters for replay and audit, and whenever parties must agree on what a computation did.

Sources of nondeterminism

Nondeterminism enters through clocks, concurrency interleavings, floating-point environments, external services, randomness, and mutable shared state. If any of these remain ambient rather than named inputs, the execution model is incomplete.

A system that claims deterministic execution must either eliminate a source or admit it as part of the input. Partial elimination without admission produces apparent determinism until an unmodeled source varies.

Execution boundary

Replay is meaningful only relative to a stated boundary. Outside that boundary, the environment is not under the model’s control.

External input
→ Canonical representation
→ Versioned execution context
→ State transition
→ Invariant validation
→ Commit
→ Provenance record

The boundary decides which of these steps are inside the model. Logging selected outputs does not move the boundary; it records a projection of what crossed it.

Two runs may emit identical outputs while taking different internal paths. If those paths are correctness-relevant, output agreement is not agreement on the computation.

Idempotency

Determinism constrains what happens on a single run under fixed inputs. Idempotency constrains what happens when an operation is applied more than once.

An operation can be deterministic and still non-idempotent. An operation can be idempotent under a stated equivalence without being bitwise deterministic. Specifying both requires stating the equivalence under which repeated application yields a unique state.

Executable invariants

An invariant that exists only in documentation does not constrain admission of invalid state. Where determinism is required, invariant checks belong at the boundary where state would otherwise be committed.

Validation after the fact can detect a violation. Validation before commit can refuse it. Those are different control points.

Numerical equivalence

Floating-point reduction order, library versions, and parallel schedules can change bit-level results without changing semantic intent. When bitwise reproducibility is required, these factors belong in the versioned execution context. When only numerical equivalence is required, the tolerance and aggregation model must be stated; otherwise “agreement” is undefined.

Provenance

A provenance record links a committed result to the inputs, execution context, and transitions that produced it. Without that link, an audit trail describes outcomes while leaving the causal chain underdetermined.

Provenance does not establish determinism by itself.

Limitations

Deterministic execution increases system complexity. It constrains scheduler choice, library upgrades, and integration with nondeterministic external services. Where observational or semantic equivalence is sufficient, bitwise reproducibility may be unnecessary.

Determinism does not imply correctness. A deterministic system can compute the wrong result.

Open Questions

• Which system boundaries must be captured for replay to remain meaningful?
• When is semantic equivalence sufficient in place of bitwise reproducibility?
• How should replay semantics treat irreversible external effects?
• Which sources of nondeterminism should be eliminated, and which should be recorded?