/Alonso-pixel/Examples

Wiki directory

Browse AI-generated documentation for any repository.

Dijkstra's EWD Algorithms

Relevant source files

The following files were used as context for generating this wiki page:

This document provides a technical overview of the TLA+ specifications for several of Edsger W. Dijkstra's algorithms, as found in the EWD (Edsger W. Dijkstra manuscript) series. The repository contains formal specifications for algorithms concerning termination detection and mutual exclusion, which are model-checked using TLC and, in some cases, formally proven with TLAPS.

The primary purpose of these specifications is to serve as a comprehensive example library for writing and verifying algorithms in TLA+. They cover various distributed computing problems and demonstrate different specification and verification techniques.

Sources: [README.md:5-9](https://github.com/Alonso-pixel/Examples/blob/HEAD/README.md#L5-L9), [README.md:46-48](https://github.com/Alonso-pixel/Examples/blob/HEAD/README.md#L46-L48), [README.md:59-60](https://github.com/Alonso-pixel/Examples/blob/HEAD/README.md#L59-L60)

Termination Detection Algorithms

The repository includes several specifications for algorithms designed to detect termination in distributed systems. These algorithms are crucial for understanding when a distributed computation has completed.

EWD687a: Detecting Termination in Distributed Computations

EWD687a is a beginner-friendly TLA+ specification for an algorithm that detects termination in distributed computations. It is available in both standard TLA+ and a PlusCal variant.

Authors: Leslie Lamport, Stephan Merz, Markus Kuppe
Features: Includes a PlusCal version (EWD687aPlusCal.tla) and an animated version (EWD687a_anim.tla) for simulation.
Verification: The main specification is model-checked with TLC via MCEWD687a.tla.

Sources: [README.md:46](https://github.com/Alonso-pixel/Examples/blob/HEAD/README.md#L46), [specifications/ewd687a/manifest.json:4-9](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/ewd687a/manifest.json#L4-L9), [specifications/ewd687a/manifest.json:15-18](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/ewd687a/manifest.json#L15-L18)

EWD840: Termination Detection in a Ring

EWD840 is an algorithm for termination detection specifically designed for ring topologies. It assumes synchronous message delivery and non-faulty nodes. This specification has been verified using both TLC model checking and TLAPS proofs.

Authors: Stephan Merz
Verification: The algorithm's correctness is checked through exhaustive search with TLC and formal proofs.

The following table summarizes the TLA+ modules and models for EWD840.

Module/Model Path	Type	Verification Result	Distinct States	State Depth
`specifications/ewd840/EWD840.tla`	Spec	`success`	302	10
`specifications/ewd840/EWD840_proof.tla`	Proof	N/A	N/A	N/A
`specifications/ewd840/SyncTerminationDetection.tla`	Spec	`success`	129	1
`specifications/ewd840/EWD840_anim.tla`	Spec	`safety failure`	N/A	N/A

Sources: [specifications/ewd998/README.md:12-14](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/ewd998/README.md#L12-L14), [README.md:53](https://github.com/Alonso-pixel/Examples/blob/HEAD/README.md#L53), [specifications/ewd840/manifest.json:8-70](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/ewd840/manifest.json#L8-L70)

EWD998: Termination Detection with Asynchronous Messages

EWD998 extends EWD840 to support asynchronous message delivery, though it still assumes reliable channels and non-faulty nodes. It is a more complex algorithm suitable for learners already familiar with EWD840.

Authors: Stephan Merz, Markus Kuppe
Refinement Hierarchy: The specification is structured as a series of refinements, which have been model-checked with TLC.

The diagram below illustrates the refinement hierarchy for the termination detection specifications.

Generating architecture diagram...

This diagram shows how the abstract SyncTerminationDetection specification is refined by concrete implementations like EWD840 and the more complex EWD998 series.

Sources: [specifications/ewd998/README.md:12-25](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/ewd998/README.md#L12-L25)

Statistical Analysis of EWD998 Variants

The EWD998 specification was used to explore inferring statistical properties by simulating TLA+ specs with TLC's simulator. Four variants of the token-passing logic were created to study their efficiency.

pt1: An active node may pass the token if the node is black/tainted.
pt2: An active node may pass the token if the token is black/tainted.
pt3: Return the token to the initiator if the node is black.
pt4: Return the token to the initiator if the token is black.

Sources: [specifications/ewd998/README.md:73-86](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/ewd998/README.md#L73-L86)

The efficiency was measured by the number of steps between the system's termination and the algorithm's detection of that termination. The PassTokenOpts action in EWD998_opts.tla implements this logic.

PassTokenOpts(n) ==
  /\ n # 0
  /\ \/ ~ active[n]
     \/ /\ "pt1" \in F
        /\ color[n] = "black"
     \/ /\ "pt2" \in F
        /\ \E j \in 1..Len(inbox[n]) : inbox[n][j].type = "tok" /\ inbox[n][j].color = "black"
  /\ \E j \in 1..Len(inbox[n]) : 
          /\ inbox[n][j].type = "tok"
          /\ LET tkn == inbox[n][j]
             IN  inbox' = [inbox EXCEPT ![CASE "pt3" \in F /\ color[n] = "black" -> 0
                                            [] "pt4" \in F /\ tkn.color ="black" -> 0
                                            [] OTHER    ->  n-1] = 
                                       Append(@, [tkn EXCEPT !.q = tkn.q + counter[n],
                                                             !.color = IF color[n] = "black"
                                                                       THEN "black"
                                                                       ELSE tkn.color]),
                                    ![n] = RemoveAt(@, j) ]
  /\ color' = [ color EXCEPT ![n] = "white" ]
  /\ UNCHANGED <<active, counter>>

This TLA+ snippet from EWD998_opts.tla shows how the different optimization variants (pt1-pt4) are conditionally enabled based on the feature flags F.

Sources: [specifications/ewd998/README.md:93-112](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/ewd998/README.md#L93-L112)

Trace Validation

The EWD998 specification was implemented in Java, and its execution traces were validated against the high-level TLA+ model. This process, documented in EWD998ChanTrace.md, involved using TLC action and state constraints to match each line in a log file to a state in a behavior of the high-level spec. This technique helped identify several divergences between the specification and the implementation, such as:

A bug where a node did not retain a token correctly.
The implementation sending messages to itself, which was not allowed by the spec.
An edge case in a single-node configuration.
The initiator starting a new token round even when the previous one was conclusive.

Sources: [specifications/ewd998/EWD998ChanTrace.md:12-14](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/ewd998/EWD998ChanTrace.md#L12-L14), [specifications/ewd998/EWD998ChanTrace.md:27-33](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/ewd998/EWD998ChanTrace.md#L27-L33), [specifications/ewd998/EWD998ChanTrace.md:73-75](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/ewd998/EWD998ChanTrace.md#L73-L75), [specifications/ewd998/EWD998ChanTrace.md:77-79](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/ewd998/EWD998ChanTrace.md#L77-L79), [specifications/ewd998/EWD998ChanTrace.md:81-83](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/ewd998/EWD998ChanTrace.md#L81-L83), [specifications/ewd998/EWD998ChanTrace.md:89-92](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/ewd998/EWD998ChanTrace.md#L89-L92)

Mutual Exclusion Algorithms

Dijkstra's Mutual Exclusion Algorithm

This specification models Dijkstra's classic algorithm for mutual exclusion. It ensures that only one process can be in its critical section at any given time.

Author: Leslie Lamport
Features: The specification is written in PlusCal.
Verification: The model is checked with TLC for a configuration of 4 processors, and the check runs successfully.

Sources: [README.md:60](https://github.com/Alonso-pixel/Examples/blob/HEAD/README.md#L60), [specifications/dijkstra-mutex/manifest.json:4-10](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/dijkstra-mutex/manifest.json#L4-L10), [specifications/dijkstra-mutex/manifest.json:28-37](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/dijkstra-mutex/manifest.json#L28-L37)

Summary

The TLA+ Examples repository provides a valuable collection of specifications for Dijkstra's EWD algorithms. These include multiple approaches to termination detection (EWD687a, EWD840, EWD998) and a classic mutual exclusion algorithm. The specifications demonstrate advanced TLA+ concepts like refinement, proofs, and practical applications such as statistical analysis via simulation and implementation validation via trace checking. They serve as robust, real-world test cases and learning resources for the TLA+ community.

Sources: [README.md:5-9](https://github.com/Alonso-pixel/Examples/blob/HEAD/README.md#L5-L9), [specifications/ewd998/README.md:195-201](https://github.com/Alonso-pixel/Examples/blob/HEAD/specifications/ewd998/README.md#L195-L201)