💻 computer science

Declarative distributed algorithms as axiomatic theories in three-valued modal logic over semitopologies

This paper proposes a novel framework for formally specifying distributed algorithms as declarative axiomatic theories within a three-valued modal logic over semitopologies, offering a precise, high-level abstraction that captures essential system properties while enabling rigorous human and machine verification, as demonstrated by formalized proofs in Lean 4 for voting, broadcast, and agreement protocols.

Original authors: Murdoch J. Gabbay

Published 2026-03-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Murdoch J. Gabbay

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to explain how a group of strangers, scattered across the world, can agree on a single decision (like "Yes" or "No") even if some of them are liars, some have bad internet, and some might try to sabotage the process.

This is the problem of distributed algorithms. Usually, computer scientists solve this by writing long, complex code that describes every single step: "If I get a message, wait 2 seconds, check my clock, send a reply..." It's like writing a recipe that lists every single chop, stir, and heat setting. It works, but it's hard to read, hard to prove is correct, and easy to mess up.

Murdoch Gabbay's paper proposes a radical new way to think about this. Instead of writing a recipe (code), he suggests writing a constitution (a set of rules).

Here is the breakdown of his idea using simple analogies:

1. The "Constitution" vs. The "Recipe"

The Old Way (Imperative/Recipe): "First, Alice sends a message to Bob. Then Bob waits. If Bob hears from 5 people, he votes." This focuses on how the machine moves step-by-step.
The New Way (Declarative/Constitution): "If a decision is made, it must be because a majority of honest people agreed on it." This focuses on what must be true, regardless of the steps taken to get there.

Gabbay argues that if you write the "Constitution" correctly, you don't need to worry about the messy details of the "Recipe." You just need to prove that the Constitution holds up.

2. The Three-Valued Logic (The "Maybe" Button)

In normal math, things are either True or False.

True = The computer did the right thing.
False = The computer made a mistake.

But in a distributed system, there is a third state: The Byzantine (or "Both") state.
Imagine a participant who is a liar. They might tell Alice "I voted Yes" and tell Bob "I voted No."

True (t): Honest behavior.
False (f): A clear error.
Both (b): The "Byzantine" state. The participant is acting weirdly, sending conflicting messages.

Gabbay uses a special logic that handles this "Both" value automatically. It's like having a traffic light that has a "Maybe" light. If the light is "Maybe," the system knows to be extra careful, but it doesn't crash. This allows the math to handle liars without needing a separate "if-then" rule for every possible lie.

3. Semitopologies (The "Quorum" Map)

In these systems, a "Quorum" is a group large enough to make a decision (e.g., "We need 2 out of 3 people to agree").
Usually, mathematicians count people: "We need 51% of the group."
Gabbay uses a concept called Semitopology.

Analogy: Imagine a map of a city. In a normal map, if you have two parks, their intersection is just a smaller park. In Gabbay's "Semitopology," the "open sets" (the parks) represent Quorums.
The magic rule is: If you pick any three different Quorums, they must all overlap at least at one honest person.
This ensures that no two groups can make conflicting decisions without at least one honest person being part of both groups, acting as a bridge to keep everyone aligned.

4. The "Time" Trick

Most computer science models treat time like a movie: Frame 1, Frame 2, Frame 3.
Gabbay's approach removes the "movie." There are no frames. There is just a snapshot of what is true now.

Analogy: Instead of watching a movie of a ball being thrown, you just look at a photo of the ball in the air and ask, "Does this photo obey the laws of physics?"
He uses Backward Rules (like a detective): "If you see a 'Delivered' message, it must be because a 'Ready' message existed before it."
This creates a "Logical Time" (cause and effect) without needing to track "Clock Time" (seconds and milliseconds). It's much simpler because it ignores the messy implementation details of when things happened, focusing only on why they happened.

5. Why This Matters (The "Error Hunter")

The paper shows that by using this "Constitution" approach, they could:

Simplify proofs: Proving a complex algorithm works became as easy as solving a logic puzzle.
Find hidden bugs: They applied this to a real-world industrial protocol (Heterogeneous Paxos). The "recipe" (code) looked fine, but when they wrote the "Constitution" (axioms), the logic revealed a hidden flaw that the engineers had missed.
Future-proofing: If you have a perfect Constitution, you can build many different "Recipes" (implementations) underneath it. As long as the Recipe follows the Constitution, it's guaranteed to be safe.

Summary

Gabbay is saying: "Stop trying to describe the dance steps. Describe the rules of the dance floor."

By using a special three-way logic (True, False, and "Liar") and a topological map of groups (Quorums), we can describe complex distributed systems as simple sets of logical rules. This makes it easier to prove they are safe, easier to find bugs, and easier to build new, better systems on top of them. It turns the chaotic problem of "how do computers agree?" into the clean, solvable problem of "does this logic hold up?"

Technical Summary: Declarative Distributed Algorithms as Axiomatic Theories

1. Problem Statement

Distributed algorithms (e.g., consensus, broadcast, voting) are notoriously difficult to design, specify, and verify due to the inherent complexity of coordinating multiple participants who may be faulty, hostile (Byzantine), or disconnected.

Current Limitations: Traditional specifications often rely on natural language or imperative pseudocode, which can be ambiguous. Formal verification methods like TLA+ or model checking typically model algorithms as state transition systems (imperative approach). While rigorous, these approaches can become computationally expensive and obscure the "logical essence" of the algorithm by focusing on low-level implementation details (e.g., specific message ordering, state transitions).
The Challenge: There is a need for a specification methodology that is:
1. Declarative: Focusing on what the system properties are, rather than how they are computed step-by-step.
2. Compact: Abstracting away implementation details to provide human-readable, concise proofs.
3. Robust: Capable of handling Byzantine failures and resilience requirements without becoming combinatorially complex.

