TLA+ Specification Testing: Model Checking Distributed Systems Before You Ship

TLA+ Specification Testing: Model Checking Distributed Systems Before You Ship

Distributed systems fail in ways that are nearly impossible to reproduce in tests. A Raft leader election bug might only surface after a specific sequence of 12 network partitions. A two-phase commit deadlock requires two coordinators to crash within milliseconds of each other. By the time you see these bugs in production, you've already lost data or availability.

TLA+ (Temporal Logic of Actions) is a formal specification language for describing and verifying distributed system behavior. The TLC model checker exhaustively explores the state space of your specification, finding violations of safety and liveness properties that integration tests would never catch. This post covers how to write TLA+ specs, check them with TLC, and use the results to build more reliable systems.

Why TLA+ Instead of Tests?

Unit and integration tests check specific execution paths. TLC checks all execution paths (up to a configurable depth). For a distributed system with 5 nodes, 3 failure modes, and message reordering, the number of possible interleavings is astronomical. TLC doesn't sample — it exhausts the state space.

Leslie Lamport and his team at AWS used TLA+ to find 10 bugs in Amazon's internal systems, including a critical flaw in a Dynamo-like replication protocol. Engineers at Azure, MongoDB, and PlanGrid have published similar results. The cost is upfront specification work; the payoff is confidence that your protocol is correct before you write a single line of implementation.

Setting Up TLA+ Toolbox

The primary IDE is the TLA+ Toolbox, but VS Code with the TLA+ extension is increasingly popular:

# VS Code extension
code --install-extension alygin.vscode-tlaplus

# Or download TLA+ Toolbox
# https://github.com/tlaplus/tlaplus/releases

TLC ships with the Toolbox. For CI integration:

# Download TLC jar
wget https://github.com/tlaplus/tlaplus/releases/download/v1.8.0/tla2tools.jar

# Run model checker
java -jar tla2tools.jar -workers auto MySpec.tla

Your First TLA+ Spec: A Simple Lock

Start with something concrete. A mutual exclusion lock:

---- MODULE SimpleLock ----
EXTENDS Naturals, TLC

CONSTANTS Threads

VARIABLES held_by, waiting

TypeInvariant ==
    /\ held_by \in Threads \union {NULL}
    /\ waiting \subseteq Threads

Init ==
    /\ held_by = NULL
    /\ waiting = {}

Acquire(t) ==
    /\ held_by = NULL
    /\ held_by' = t
    /\ waiting' = waiting \ {t}

Release(t) ==
    /\ held_by = t
    /\ held_by' = NULL
    /\ waiting' = waiting

Request(t) ==
    /\ held_by # t
    /\ waiting' = waiting \union {t}
    /\ UNCHANGED held_by

Next ==
    \E t \in Threads:
        \/ Acquire(t)
        \/ Release(t)
        \/ Request(t)

Spec == Init /\ [][Next]_<<held_by, waiting>>

\* Safety: at most one thread holds the lock
MutualExclusion ==
    \A t1, t2 \in Threads:
        (held_by = t1 /\ held_by = t2) => t1 = t2

====

The MutualExclusion invariant is what TLC checks — it must hold in every reachable state. If it ever fails, TLC produces a counterexample showing the exact sequence of actions that violated it.

Model Configuration

TLA+ specs are parameterized. The model tells TLC what values to use:

\* SimpleLock.cfg
CONSTANTS
    Threads = {t1, t2, t3}
    NULL = NULL

SPECIFICATION Spec

INVARIANTS
    TypeInvariant
    MutualExclusion

Run TLC:

java -jar tla2tools.jar -config SimpleLock.cfg SimpleLock.tla

Output on success:

Model checking completed. No error has been found.
  Estimates of the probability that TLC did not check all reachable states
  because two distinct states had the same fingerprint:
  calculated (max): val = 5.9E-18
  based on the actual fingerprint usage in the last 1h: val = 2.2E-18

Specifying Distributed Consensus

Here's where TLA+ pays off. A simplified Raft leader election:

---- MODULE RaftElection ----
EXTENDS Naturals, FiniteSets, TLC

CONSTANTS Servers, Quorum

VARIABLES
    currentTerm,    \* term[s] = current term of server s
    state,          \* state[s] \in {Follower, Candidate, Leader}
    votedFor,       \* votedFor[s] = server s voted for, or NULL
    votesGranted    \* votesGranted[s] = set of servers that voted for s

States == {"Follower", "Candidate", "Leader"}

TypeOK ==
    /\ currentTerm \in [Servers -> Nat]
    /\ state \in [Servers -> States]
    /\ votedFor \in [Servers -> Servers \union {NULL}]
    /\ votesGranted \in [Servers -> SUBSET Servers]

Init ==
    /\ currentTerm = [s \in Servers |-> 0]
    /\ state = [s \in Servers |-> "Follower"]
    /\ votedFor = [s \in Servers |-> NULL]
    /\ votesGranted = [s \in Servers |-> {}]

RequestVote(s, t) ==
    \* s requests vote from t
    /\ state[s] = "Candidate"
    /\ votedFor[t] \in {NULL, s}
    /\ currentTerm[t] <= currentTerm[s]
    /\ votesGranted' = [votesGranted EXCEPT ![s] = votesGranted[s] \union {t}]
    /\ votedFor' = [votedFor EXCEPT ![t] = s]
    /\ UNCHANGED <<currentTerm, state>>

BecomeLeader(s) ==
    /\ state[s] = "Candidate"
    /\ votesGranted[s] \in Quorum
    /\ state' = [state EXCEPT ![s] = "Leader"]
    /\ UNCHANGED <<currentTerm, votedFor, votesGranted>>

