Generating TLA+ Verification Models for Distributed Systems Using AI Agents
Depot used AI agents to translate Go database transactions and S3 API calls directly into TLA+ formal specifications. The TLC model checker evaluated over 14 million states to discover a subtle race condition in container registry garbage collection.
Impact: High
Why it matters
You can now delegate tedious TLA+ syntax generation to AI agents, leaving engineers to focus purely on defining critical system invariants.
TL;DR
- 01Use AI coding agents to translate multi-step backend logic into TLA+ state machine modules.
- 02Combine model checking with human code reviews focused on invariant definitions rather than syntax.
- 03Implement object versioning in blob stores as a delete fence to prevent race conditions during garbage collection.
Key facts
- States explored
- 14,290,224 distinct states
- Model checker runtime
- ~21 minutes
- Verified properties
- 10 safety invariants, 2 liveness properties
- Storage key format
- blobs/sha256/<digest>
Solving the High Cost of TLA+ Spec Creation
Formal verification with Temporal Logic of Actions (TLA+) and the TLC model checker provides mathematical proof of system correctness, but hand-writing specifications has historically been too time-consuming for standard development cycles. Depot bypassed this hurdle by using AI agents to translate existing Go code, SQL queries, and S3 transactions directly into TLA+ specs. Developers then focus strictly on defining safety invariants while human review validates the abstractions.
Catching Concurrency Races in Garbage Collection
During the rebuild of the Depot Registry garbage collector, the TLC model checker evaluated 14,290,224 distinct states across 10 safety invariants and 2 liveness properties in approximately 21 minutes. It uncovered a critical race condition where a garbage collection worker verified zero references and initiated deletion at blobs/sha256/<digest>, while a client concurrently re-uploaded the exact same content-addressed blob and committed a new manifest.
S3 Versioning as a Safe Delete Fence
Because database references in MySQL and blob storage in S3 cannot be updated in a single atomic cross-system transaction, traditional re-checking fails. Depot resolved this by turning on S3 bucket versioning as a delete fence. The garbage collector captures a specific version ID v1 during the mark phase and explicitly deletes only v1. If a concurrent upload occurs, it receives version v2, keeping active manifest references intact without locking.
Try it in 2 minutes
ManifestNeedsData == \A p \in PusherIDs: manifestExists[p] => s3Versions /= {}tla
✓ When to use
- Verifying non-atomic distributed transactions across relational databases and object storage.
- Designing asynchronous garbage collection or background reconciliation loops.
- Automating formal specification syntax drafting with LLM agentic tools.
What to do today
- Prompt your agent to extract database transaction steps and convert them into TLA+ state transitions.
- Verify state-machine edge cases in distributed systems using the TLC model checker.
- Enable S3 versioning on content-addressed stores to scope deletion operations to explicit version IDs.
Sources