TimeWarp

Optimistic parallel discrete-event simulation (PDES) on the BEAM. Logical processes execute events speculatively — never blocking to confirm that an earlier event might still arrive — and roll back automatically when causality is violated. The engine tracks causal dependencies through the message graph and propagates each correction itself, so a model implements only pure event handling and never writes rollback logic.

It implements Jefferson's Time Warp (TOPLAS, 1985) with Mattern's distributed Global Virtual Time (JPDC, 1993), mapping each mechanism onto a BEAM primitive.

When not to use it

Optimistic PDES has a narrow sweet spot. Three workload classes are poor fits, and the engine will underperform or thrash on them:

• Workloads that partition cleanly. If the problem shards into partitions with no causal dependencies crossing between them, plain data-parallel execution — one shard per core, no synchronization — is simpler and faster. This engine earns its place only where dependencies cross partitions dynamically.
• High-conflict, all-to-all dependency graphs. When any logical process can causally affect any other, stragglers set off rollback cascades whose rate climbs steeply — near-exponentially — with coupling, and speculation spends more work undoing than doing. A tight optimism window bounds the storm, but only by throttling parallelism toward conservative execution; at that point the workload simply is not a fit for optimism, and a smaller window is not a fix.
• Workloads dominated by low-latency irreversible external effects. Irreversible effects are held until Global Virtual Time (GVT) passes them — committed once, never revoked. If an application's value is emitting such effects with low latency, the GVT commit floor bounds that latency and the quarantine becomes the bottleneck.

One further boundary the engine's own measurements draw sharply: optimism buys correctness under out-of-order input for free, but it buys nothing by performing per-event computation speculatively. Deferring expensive per-event work to the commit stage (past GVT) makes a rollback nearly free — a list truncation rather than a re-computation — while computing eagerly pays the full cost again on every rollback. Where per-event work is non-trivial, defer it; do not fold it eagerly.

Why the BEAM

In C/MPI Time Warp implementations, state saving is the dominant engineering cost and the dominant research topic: mutable process state is deep-copied on every event, mitigated by incremental state saving, periodic checkpointing, and reverse computation. On the BEAM that cost largely disappears. Process state is an immutable term; a snapshot is a retained reference; persistent data structures share structure, so a snapshot taken after a mutation costs O(changed), not O(state), and a rollback restores a reference. The decades-long PDES research program on state saving is replaced by a language feature.

The other Time Warp concepts map directly onto BEAM primitives:

Status

Research- and engineering-quality, not production software. Correctness rests on a sequential-equivalence oracle: every optimistic run is asserted to produce byte-identical committed results to a single-threaded, in-timestamp-order execution of the same model — including under adversarial out-of-order arrival and across two nodes under a FIFO-preserving inter-node delay fuzzer. Property tests and an exhaustive small-scale model check exercise the GVT algorithm, rollback, annihilation, and output commit.

The container-terminal application that motivated the design was never built. The calibration data it would have required was unavailable, and an uncalibrated model was judged worse than none — so that work was set aside rather than shipped. Every example in this library is synthetic; nothing here models, or claims to model, any real terminal.

Example

PHOLD is the standard PDES stress workload: a fixed population of events bounces between logical processes to random targets at random future times. This run terminates in a few seconds and does real rollback work.

ids = [:a, :b, :c, :d]
lps = Map.new(ids, fn id -> {id, %{ids: ids, max_delay: 10}} end)

{:ok, sim} =
  TimeWarp.start_run(
    model: TimeWarp.Examples.PHOLD,
    lps: lps,
    seed: 7,
    until: {:vtime, 1_000},
    init_events: for(i <- 0..7, do: {Enum.at(ids, rem(i, 4)), i, :ping}),
    # PHOLD is all-to-all and does not bound on its own: raising `until` WITHOUT a
    # window grows retained state without limit. The window caps how far any process
    # speculates past GVT.
    time_window: {:vtime, 20}
  )

{:done, _info} = TimeWarp.await(sim)
report = TimeWarp.report(sim)

IO.inspect(report.totals)
# => %{rollbacks: 1114, antimsgs_sent: 1745, events_processed: 3195}   # <- yours WILL differ
#
# Committed results are deterministic; these counts are NOT. They depend on the parallel
# schedule, so every run reports different rollback and anti-message totals — that
# divergence is the speculation itself.

A model implements the TimeWarp.Model behaviour: init/1, a pure handle_event/3 (state transition plus emitted events, no side effects), and an optional commit/2 for irreversible effects. handle_event/3 purity is the one contract whose violation corrupts results silently — run with check_purity: true during development to catch it.

The TimeWarp.Examples modules run two unrelated workloads on the same unmodified engine: the PHOLD benchmark family (PHOLD, and DecayingPHOLD which terminates by construction) and a keyed-stream windowed aggregator (KeyedWindow / BufferedWindow, built two ways — eager and buffered). Different domains, zero engine changes.

Running the tests

mix test

The suite includes a sequential-equivalence property test, an exhaustive small-scale model check of the GVT algorithm, lazy-cancellation and time-window characterizations, and distributed correctness across two nodes.

Installation

Add timewarp to the dependencies in mix.exs:

def deps do
  [{:timewarp, "~> 0.1.0"}]
end

Documentation is published at hexdocs.pm/timewarp.