StartElection(s) ==
    /\ state[s] = "Follower"
    /\ currentTerm' = [currentTerm EXCEPT ![s] = currentTerm[s] + 1]
    /\ state' = [state EXCEPT ![s] = "Candidate"]
    /\ votesGranted' = [votesGranted EXCEPT ![s] = {s}]  \* votes for itself
    /\ votedFor' = [votedFor EXCEPT ![s] = s]

Next ==
    \E s, t \in Servers:
        \/ RequestVote(s, t)
        \/ BecomeLeader(s)
        \/ StartElection(s)

Spec == Init /\ [][Next]_<<currentTerm, state, votedFor, votesGranted>>

\* Safety: at most one leader per term
AtMostOneLeaderPerTerm ==
    \A s1, s2 \in Servers:
        (/\ state[s1] = "Leader"
         /\ state[s2] = "Leader"
         /\ currentTerm[s1] = currentTerm[s2])
        => s1 = s2

====

When TLC checks AtMostOneLeaderPerTerm, it's verifying something that no unit test could: that regardless of message ordering, network partitions, or concurrent elections, you never get two leaders in the same term.

Liveness Properties with Temporal Logic

Safety properties are "nothing bad happens." Liveness properties are "something good eventually happens." In TLA+, liveness uses temporal operators:

  • <>P — P is eventually true
  • []P — P is always true
  • []<>P — P is true infinitely often
  • <>[]P — P is eventually always true
\* Liveness: a candidate with a quorum eventually becomes leader
EventualLeader ==
    \A s \in Servers:
        (state[s] = "Candidate" /\ votesGranted[s] \in Quorum)
        ~> (state[s] = "Leader")

The ~> (leads-to) operator means: whenever the left side is true, eventually the right side becomes true.

Add liveness to your model config:

PROPERTIES
    AtMostOneLeaderPerTerm
    EventualLeader

Liveness checking requires fairness assumptions. Weak fairness (WF_vars(A)) says an action that is continuously enabled will eventually occur. Add it to your spec:

Spec == Init 
    /\ [][Next]_vars 
    /\ WF_vars(Next)

Symmetry Reduction for Performance

Checking all 3-server interleavings with distinct server identifiers means TLC explores many equivalent states. Symmetry sets tell TLC that servers are interchangeable:

\* In model config
SYMMETRY Permutations(Servers)

This can reduce state space by N! where N is the symmetry set size. For 5 servers, that's 120x fewer states to explore.

Using TLAPS for Machine-Checked Proofs

TLC is bounded model checking — it checks up to a depth limit. For unbounded proofs, TLAPS (TLA+ Proof System) lets you write Lamport-style proofs:

THEOREM AtMostOneLeaderPerTerm
<1>1. Init => AtMostOneLeaderPerTerm
  BY DEF Init, AtMostOneLeaderPerTerm
<1>2. ASSUME AtMostOneLeaderPerTerm /\ [Next]_vars
      PROVE AtMostOneLeaderPerTerm'
  <2>1. CASE Next
    <3>1. CASE \E s, t \in Servers: RequestVote(s, t)
      BY <3>1 DEF RequestVote, AtMostOneLeaderPerTerm
    <3>2. CASE \E s \in Servers: BecomeLeader(s)
      BY <3>2 DEF BecomeLeader, AtMostOneLeaderPerTerm
    <3>3. QED BY <3>1, <3>2 DEF Next
  <2>2. CASE vars' = vars
    BY <2>2 DEF AtMostOneLeaderPerTerm
  <2>3. QED BY <2>1, <2>2
<1>3. QED BY <1>1, <1>2, PTL

TLAPS integrates with Zenon and Isabelle backends for automated proof checking.

TLA+ in CI Pipelines

Run TLC automatically on spec changes:

# .github/workflows/tla-check.yaml
name: TLA+ Model Check
on:
  push:
    paths:
      - 'specs/**/*.tla'
      - 'specs/**/*.cfg'

jobs:
  tlacheck:
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v4
      - name: Download TLC
        run: wget -q https://github.com/tlaplus/tlaplus/releases/download/v1.8.0/tla2tools.jar
      - name: Check all specs
        run: |
          for cfg in specs/**/*.cfg; do
            spec="${cfg%.cfg}.tla"
            echo "Checking $spec..."
            java -jar tla2tools.jar -workers auto -config "$cfg" "$spec"
          done

Reading Counterexamples

When TLC finds a violation, it prints a counterexample trace:

Error: Invariant AtMostOneLeaderPerTerm is violated.
The behavior up to this point is:
State 1: <Initial predicate>
/\ currentTerm = (s1 :> 0 @@ s2 :> 0 @@ s3 :> 0)
/\ state = (s1 :> Follower @@ s2 :> Follower @@ s3 :> Follower)

State 2: <Action StartElection line 47>
/\ currentTerm = (s1 :> 1 @@ s2 :> 0 @@ s3 :> 0)
/\ state = (s1 :> Candidate @@ s2 :> Follower @@ s3 :> Follower)
...
State 8: Two leaders in term 1

Read these traces carefully. They tell you the exact sequence of actions that led to the bug. This is often enough to identify the fix in your implementation even before touching the spec.

Practical Workflow

The TLA+ workflow that works in practice:

  1. Specify the happy path first. Get Init and the core actions right before adding failure modes.
  2. Add invariants incrementally. Start with TypeOK (type correctness), then add safety properties.
  3. Start small. 2-3 servers, 2-3 terms. Expand only if the small model passes.
  4. Use constants for symmetry. Replace specific values with symbolic constants you can tune.
  5. Match the spec to the implementation. The spec should describe what the code does, not an idealized version.

TLA+ doesn't replace testing — it complements it. TLC finds protocol bugs; your integration tests find implementation bugs. The combination gives you defense in depth that neither approach provides alone.

Read more

Start now free