TLA+

TLA+ is considered to be exhaustively-testable pseudocode,[4] and its use likened to drawing blueprints for software systems;[5] TLA is an acronym for Temporal Logic of Actions.

The model checker finds all possible system behaviours up to some number of execution steps, and examines them for violations of desired invariance properties such as safety and liveness.

The proofs are written in a declarative, hierarchical style independent of any single theorem prover backend.

Although Amir Pnueli was the first to seriously study the applications of temporal logic to computer science, Prior speculated on its use a decade earlier in 1967: The usefulness of systems of this sort [on discrete time] does not depend on any serious metaphysical assumption that time is discrete; they are applicable in limited fields of discourse in which we are concerned only with what happens next in a sequence of discrete states, e.g. in the working of a digital computer.Pnueli researched the use of temporal logic in specifying and reasoning about computer programs, introducing linear temporal logic in 1977.

LTL became an important tool for analysis of concurrent programs, easily expressing properties such as mutual exclusion and freedom from deadlock.

Leslie Lamport became interested in the problem after peer review found an error in a paper he submitted on mutual exclusion.

[9] This method was used to verify the first concurrent garbage collection algorithm in a 1978 paper with Edsger Dijkstra.

According to Lamport, "I was sure that temporal logic was some kind of abstract nonsense that would never have any practical application, but it seemed like fun, so I attended."

[11] Lamport worked on writing temporal logic specifications during his time at SRI, but found the approach to be impractical: However, I became disillusioned with temporal logic when I saw how Schwartz, Melliar-Smith, and Fritz Vogt were spending days trying to specify a simple FIFO queue – arguing over whether the properties they listed were sufficient.

I realized that, despite its aesthetic appeal, writing a specification as a conjunction of temporal properties just didn't work in practice.

[12]His search for a practical method of specification resulted in the 1983 paper "Specifying Concurrent Programming Modules", which introduced the idea of describing state transitions as boolean-valued functions of primed and unprimed variables.

TLA provided a mathematical foundation to the specification language TLA+, introduced with the paper "Specifying Concurrent Systems with TLA+" in 1999.

[14] Lamport published a full textbook on TLA+ in 2002, titled "Specifying Systems: The TLA+ Language and Tools for Software Engineers".

[17] TLA+2 was announced in 2014, adding some additional language constructs as well as greatly increasing in-language support for the proof system.

Two such behaviours are: The safety properties of the one-bit clock – the set of reachable system states – are adequately described by the spec.

The language includes set membership, union, intersection, difference, powerset, and subset operators.

Strong fairness SFe(A) means if action A is enabled continually (repeatedly, with or without interruptions), it must eventually be taken.

It includes an editor with error and syntax highlighting, plus a GUI front-end to several other TLA+ tools: The IDE is distributed in The TLA Toolbox.

[14] It also parallelizes the state exploration step, and can run in distributed mode to spread the workload across a large number of computers.

It was developed at the Microsoft Research-INRIA Joint Centre to prove correctness of concurrent and distributed algorithms.

TLAPS works well with TLC, as the model checker quickly finds small errors before verification is begun.

Isabelle and Zenon generally cannot prove arithmetic proof obligations, requiring use of the SMT solvers.

[21] TLAPS has been used to prove correctness of Byzantine Paxos, the Memoir security architecture, components of the Pastry distributed hash table,[17] and the Spire consensus algorithm.

At Microsoft, a critical bug was discovered in the Xbox 360 memory module during the process of writing a specification in TLA+.

[24] TLA+ was used to write formal proofs of correctness for Byzantine Paxos and components of the Pastry distributed hash table.

[4][25] Microsoft Azure used TLA+ to design Cosmos DB, a globally-distributed database with five different consistency models.

Portrait of an Israeli man in his sixties. His hair is short and balding, and he is wearing glasses with a dress shirt and jacket.
Amir Pnueli applied temporal logic to computer science, for which he received the 1996 Turing Award .
Portrait of a Caucasian man in his seventies with medium-length gray hair and a full gray beard, wearing glasses and a T-shirt.
TLA + was developed by computer scientist and 2013 Turing award recipient Leslie Lamport .
Finite state machine diagram of one-bit clock
States and transitions discovered by TLC for the one-bit clock.