timewarp

# 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:

| Time Warp concept    | BEAM primitive                                          |
|----------------------|---------------------------------------------------------|
| Logical process      | Process (GenServer)                                     |
| Event / anti-message | Message (`%TimeWarp.Event{}`); anti-message is `sign: :neg` |
| Annihilation         | Selective-receive match on the twin                     |
| State snapshot       | Immutable term reference (structural sharing)           |
| Rollback isolation   | Per-process heap — one rollback touches no other memory |
| Fossil collection    | Per-process GC, triggered on GVT advance                |
| Distribution         | Location-transparent — the straggler protocol is the same local or remote |

## 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.

```elixir
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`:

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

Documentation is published at [hexdocs.pm/timewarp](https://hexdocs.pm/timewarp).