2. Methodology

The paper proposes a novel framework that models distributed algorithms as axiomatic theories within a three-valued modal logic defined over semitopologies.

Core Components

Semitopologies (Quorums as Open Sets):
- Instead of defining quorums via specific counting thresholds (e.g., "2f+1 participants"), the authors use semitopologies (a structure similar to topology but without requiring the intersection of two open sets to be open).
- Participants are points in a set $P$ .
- Quorums are represented as non-empty open sets ( $Open \neq \emptyset$ ).
- This abstraction allows reasoning about intersection properties (e.g., "any two quorums intersect") without explicit arithmetic counting.
Three-Valued Logic (Handling Byzantine Behavior):
- The logic uses a truth-value lattice: $f$ (False), $b$ (Both/Byzantine), and $t$ (True).
- $t$ and $f$ represent correct/honest behavior.
- $b$ represents faulty or Byzantine behavior (e.g., a participant sending conflicting messages).
- This allows the logic to "absorb" faults: if a participant is Byzantine ( $b$ ), implications involving them often remain valid without needing explicit "if the participant is honest" side-conditions in every axiom.
Modal Logic & Axiomatic Structure:
- The framework uses modal operators to represent system properties:
  - $\square \cdot f$ (Quorum-f): True if $f$ holds for a quorum.
  - $\diamond \cdot f$ (Contraquorum-f): True if $f$ holds for a blocking set.
  - $\Box f$ / $\Diamond f$ : Standard "everywhere" and "somewhere" modalities.
- Axioms are divided into:
  - Backward Rules (?): "If event $A$ happened, then event $B$ must have happened previously." (Reasoning about causality).
  - Forward Rules (!): "If event $A$ happens, then event $B$ must happen." (Reasoning about progress).
  - Correctness Assumptions: Axioms asserting the existence of honest quorums.
3-Twined Semitopologies:
- A specific structural property where any three non-empty open sets have a non-empty intersection. This is crucial for proving agreement properties in Byzantine fault-tolerant systems (ensuring that if two participants see different quorums, there is a third honest participant in the intersection).

3. Key Contributions

A. Theoretical Framework

Declarative Abstraction: The paper establishes that distributed protocols can be treated as logical theories where a "run" of the protocol is a "model" of the theory. This shifts the focus from state transitions to logical validity.
New Logic: It introduces a specific three-valued modal logic over semitopologies, formalizing the relationship between topology (quorums) and logic (truth values).
Formalization: All proofs in the paper have been formalized in Lean 4, ensuring mathematical rigor.

B. Case Studies

The authors apply this framework to three distinct algorithms, demonstrating scalability and precision:

Simple Voting Protocol: Used to introduce the machinery. Proves Agreement (consistency) using the 3-twined property.
Declarative Bracha Broadcast: A classic broadcast algorithm. The authors axiomatize it and prove standard properties: Validity, Integrity, Consistency, and Totality.
Declarative Crusader Agreement: An agreement protocol where participants start with different inputs. The authors prove Weak Agreement, Validity, and Liveness.
- Discovery: During the axiomatization of Crusader Agreement, the authors identified an unintended redundancy in the original pseudocode (a conjunct that was never used), which was invisible in the imperative description but obvious in the logical axioms.

C. Industrial Application (Mentioned)

The paper notes that these techniques were successfully scaled to analyze Heterogeneous Paxos, a complex industrial protocol. The declarative approach helped identify errors that were difficult to find using traditional imperative debugging, leading to a corrected protocol design verified in Lean 4.

4. Results

Correctness Proofs: The paper provides compact, symbolic proofs for the correctness of Bracha Broadcast and Crusader Agreement. These proofs rely on lattice properties and modal logic rules rather than combinatorial counting arguments.
Error Detection: The method successfully identified a logical redundancy in the Crusader Agreement pseudocode, demonstrating that the declarative approach can reveal flaws in existing specifications.
Abstraction Power: The framework successfully elides low-level details (like specific message counts) while preserving the essential logical structure required for safety and liveness.
Time and Causation: The paper argues that this approach eliminates "algorithmic time" (state transitions) but retains "logical time" (causal ordering of predicates via backward rules), offering a more abstract view of causality in distributed systems.

5. Significance and Impact

Paradigm Shift: Moves distributed algorithm specification from an imperative (state-transition) mindset to a declarative (axiomatic) one, similar to the difference between writing a for loop and using a map function.
Human-Readable Specifications: The axioms are concise and precise, serving as a "source of truth" that is easier for humans to reason about than complex state machines.
Foundation for Verification: Provides a solid foundation for both human and machine verification. Since the specifications are logical theories, they can be fed into theorem provers (like Lean 4) to verify implementations.
Scalability: The approach is designed to handle complex, industrial-scale protocols (as evidenced by the Heterogeneous Paxos case study) by abstracting away implementation noise.
Future Directions: The paper suggests potential for compiling these declarative specifications directly into efficient executable code and integrating them into model-checking tools, bridging the gap between high-level design and low-level implementation.

In summary, Murdoch J. Gabbay presents a powerful new methodology that uses three-valued modal logic over semitopologies to distill distributed algorithms into their logical essence. This approach simplifies reasoning about Byzantine faults, uncovers hidden flaws in specifications, and offers a rigorous, abstract foundation for the design and verification of future distributed systems.