TLA+ Examples

This is a repository of TLA⁺ specifications and models covering applications in a variety of fields. It serves as:

• a comprehensive example library demonstrating how to specify an algorithm in TLA⁺
• a diverse corpus facilitating development & testing of TLA⁺ language tools
• a collection of case studies in the application of formal specification in TLA⁺

All TLA⁺ specs can be found in the specifications directory. To contribute a spec of your own, see CONTRIBUTING.md.

The table below lists all specs and indicates whether a spec is beginner-friendly, includes an additional PlusCal variant (✔), or uses PlusCal exclusively. Additionally, the table specifies which verification tool—TLC, Apalache, or TLAPS—can be used to verify each specification.

Space contraints limit the information displayed in the table; detailed spec metadata can be found in the manifest.json files in each specification's directory. You can search these files for examples exhibiting a number of features, either using the GitHub repository search or locally with the command ls specifications/*/manifest.json | xargs grep -l $keyword, where $keyword can be a value like:

• pluscal, proof, or action composition (the \cdot operator)
• Specs intended for trace generation (generate), simulate, or checked symbolically with Apalache (symbolic)
• Models failing in interesting ways, like deadlock failure, safety failure, liveness failure, or assumption failure

It is also helpful to consult model files using specific TLC features. For this, run ls specifications/*/*.cfg | xargs grep -l $keyword, where $keyword can be a feature like SYMMETRY, VIEW, ALIAS, CONSTRAINT, or DEADLOCK.

Validated Examples Included Here

Here is a list of specs included in this repository which are validated by the CI, with links to the relevant directory and flags for various features:

Name	Author(s)	Beginner	TLAPS Proof	PlusCal	TLC Model	Apalache
Teaching Concurrency	Leslie Lamport	✔	✔	✔	✔
Loop Invariance	Leslie Lamport	✔	✔	✔	✔
Learn TLA⁺ Proofs	Andrew Helwer	✔	✔	✔	✔
Boyer-Moore Majority Vote	Stephan Merz	✔	✔		✔
Proof x+x is Even	Martin Riener	✔	✔		✔
The N-Queens Puzzle	Stephan Merz	✔		✔	✔
The Dining Philosophers Problem	Jeff Hemphill	✔		✔	✔	✔
The Car Talk Puzzle	Leslie Lamport	✔			✔
The Die Hard Problem	Leslie Lamport	✔			✔	✔
The Prisoners & Switches Puzzle	Leslie Lamport	✔			✔
The Prisoners & Switch Puzzle	Florian Schanda	✔			✔
Specs from Specifying Systems	Leslie Lamport	✔			✔	✔
The Tower of Hanoi Puzzle	Markus Kuppe, Alexander Niederbühl	✔			✔
Missionaries and Cannibals	Leslie Lamport	✔			✔	✔
Stone Scale Puzzle	Leslie Lamport	✔			✔
The Coffee Can Bean Problem	Andrew Helwer	✔			✔	✔
EWD687a: Detecting Termination in Distributed Computations	Stephan Merz, Leslie Lamport, Markus Kuppe	✔		(✔)	✔
The Moving Cat Puzzle	Florian Schanda	✔			✔	✔
The Boulangerie Algorithm	Leslie Lamport, Stephan Merz		✔	✔	✔
Misra Reachability Algorithm	Leslie Lamport		✔	✔	✔	✔
Byzantizing Paxos by Refinement	Leslie Lamport		✔	✔	✔
Barrier Synchronization	Jarod Differdange		✔	✔	✔	✔
Peterson Lock Refinement With Auxiliary Variables	Jarod Differdange		✔	✔	✔
EWD840: Termination Detection in a Ring	Stephan Merz		✔		✔	✔
EWD998: Termination Detection in a Ring with Asynchronous Message Delivery	Stephan Merz, Markus Kuppe		✔	(✔)	✔
The Paxos Protocol	Leslie Lamport		(✔)		✔
Asynchronous Reliable Broadcast	Thanh Hai Tran, Igor Konnov, Josef Widder		✔		✔
Distributed Mutual Exclusion	Stephan Merz		✔		✔	✔
Two-Phase Handshaking	Leslie Lamport, Stephan Merz		✔		✔
Paxos (How to Win a Turing Award)	Leslie Lamport		(✔)		✔
Finitizing Monotonic Systems	Andrew Helwer, Stephan Merz, Markus Kuppe		✔		✔	✔
Dijkstra's Mutual Exclusion Algorithm	Leslie Lamport			✔	✔
The Echo Algorithm	Stephan Merz			✔	✔
The TLC Safety Checking Algorithm	Markus Kuppe			✔	✔
Transaction Commit Models	Leslie Lamport, Jim Gray, Murat Demirbas			✔	✔	✔
The Slush Protocol	Andrew Helwer			✔	✔
Minimal Circular Substring	Andrew Helwer			✔	✔
Snapshot Key-Value Store	Andrew Helwer, Murat Demirbas			✔	✔
Chang-Roberts Algorithm for Leader Election in a Ring	Stephan Merz			✔	✔	✔
MultiPaxos in SMR-Style	Guanzhou Hu			✔	✔
Einstein's Riddle	Isaac DeFrain, Giuliano Losa					✔
Resource Allocator	Stephan Merz				✔
Transitive Closure	Stephan Merz				✔
Atomic Commitment Protocol	Stephan Merz				✔	✔
SWMR Shared Memory Disk Paxos	Leslie Lamport, Giuliano Losa				✔
Span Tree Exercise	Leslie Lamport				✔	✔
The Knuth-Yao Method	Ron Pressler, Markus Kuppe				✔
Huang's Algorithm	Markus Kuppe				✔
EWD 426: Token Stabilization	Murat Demirbas, Markus Kuppe				✔	✔
Sliding Block Puzzle	Mariusz Ryndzionek				✔
Single-Lane Bridge Problem	Younes Akhouayri				✔
Software-Defined Perimeter	Luming Dong, Zhi Niu				✔
Simplified Fast Paxos	Lim Ngian Xin Terry, Gaurav Gandhi				✔
Checkpoint Coordination	Andrew Helwer				✔
Multi-Car Elevator System	Andrew Helwer				✔
Nano Blockchain Protocol	Andrew Helwer				✔
The Readers-Writers Problem	Isaac DeFrain				✔	✔
Asynchronous Byzantine Consensus	Thanh Hai Tran, Igor Konnov, Josef Widder				✔
Folklore Reliable Broadcast	Thanh Hai Tran, Igor Konnov, Josef Widder				✔	✔
The Bosco Byzantine Consensus Algorithm	Thanh Hai Tran, Igor Konnov, Josef Widder				✔	✔
Consensus in One Communication Step	Thanh Hai Tran, Igor Konnov, Josef Widder				✔	✔
One-Step Consensus with Zero-Degradation	Thanh Hai Tran, Igor Konnov, Josef Widder				✔
Failure Detector	Thanh Hai Tran, Igor Konnov, Josef Widder				✔
Asynchronous Non-Blocking Atomic Commit	Thanh Hai Tran, Igor Konnov, Josef Widder				✔
Asynchronous Non-Blocking Atomic Commitment with Failure Detectors	Thanh Hai Tran, Igor Konnov, Josef Widder				✔	✔
Spanning Tree Broadcast Algorithm	Thanh Hai Tran, Igor Konnov, Josef Widder				✔	✔
The Cigarette Smokers Problem	Mariusz Ryndzionek				✔	✔
Conway's Game of Life	Mariusz Ryndzionek				✔
Chameneos, a Concurrency Game	Mariusz Ryndzionek				✔
PCR Testing for Snippets of DNA	Martin Harrison				✔	✔
RFC 3506: Voucher Transaction System	Santhosh Raju, Cherry G. Mathew, Fransisca Andriani				✔
Yo-Yo Leader Election	Ludovic Yvoz, Stephan Merz				✔
TCP as defined in RFC 9293	Markus Kuppe				✔	✔
B-trees	Lorin Hochstein				✔
TLA⁺ Level Checking	Leslie Lamport
Condition-Based Consensus	Thanh Hai Tran, Igor Konnov, Josef Widder
Buffered Random Access File	Calvin Loncaric				✔
Disruptor	Nicholas Schultz-Møller				✔	✔
DAG-based Consensus	Giuliano Losa			✔	✔

Other Examples

Here is a list of specs stored in locations outside this repository or not validated by the CI, such as submodules. Since these specs are not covered by CI testing it is possible they contain errors, the reported details are incorrect, or they are no longer available. Ideally these will be moved into this repo over time.

Spec	Details	Author(s)	Beginner	TLAPS Proof	TLC Model	PlusCal	Apalache
Blocking Queue	BlockingQueue	Markus Kuppe	✔	✔	✔	(✔)
IEEE 802.16 WiMAX Protocols	2006, paper, specs	Prasad Narayana, Ruiming Chen, Yao Zhao, Yan Chen, Zhi (Judy) Fu, Hai Zhou
On the diversity of asynchronous communication	2016, paper, specs	Florent Chevrou, Aurélie Hurault, Philippe Quéinnec
Caesar	Multi-leader generalized consensus protocol (Arun et al., 2017)	Giuliano Losa			✔	✔
CASPaxos	An extension of the single-decree Paxos algorithm to a compare-and-swap type register (Rystsov)	Tobias Schottdorf			✔
DataPort	Dataport protocal 505.89PT, only PDF files (Biggs & Noriaki, 2016)	Geoffrey Biggs, Noriaki Ando
egalitarian-paxos	Leaderless replication protocol based on Paxos (Moraru et al., 2013)	Iulian Moraru			✔
fastpaxos	An extension of the classic Paxos algorithm, only PDF files (Lamport, 2006)	Leslie Lamport
fpaxos	A variant of Paxos with flexible quorums (Howard et al., 2017)	Heidi Howard			✔
HLC	Hybrid logical clocks and hybrid vector clocks (Demirbas et al., 2014)	Murat Demirbas			✔	✔
L1	Data center network L1 switch protocol, only PDF files (Thacker)	Tom Rodeheffer
leaderless	Leaderless generalized-consensus algorithms (Losa, 2016)	Giuliano Losa			✔	✔
losa_ap	The assignment problem, a variant of the allocation problem (Delporte-Gallet, 2018)	Giuliano Losa			✔	✔
losa_rda	Applying peculative linearizability to fault-tolerant message-passing algorithms and shared-memory consensus, only PDF files (Losa, 2014)	Giuliano Losa
m2paxos	Multi-leader consensus protocols (Peluso et al., 2016)	Giuliano Losa			✔
mongo-repl-tla	A simplified part of Raft in MongoDB (Ongaro, 2014)	Siyuan Zhou			✔
MultiPaxos	The abstract specification of Generalized Paxos (Lamport, 2004)	Giuliano Losa			✔
naiad	Naiad clock protocol, only PDF files (Murray et al., 2013)	Tom Rodeheffer			✔
nfc04	Non-functional properties of component-based software systems (Zschaler, 2010)	Steffen Zschaler			✔
raft	Raft consensus algorithm (Ongaro, 2014)	Diego Ongaro			✔
SnapshotIsolation	Serializable snapshot isolation (Cahill et al., 2010)	Michael J. Cahill, Uwe Röhm, Alan D. Fekete			✔
SyncConsensus	Synchronized round consensus algorithm (Demirbas)	Murat Demirbas			✔	✔
Termination	Channel-counting algorithm (Kumar, 1985)	Giuliano Losa		✔	✔	✔	✔
Tla-tortoise-hare	Robert Floyd's cycle detection algorithm	Lorin Hochstein			✔	✔
VoldemortKV	Voldemort distributed key value store	Murat Demirbas			✔	✔
Tencent-Paxos	PaxosStore: high-availability storage made practical in WeChat. Proceedings of the VLDB Endowment(Zheng et al., 2017)	Xingchen Yi, Hengfeng Wei		✔	✔
Paxos	Paxos				✔
Lock-Free Set	PlusCal spec of a lock-Free set used by TLC	Markus Kuppe			✔	✔
ParallelRaft	A variant of Raft	Xiaosong Gu, Hengfeng Wei, Yu Huang			✔
CRDT-Bug	CRDT algorithm with defect and fixed version	Alexander Niederbühl			✔
asyncio-lock	Bugs from old versions of Python's asyncio lock	Alexander Niederbühl			✔
Raft (with cluster changes)	Raft with cluster changes, and a version with Apalache type annotations but no cluster changes	George Pîrlea, Darius Foom, Brandon Amos, Huanchen Zhang, Daniel Ricketts			✔		✔
MET for CRDT-Redis	Model-check the CRDT designs, then generate test cases to test CRDT implementations	Yuqi Zhang			✔	✔
Parallel increment	Parallel threads incrementing a shared variable. Demonstrates invariants, liveness, fairness and symmetry	Chris Jensen			✔
The Streamlet consensus algorithm	Specification and model-checking of both safety and liveness properties of Streamlet with TLC	Giuliano Losa			✔	✔
Petri Nets	Instantiable Petri Nets with liveness properties	Eugene Huang			✔
CRDT	Specifying and Verifying CRDT Protocols	Ye Ji, Hengfeng Wei			✔
Azure Cosmos DB	Consistency models provided by Azure Cosmos DB	Dharma Shukla, Ailidani Ailijiang, Murat Demirbas, Markus Kuppe			✔	✔
Simple Microwave Oven	Spec of a microwave oven	Konstantin Läufer, George K. Thiruvathukal	✔			✔

Contributing a Spec

See CONTRIBUTING.md for instructions.

License

The repository is under the MIT license and you are encouraged to publish your spec under a similarly-permissive license. However, your spec can be included in this repo along with your own license if you wish.

Support or Contact

Do you have any questions or comments? Please open an issue or send an email to the TLA⁺ mailing list.