💻 computer science

Self-Correcting Gossip Protocols

This paper proposes a dynamic epistemic logic framework for self-correcting gossip protocols that enables distributed systems to autonomously correct transmission errors without central coordination, while analyzing the resulting impacts on optimality and comparing the approach to bounded memory and full information protocols.

Original authors: Giorgio Cignarale, Hans van Ditmarsch, Stephan Felber, Malvin Gattinger, Hugo Rincon Galeana, Vaishnavi Sundararajan

Published 2026-05-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Giorgio Cignarale, Hans van Ditmarsch, Stephan Felber, Malvin Gattinger, Hugo Rincon Galeana, Vaishnavi Sundararajan

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 a group of friends sitting in a circle, each holding a unique secret (like a password or a favorite song). Their goal is simple: everyone needs to know everyone else's secret. In the perfect world of computer science, they just take turns whispering to each other, swapping all the secrets they know until everyone is an "expert."

But in the real world, whispers get garbled. A friend might mishear a secret, or a message might get corrupted. This paper asks: What happens when gossip goes wrong, and can the friends fix it themselves without a teacher or a boss telling them what to do?

Here is the breakdown of the paper's findings using simple analogies:

1. The Problem: The "Garbled Whisper"

In a normal game, if Alice tells Bob her secret, Bob knows it forever. But in this paper's version, sometimes the message gets flipped. If Alice whispers "My secret is Red," Bob might hear "My secret is Blue."

If Bob believes it's Blue, he might tell Charlie it's Blue. Now the whole group is confused. In traditional computer science, this usually means the whole system crashes or needs a central referee to fix it. This paper asks: Can the friends fix the confusion just by talking to each other more?

2. The Solution: The "Self-Correcting" Group

The authors propose a system where the friends don't need a referee. Instead, they use a clever trick based on repetition and conflict detection.

The Conflict: Imagine Alice hears "Red" from Bob, but later hears "Blue" from Charlie. She now has a conflict. She knows something is wrong, but she doesn't know who is wrong yet.
The Fix: The friends keep talking. If Alice hears "Red" from two different people and "Blue" from only one, she realizes, "Okay, the majority says Red, so Blue must be the mistake." She then throws away the "Blue" idea and accepts "Red."
The Magic: The paper proves that even if one message gets garbled, the group can eventually sort it out. They don't need to know who made the mistake; they just need enough independent confirmations to see the majority truth.

3. "Lucky" Friends

One of the coolest findings is that you don't always have to talk to someone to know their secret.

The Analogy: Imagine Alice wants to know Dave's secret. She doesn't call Dave. Instead, she talks to Bob and Charlie. Bob says, "Dave told me his secret is X." Charlie says, "Dave told me his secret is X."
The Result: Even though Alice never spoke to Dave, she is now 100% sure of his secret. In the paper's language, she is "lucky." She figured out the truth just by listening to the echoes of other people's conversations.

4. The "Super Expert" Goal

There are two levels of success in this game:

Expert: Everyone knows all the secrets.
Super Expert: Everyone knows that everyone else knows all the secrets.

The paper finds a tricky twist here. It is possible for everyone to know all the secrets, but for them to be unsure if everyone else knows them.

The Twist: Because of the possibility of a garbled message, Alice might think, "I know the secrets, but maybe Bob is still confused because he heard a wrong message."
The Stability: The paper shows that the only state that is truly "stable" and unshakeable is when everyone is a Correct Super Expert. This means everyone knows the secrets, everyone knows everyone else knows them, and everyone is absolutely certain that no one is holding a wrong belief. It takes a bit longer to reach this "Super Expert" state, but it's the only one that guarantees the system is truly fixed.

5. Memory vs. Full History

The authors also compared two ways the friends could remember things:

Bounded Memory (The "Last Call" Rule): Friends only remember the last person they spoke to. The paper finds this is risky. If the last call was the one with the error, they might never realize the mistake because they forgot the earlier correct information.
Full Information (The "Diary" Rule): Friends remember every conversation they've ever had. This is much stronger. It allows them to reach the "Super Expert" goal much faster because they can trace the history of every secret to see where the error happened.

Summary

The paper proves that a group of people (or computers) can fix a single mistake in their communication chain without needing a boss. They do this by:

Listening for conflicts (when two stories don't match).
Trusting the majority (if three people say X and one says Y, X is likely right).
Being patient (sometimes you need to talk to the same person twice to be sure).

While it might take a few extra phone calls to fix the error, the group can eventually reach a state where everyone is 100% sure of the truth, and 100% sure that everyone else is too.

Technical Summary: Self-Correcting Gossip Protocols

Problem Statement
The paper investigates gossip protocols in distributed systems where agents exchange secrets to achieve epistemic goals (specifically, becoming "experts" who know all secrets, or "super experts" who know that everyone knows all secrets). While standard gossip protocols assume error-free transmission and correct agent behavior, this work addresses the scenario where at most one transmission error occurs during protocol execution. The core challenge is to determine how agents can self-correct false beliefs caused by faulty messages without a central authority, how this affects the reachability of epistemic goals, and how the optimality of call sequences compares to error-free, bounded memory, and full-information protocols.

Methodology
The authors propose a Dynamic Epistemic Logic (DEL) framework tailored for gossip with errors, differing from previous investigations that relied on temporal epistemic logics.

Formal Structures:
- Secrets and Values: Secrets are modeled as pairs $(a, v)$ where $v \in \{0, 1\}$ . An agent holds a value for a secret; a "correct" value is denoted $b$ and an "incorrect" (faulty) value $\bar{b}$ .
- Call Semantics: A call between agents $a$ $a$ and $b$ $b$ involves exchanging all known secret values. The semantics introduce a mechanism for self-correction:
  - If an agent receives a value conflicting with a value they already know to be correct (based on prior knowledge), the incorrect value is discarded (set $\ast$ ).
  - If an agent receives a value that creates a conflict with a value they held previously, and subsequent reasoning (based on the global clock and the "at most one error" assumption) reveals the prior value was incorrect, the agent discards the old value (set $\ast\ast$ ).
- Observation Model: The system is modeled as a Kripke model where states are pairs $(S, \sigma)$ consisting of an initial secret distribution $S$ and a call sequence $\sigma$ . The observation relation $\sim_a$ defines indistinguishability for agent $a$ . Crucially, agents are aware of a global clock (synchronous setting) and know which calls involve them, but they cannot distinguish between a correct call and a faulty call involving other agents unless the resulting state creates a conflict or contradiction with the "at most one error" constraint.
Logical Language:
- The language includes atoms for holding specific values ( $b_a$ , $\bar{b}_a$ ) and knowledge operators ( $K_a$ ).
- Knowledge vs. Belief: The paper distinguishes between holding a value (belief) and knowing a value. Knowledge ( $K_v ab$ ) is defined as justified correct belief. The authors prove that knowledge implies correct belief, but correct belief does not necessarily imply knowledge (as the agent may not yet have ruled out the possibility of error).

Key Contributions and Results

Self-Correction Mechanism:
The paper demonstrates that agents can resolve conflicts and recover the correct secret values without central coordination. By leveraging the constraint that at most one transmission error occurs, agents can eliminate indistinguishable scenarios where multiple errors would be required to explain a conflict. This allows them to identify the correct value through a "majority" of independent observations or by ruling out faulty call sequences.
Epistemic Goals and Stability:
- Expert Goal: The protocol ensures that all agents eventually become experts (holding all correct secrets without conflict).
- Super Expert Goal: The protocol ensures that all agents eventually become super experts.
- Stability: A critical finding is that the goal of "correct super success" (all agents know that all agents hold correct secrets) is the only stable termination goal. In contrast, the goal of simply being an expert ( $Exp_A$ ) is unstable; an agent might temporarily satisfy the expert condition but lose it if a subsequent call introduces a conflict that hasn't yet been resolved.
- First-Correctness: The standard "ANY" protocol (where any pair can call) is not "first-correct successful." Agents may reach the state of being experts before they reach the state of being correct experts. They may hold all secrets but still harbor incorrect beliefs about some values before self-correcting.
Comparison with Other Semantics:
- Bounded Memory (Last-Call Semantics): The authors compare their full-history semantics with a "last-call" semantics where agents only remember the most recent exchange. They find that while last-call semantics can achieve "first-correct supersuccess," it fails to preserve knowledge of secrets over time (knowledge is unstable) and cannot guarantee correct termination in the same robust way as the full-history approach.
- Full-Information Protocols: The paper analyzes full-information protocols where agents exchange their entire view of the call history. In error-free settings, full-information protocols can reach super-expert goals faster and achieve higher-order epistemic goals (e.g., $EAEAEA Exp_A$ ) that are unreachable in standard semantics. However, in the presence of errors, the authors conjecture that while full-information protocols still allow for faster convergence, the fundamental instability of higher-order goals in standard semantics persists.
Lucky Calls:
The paper illustrates "lucky calls," where an agent learns that another agent is an expert (or holds a correct secret) without directly calling them, by observing the interactions of others and ruling out error scenarios. This phenomenon is shown to be possible even with transmission errors, though it requires careful analysis of the call sequence to rule out conflicting error hypotheses.

Significance and Claims
The paper claims to provide the first dynamic epistemic logic analysis of self-correcting gossip protocols with transmission errors. Its primary significance lies in:

Formalizing Self-Correction: Showing how distributed agents can autonomously correct false beliefs using only local observations and a global clock, without central authority.
Refining Epistemic Goals: Distinguishing between "expert" and "correct expert" states, and proving that the latter is the only stable termination condition in error-prone environments.
Optimality Insights: Demonstrating that while lower bounds on call sequences must increase to accommodate error correction, agents can sometimes achieve goals faster than expected via "lucky calls" where they infer correctness without direct interaction.
Foundations for Future Work: The authors position this work as a foundation for extending results to asynchronous settings, multiple transmission errors ( $f$ errors), and Byzantine (faulty) agents. They explicitly state that generalizing to $f$ errors and asynchronous models are the intended next steps, noting that the current synchronous, single-error model serves as a necessary technical precursor.

The paper concludes that while error-free gossip has well-known optimal bounds ( $2n-4$ for experts, $n-2 + \binom{n}{2}$ for super experts), the introduction of errors necessitates a more complex logical framework where "knowledge" is defined as justified correct belief, and where the stability of termination goals is a critical property for protocol design.