Deterministic Market Laboratory

A correctness-first electronic-exchange laboratory in Rust.

The project treats matching as a deterministic state machine driven by one strictly ordered command journal. Around that core it models replay, snapshots, idempotent retries, synchronous primary/replica execution, sequenced market data, unreliable delivery, explicit leader fencing, virtual time, fault injection, and counterexample minimization.

This is deliberately a laboratory, not a production exchange or a latency claim. It is exposed as a Rust library plus a reproducible demonstration and inspection CLI. There is no socket gateway, FIX session, distributed consensus protocol, or storage service in this repository. The primary/replica orchestrator is an in-memory crash model; the checksummed file journal and atomic snapshot writer are separate persistence primitives. That boundary is part of the design, not hidden behind marketing language.

Why this matters across industries

Deterministic replay, idempotent retries, explicit leader fencing, and fault-injected counterexample minimization are the exact correctness properties that matter for any auditable, reproducible transactional system — directly relevant to finance/banking (trading-system and settlement infrastructure needs to reconstruct and prove what happened, not just process fast), but the discipline generalizes well beyond it: tech infrastructure broadly needs the same primary/replica determinism guarantees, and industrial control systems demand the same reproducibility and fault-injection rigor when a wrong decision has physical consequences. The value here isn't the exchange domain specifically — it's demonstrating that a stated correctness property is actually tested adversarially, not just asserted.

What is implemented

• A single-threaded price-time-priority limit-order book with partial fills, GTC and IOC orders, cancel, replace, and mass cancel.
• Integer ticks and checked fixed-point arithmetic; no floating-point values in matching or accounting.
• Synchronous pre-trade limits for order size, open notional, and worst-case position, plus deterministic position, cash, and FIFO realized-P&L state.
• Participant-scoped idempotency keys and a strictly contiguous global input sequence.
• Stable output identities derived from (global_sequence, event_ordinal).
• A versioned, checksummed append-only file-journal format with explicit torn-tail detection and repair.
• Canonical state encoding, incremental BLAKE3 semantic fingerprints, immutable snapshots, full replay, and snapshot-plus-tail recovery.
• An in-memory primary/replica model that acknowledges only after both engines agree, with crashpoints at meaningful commit boundaries.
• A sequenced market-data projection with checksums, bounded retransmission, duplicate suppression, gap detection, snapshot fallback, and epoch fencing.
• A deterministic virtual scheduler/network supporting loss, duplication, delay, reordering, and corruption.
• Executable structural, accounting, output-identity, and replica-equivalence invariants, property-generated command sequences, and deterministic scenario shrinking.
• A feature-gated bug-zoo with isolated symbolic mutations for volatile-only dedupe and reversed FIFO, each reduced to a minimal counterexample.
• A CLI that produces machine-readable demo/measurement output and validates journal or snapshot files supplied by callers.

Guarantees, stated precisely

For a fixed semantics version, immutable configuration, and contiguous journal, replay produces the same ordered outputs, canonical state bytes, and semantic state fingerprint. An exact retry of a durable (participant_id, client_sequence) returns the original transition and does not append a second command. Consequently, the model provides exactly-once logical effects, even though requests and market-data packets may be delivered at least once.

Those words do not imply exactly-once transport. Progress still requires retry, retransmission, or snapshot installation. Nor does this project implement consensus: after a network partition, promotion is rejected until an external actor explicitly fences the old primary. See the correctness contract and the failure model for assumptions and limits.

Data path

flowchart LR
    C["CommandEnvelope<br/>participant + client_seq"] --> S["Sequencer"]
    S --> J["Authoritative ordered journal"]
    J --> P["Primary Engine"]
    J --> R["Replica Engine"]
    P --> X["Transition comparison<br/>and commit watermark"]
    R --> X
    X --> F["Sequenced market-data publisher"]
    F --> N["Unreliable virtual network"]
    N --> U["Ordered, idempotent consumer"]

Loading

The engine itself has no I/O, clock, randomness, threads, or process-global state. All ordering and fault decisions are explicit inputs.

Build and verify

The crate declares Rust 1.93 and edition 2024. CI pins Rust 1.93.1 and runs the full validation matrix on Linux and Windows.

cargo fmt --all -- --check
cargo clippy --all-targets --all-features -- -D warnings
cargo test --all-targets --all-features
cargo test --doc

On PowerShell, scripts/verify.ps1 runs the same local gate.

Reproducible demonstrations

Run the integrated crash/retry, replica-equivalence, replay, snapshot-recovery, and market-data repair proof:

cargo run --release -- demo --events 100k --seed 42 --replays 3

The command prints JSON with all compared digests, the crash/snapshot positions, network duplicate/repair counts, and an explicit measurement scope. Add --report PATH to create a new report file; an existing file is never overwritten.

The same proof can be run over one million commands with --events 1m; the smaller default keeps an interactive review comfortably short.

Run the materialized fault scenario on its own:

cargo run --release -- fault-demo

