Propositional Gossip Protocols under Fair Schedulers

Joseph Livesey, Dominik WojtczakIJCAI 2022 · DOI

TL;DR

This paper investigates how fairness constraints on schedulers drastically alter the conditions under which "gossip protocols" (information-spreading algorithms) are guaranteed to work correctly. They show that while unrestricted schedulers require a complete communication network, fair schedulers allow for correct protocols on a much wider range of network structures, including any connected graph. Furthermore, they establish that checking the correctness of these protocols under fair schedulers is a coNP-complete problem.

What Problem Does This Paper Address?

Gossip protocols are designed for distributed systems where agents (like computers or robots) need to synchronize information. The fundamental goal is for every agent to eventually know a secret initially held by another agent. This paper focuses on "propositional gossip protocols," a simplified version where an agent's decision to communicate depends only on the secrets it currently possesses.

A key challenge in studying these protocols is ensuring they are "correct," meaning they eventually terminate with all agents knowing all secrets. Previous work showed that for a protocol to be correct without any fairness guarantees on how calls are scheduled, the communication network (graph) between agents had to be "complete" – every agent could directly communicate with every other agent.

This paper addresses a crucial question: What happens to the network requirements for correctness when we introduce fairness constraints on the scheduler? Fairness is essential in real-world distributed systems to prevent starvation and ensure progress. The authors specifically consider two types of fairness: "agent-fairness" (each agent that wants to call eventually gets to) and "rule-fairness" (each communication rule that is active eventually gets executed). They investigate how these fairness notions change the necessary communication graph structures for correct propositional gossip protocols and analyze the computational complexity of checking correctness under these fair schedulers.

Methods

The paper builds upon existing work on epistemic logic and gossip protocols, particularly the framework introduced by Apt et al. (2016). They define a formal language for propositional gossip protocols and the semantics of gossip situations (which secrets agents know).

The core methodological contributions involve:

  • Characterizing Communication Graphs under Fairness: They systematically explore which types of communication graphs (paths, trees, strongly connected digraphs) can support correct propositional gossip protocols under agent-fair and rule-fair schedulers. This involves constructing specific protocols for each graph class.
  • Distinguishing Fairness Types: They demonstrate that agent-fairness and rule-fairness are not equivalent in terms of protocol correctness, providing examples of protocols that are correct under one but not the other.
  • Complexity Analysis: They analyze the computational complexity of checking whether a given propositional gossip protocol is correct under agent-fair or rule-fair schedulers. This involves proving both membership in coNP and coNP-hardness.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Fairness Dramatically Expands Network Possibilities: The most significant insight is that imposing fairness constraints on the scheduler fundamentally changes the network requirements for correct gossip protocols. A complete graph is no longer a strict necessity.
  • Agent-Fairness vs. Rule-Fairness Distinction: The paper highlights that agent-fairness and rule-fairness are distinct and can lead to different sets of correct protocols. A protocol correct under agent-fairness might not be correct under rule-fairness, and vice-versa. This is demonstrated through concrete examples.
  • Broad Applicability of Fair Protocols: The paper shows that protocols can be designed to be correct under fair schedulers for a wide range of communication graphs, including any connected undirected graph (via spanning trees) and any strongly connected directed graph. This suggests that many real-world network topologies can support reliable information dissemination with fair scheduling.
  • Complexity Remains High: Despite the broader applicability of protocols under fair schedulers, checking their correctness remains computationally challenging, being coNP-complete. This implies that while designing such protocols is feasible for various networks, verifying their correctness is a hard problem.

Key Results

  • Graph Structures for Fair Protocols:
    • For any path graph, an agent-fair correct propositional gossip protocol exists.
  • For any tree (connected acyclic undirected graph), an agent-fair correct propositional gossip protocol exists.
  • For any undirected connected graph, an agent-fair and rule-fair correct propositional gossip protocol exists.
  • For any strongly connected digraph, a rule-fair correct propositional gossip protocol exists.
  • For any strongly connected digraph, an agent-fair correct propositional gossip protocol exists.
  • Complexity of Correctness Checking: Checking if a given propositional gossip protocol is agent-fair or rule-fair correct is a coNP-complete problem.

Limitations and Future Work

  • Open Problem on Graph Classes: While the paper characterizes correctness for path graphs, trees, and strongly connected digraphs, the exact characterization of all communication graph classes that admit agent-fair or rule-fair correct propositional gossip protocols remains an open question.
  • Focus on Propositional Protocols: The study is limited to propositional gossip protocols, where decisions are based solely on known secrets. Future work could explore more expressive protocols with richer guards.
  • Complexity of Specific Fairness: The paper establishes coNP-completeness for checking correctness under both agent-fair and rule-fair schedulers. Further research might investigate if there are differences in complexity between these two fairness types for specific sub-problems.

Summary updated

BibTeX
@inproceedings{livesey2022propositional,
  author = {Joseph Livesey and Dominik Wojtczak},
  title = {{Propositional Gossip Protocols under Fair Schedulers}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/56},
}
Figure