Generate a concrete fault schedule, persist every random choice, then replay that exact JSON scenario without consulting a random generator:

cargo run --release -- fault run --steps 100 --seed 42 --save scenario.json
cargo run --release -- fault reproduce scenario.json

Both runs print the scenario digest and a terminal report containing network watermarks, pending work, crashpoints, trade exposure, logical duplicates, and convergence. PASS requires both safety and a fully caught-up quiescent state, making failures portable and directly reproducible.

The deliberately faulty models are compiled only when requested and never switch the production engine's behavior:

cargo run --features bug-zoo -- bug-demo dedupe --seed 42
cargo run --features bug-zoo -- bug-demo fifo --seed 42

For journal and snapshot files created through the library, the CLI also exposes inspect LOG, replay LOG, and snapshot verify SNAPSHOT. inspect is configuration-agnostic: it validates the framing and current semantics, then reports the configuration digest recorded in the journal header. By contrast, replay and snapshot verify currently use EngineConfig::default() and reject artifacts created with any other configuration. Use the library APIs with the matching EngineConfig for non-default lineages. Run cargo run -- --help for the complete command surface.

Run the Criterion benchmark target separately:

cargo bench --bench matching

Benchmark output is intentionally not summarized as a headline number here. Machine details, CPU isolation, workload shape, distributions, and raw Criterion artifacts are required before quoting a result; the protocol is in docs/benchmark-methodology.md.

Explicit resource budgets

Resource exhaustion is part of the deterministic contract rather than an implicit allocator failure:

• one matching or mass-cancel command may affect at most 65,536 resting orders;
• the materializing journal adapter accepts at most 128 MiB and 2,000,000 records per segment;
• snapshot files are capped at 256 MiB and decoding shares a conservative 256 MiB weighted collection-memory budget;
• one invariant pass returns at most 1,024 evidence rows, with a final validation.truncated row when more failures exist;
• the CLI accepts fault-scenario files up to 16 MiB and executes at most 250,000 materialized steps; demo and sampler corpora are capped at 1,000,000 commands.

These are laboratory adapter limits, not claims about an exchange-wide order capacity. A larger deployment needs journal segmentation, checkpoint rotation, streaming recovery, admission control, and measured memory sizing.

Minimal engine example

use deterministic_market_lab::{Engine, EngineConfig};
use deterministic_market_lab::types::{
    ClientSeq, Command, CommandEnvelope, GlobalSeq, InstrumentId, OrderId,
    ParticipantId, Price, Quantity, SequencedCommand, Side, TimeInForce,
};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let mut engine = Engine::new(EngineConfig::default());
    let input = SequencedCommand {
        global_seq: GlobalSeq::new(1),
        envelope: CommandEnvelope {
            participant: ParticipantId::new(7),
            client_seq: ClientSeq::new(1),
            command: Command::NewOrder {
                order_id: OrderId::new(42),
                instrument: InstrumentId::new(1),
                side: Side::Buy,
                price: Price::from_ticks(10_000)?,
                quantity: Quantity::new(25)?,
                time_in_force: TimeInForce::GoodTillCancel,
            },
        },
    };

    let transition = engine.apply(&input)?;
    assert_eq!(transition.global_seq, GlobalSeq::new(1));
    assert_eq!(engine.last_seq(), GlobalSeq::new(1));
    Ok(())
}

Production-facing callers normally use ReplicatedExchange::submit rather than assigning GlobalSeq directly. The direct example exposes the deterministic state-machine boundary.

Repository map

Area	Responsibility
src/engine.rs, src/book.rs	Matching transition and price-time book
src/risk.rs	Pre-trade reservations and post-trade accounting
src/codec.rs, src/types.rs	Canonical wire/domain representation
src/journal.rs	Versioned checksummed file journal
src/snapshot.rs	Canonical snapshots, replay, and recovery
src/replication.rs	Sequencing, retry dedupe, crashpoints, promotion
src/market_data.rs	Publisher, retention, gap repair, consumer view
src/fault.rs, src/invariant.rs	Virtual faults, reports, shrinking, checks
src/bug_zoo.rs	Feature-gated deliberate symbolic mutations
src/main.rs	Demo, benchmark, replay, and inspection CLI
tests/properties.rs	Generated replay, invariant, retry, and recovery tests
tests/differential.rs	Independent linear-book oracle and generated comparison
tests/conformance.rs	Cross-platform golden journal, outputs, and state vector
benches/matching.rs	Criterion benchmark target
scripts/*.ps1	Reproducible verify, demo, and benchmark entrypoints
.github/workflows/ci.yml	Locked Linux/Windows validation matrix

Design documents

• Architecture
• Correctness contract and evidence
• Failure model and recovery matrix
• Benchmark methodology

Non-goals

The current repository does not claim real-network behavior, Byzantine fault tolerance, multi-node quorum durability, automatic leader election, linearizable configuration changes, authentication, authorization, regulatory completeness, or production observability. It also makes no zero-allocation or sub-microsecond latency claim. Those would require different evidence and, in several cases, a larger system boundary.