pith. sign in

arxiv: 1907.09097 · v1 · pith:V7GZ5JCBnew · submitted 2019-07-22 · 💻 cs.AI · cs.LO

Open Problems in a Logic of Gossips

Krzysztof R. Apt (Centrum Wiskunde & Informatica , Amsterdam , The Netherlands , University of Warsaw , Warsaw , Poland) , Dominik Wojtczak (University of Liverpool , Liverpool
show 1 more author
UK)
This is my paper

Pith reviewed 2026-05-24 18:32 UTC · model grok-4.3

classification 💻 cs.AI cs.LO
keywords gossip protocolsepistemic logicmodal logicdistributed protocolsdecidabilitycommon knowledgeopen problemsmulti-agent systems
0
0 comments X

The pith

Several often simple questions about the modal logic for epistemic gossip protocols remain open.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper lists and explains a collection of unresolved questions concerning a modal logic introduced to express and verify distributed epistemic gossip protocols. In these protocols each agent holds a secret and agents communicate to ensure everyone eventually knows every secret, with epistemic formulas guiding the agents' actions. Prior work established that the protocols are implementable, that correctness properties including termination are decidable, and that the semantics and truth definitions of the logic itself are decidable. The same decidability results hold when the logic is extended with a common-knowledge operator. A reader would care because these open questions block a complete picture of how epistemic logic can support concise, verifiable secret-sharing in distributed settings.

Core claim

A natural modal logic permits the expression of distributed epistemic gossip protocols and supports proofs that the protocols are implementable and that all aspects of their correctness, including termination, are decidable; the semantics and truth of the logic are also decidable, and the same holds for the extension with common knowledge, yet several questions about the logic and the protocols remain open.

What carries the argument

The natural modal logic that expresses distributed epistemic gossip protocols and allows reasoning about their correctness.

If this is right

  • Correctness properties of the protocols, including termination, remain decidable within the logic.
  • Both the definition of semantics and the definition of truth in the logic are decidable.
  • The extension of the logic with the common-knowledge operator preserves the decidability results for protocols and for the logic itself.
  • The listed open questions concern both the logic and the concrete gossip protocols that can be written in it.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Answers to the open questions could clarify whether epistemic formulas yield the most compact possible protocols for secret dissemination.
  • The same modal-logic approach might be tested on related distributed tasks such as leader election or consensus.
  • If some of the questions turn out to be undecidable, protocol designers would need to restrict the fragment of the logic they use.

Load-bearing premise

The modal logic previously introduced provides the right framework in which to define and study the open questions about gossip protocols.

What would settle it

A new proof or counter-example that settles the decidability status of any one of the listed open questions about the logic or the protocols.

read the original abstract

Gossip protocols are programs used in a setting in which each agent holds a secret and the aim is to reach a situation in which all agents know all secrets. Such protocols rely on a point-to-point or group communication. Distributed epistemic gossip protocols use epistemic formulas in the component programs for the agents. The advantage of the use of epistemic logic is that the resulting protocols are very concise and amenable for a simple verification. Recently, we introduced a natural modal logic that allows one to express distributed epistemic gossip protocols and to reason about their correctness. We proved that the resulting protocols are implementable and that all aspects of their correctness, including termination, are decidable. To establish these results we showed that both the definition of semantics and of truth of the underlying logic are decidable. We also showed that the analogous results hold for an extension of this logic with the 'common knowledge' operator. However, several, often deceptively simple, questions about this logic and the corresponding gossip protocols remain open. The purpose of this paper is to list and elucidate these questions and provide for them an appropriate background information in the form of partial of related results.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper lists and provides background for several open problems in a modal logic for distributed epistemic gossip protocols (introduced in the authors' prior work). It recalls the established decidability results for the semantics and truth of the logic, the implementability of the protocols, and the decidability of all aspects of correctness including termination, as well as the extension with common knowledge; the central claim is simply that a number of (often simple) questions about the logic and protocols remain unresolved.

Significance. By clearly framing unresolved questions relative to a decidable modal logic for gossip protocols, the paper can usefully direct future work in epistemic logic and multi-agent systems. The prior decidability results (semantics, truth, termination) are a documented strength that makes the open-problem list well-scoped and falsifiable in principle.

minor comments (2)
  1. [Abstract] The abstract states that the paper will 'list and elucidate these questions' but does not enumerate them; adding a brief bullet list of the main open problems would improve immediate readability without altering the manuscript's scope.
  2. Notation for the gossip protocols and epistemic operators is referenced to prior work; a short self-contained recap table of the key modalities and their semantics in §2 or §3 would reduce the need for readers to consult the earlier paper.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment and the recommendation to accept the manuscript. The report accurately summarizes the paper's purpose of listing open problems against the backdrop of our prior decidability results.

Circularity Check

0 steps flagged

No significant circularity: open-problems paper with no derivations

full rationale

This is an open-problems paper whose purpose is to list unresolved questions about a previously introduced modal logic for gossip protocols. It references earlier work solely to provide background and define the open questions relative to that logic; no new theorems, derivations, predictions, or fitted quantities are asserted. The central claim (that certain questions remain open) is not a derivation that could reduce to its inputs by construction, self-citation, or ansatz. No load-bearing technical steps exist to analyze for circularity. The paper is self-contained as a survey of open issues and scores 0.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The paper introduces no new free parameters, axioms, or invented entities; it discusses questions about an existing logic.

pith-pipeline@v0.9.0 · 5756 in / 860 out tokens · 22586 ms · 2026-05-24T18:32:20.952062+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    In: The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’14, ACM, pp

    Carolyn Jane Anderson, Nate Foster, Arjun Guha, Jean-Baptiste Jeannin, Dexter Kozen, Cole Schlesinger & David Walker (2014): NetKAT: semantic foundations for networks . In: The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’14, ACM, pp. 113–126, doi:10.1145/2535838.2535862

    work page doi:10.1145/2535838.2535862 2014

  2. [2]

    Apt, Davide Grossi & Wiebe van der Hoek (2018): When Are Two Gossips the Same? In Gilles Barthe, Geoff Sutcliffe & Margus Veanes, editors: LPAR-22

    Krzysztof R. Apt, Davide Grossi & Wiebe van der Hoek (2018): When Are Two Gossips the Same? In Gilles Barthe, Geoff Sutcliffe & Margus Veanes, editors: LPAR-22. 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, EPiC Series in Computing 57, EasyChair, pp. 36–55, doi:10.29007/ww65

    work page doi:10.29007/ww65 2018

  3. [3]

    Apt, Davide Grossi & Wiebe van der Hoek (2016):Epistemic Protocols for Distributed Gossiping

    Krzysztof R. Apt, Davide Grossi & Wiebe van der Hoek (2016):Epistemic Protocols for Distributed Gossiping. In: Proceedings of the 15th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2015), EPTCS 215, pp. 51–66, doi:10.4204/EPTCS.215.5

    work page doi:10.4204/eptcs.215.5 2016

  4. [4]

    Apt, Eryk Kopczy´nski & Dominik Wojtczak (2017): On the Computational Complexity of Gossip Protocols

    Krzysztof R. Apt, Eryk Kopczy´nski & Dominik Wojtczak (2017): On the Computational Complexity of Gossip Protocols. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, pp. 765–771, doi:10.24963/ijcai.2017/106

    work page doi:10.24963/ijcai.2017/106 2017

  5. [5]

    Apt & Dominik Wojtczak (2016): On Decidability of a Logic of Gossips

    Krzysztof R. Apt & Dominik Wojtczak (2016): On Decidability of a Logic of Gossips. In: Proceedings of the 15th European Conference, JELIA 2016, Lecture Notes in Computer Science 10021, Springer, pp. 18–33, doi:10.1007/978-3-319-48758-8 2

    work page doi:10.1007/978-3-319-48758-8 2016

  6. [6]

    Apt & Dominik Wojtczak (2017): Common Knowledge in a Logic of Gossips

    Krzysztof R. Apt & Dominik Wojtczak (2017): Common Knowledge in a Logic of Gossips. In: Proc. of the 16th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2017), EPTCS 251, pp. 10–27, doi:10.4204/EPTCS.251.2

    work page doi:10.4204/eptcs.251.2 2017

  7. [7]

    Apt & Dominik Wojtczak (2017): Decidability of Fair Termination of Gossip Protocols

    Krzysztof R. Apt & Dominik Wojtczak (2017): Decidability of Fair Termination of Gossip Protocols. In: Proc. of the 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR 21), Kalpa Publications in Computing 1, pp. 73–85, doi:10.29007/62s4

    work page doi:10.29007/62s4 2017

  8. [8]

    Apt & Dominik Wojtczak (2018): Verification of Distributed Epistemic Gossip Protocols

    Krzysztof R. Apt & Dominik Wojtczak (2018): Verification of Distributed Epistemic Gossip Protocols. J. Artif. Intell. Res. (JAIR) 62, pp. 101–132, doi:10.1613/jair.1.11204

    work page doi:10.1613/jair.1.11204 2018

  9. [9]

    In: Proceedings of the 12th European Conference on Multi-Agent Systems (EUMAS 2014), Revised Selected Papers, 8953, Springer, pp

    Maduka Attamah, Hans Van Ditmarsch, Davide Grossi & Wiebe van der Hoek (2014): A Framework for Epistemic Gossip Protocols. In: Proceedings of the 12th European Conference on Multi-Agent Systems (EUMAS 2014), Revised Selected Papers, 8953, Springer, pp. 193–209, doi:10.1007/978-3-319-17130-2 13

    work page doi:10.1007/978-3-319-17130-2 2014

  10. [10]

    In: Proceedings of ECAI’14, IOS Press, pp

    Maduka Attamah, Hans Van Ditmarsch, Davide Grossi & Wiebe van der Hoek (2014):Knowledge and Gossip. In: Proceedings of ECAI’14, IOS Press, pp. 21–26, doi:10.3233/978-1-61499-419-0-21

    work page doi:10.3233/978-1-61499-419-0-21 2014

  11. [11]

    Cooper, Andreas Herzig, Faustine Maffre, Fr´ed´eric Maris & Pierre R´egnier (2016): A simple account of multiagent epistemic planning

    Martin C. Cooper, Andreas Herzig, Faustine Maffre, Fr´ed´eric Maris & Pierre R´egnier (2016): A simple account of multiagent epistemic planning. In: Proceedings of ECAI 2016, IOS Press, pp. 193–201, doi:10.3233/978-1- 61499-672-9-193

    work page doi:10.3233/978-1- 2016

  12. [12]

    Cooper, Andreas Herzig, Faustine Maffre, Fr´ed´eric Maris & Pierre R´egnier (2016): Simple Epistemic Planning: Generalised Gossiping

    Martin C. Cooper, Andreas Herzig, Faustine Maffre, Fr´ed´eric Maris & Pierre R´egnier (2016): Simple Epistemic Planning: Generalised Gossiping . In: Proceedings of ECAI 2016, Frontiers in Artificial Intelligence and Applications 285, IOS Press, pp. 1563–1564, doi:10.3233/978-1-61499-672-9-1563

    work page doi:10.3233/978-1-61499-672-9-1563 2016

  13. [13]

    In: Fodor, P., Montali, M., Calvanese, D., Roman, D

    Martin C. Cooper, Andreas Herzig, Fr ´ed´eric Maris & Julien Vianey (2018): Temporal Epistemic Gossip Problems. In: European Conference on Multi-Agent Systems, Springer, pp. 1–14, doi:10.1007/978-3-030- 14174-5 1. 18 Open Problems in a Logic of Gossips

    work page doi:10.1007/978-3-030- 2018

  14. [14]

    Hans van Ditmarsch, Jan van Eijck, Pere Pardo, Rahim Ramezanian & Fran c ¸ois Schwarzentruber (2017): Epistemic Protocols for Dynamic Gossip. J. of Applied Logic 20(C), pp. 1–31, doi:10.1016/j.jal.2016.12.001

    work page doi:10.1016/j.jal.2016.12.001 2017

  15. [15]

    Hans van Ditmarsch, Jan van Eijck, Pere Pardo, Rahim Ramezanian & Fran c ¸ois Schwarzentruber (2018): Dynamic Gossip. Bull. Iran. Math. Soc., pp. 1–28, doi:10.1007/s41980-018-0160-4

    work page doi:10.1007/s41980-018-0160-4 2018

  16. [16]

    Kuijer (2016): Param- eters for Epistemic Gossip Problems

    Hans van Ditmarsch, Davide Grossi, Andreas Herzig, Wiebe van der Hoek & Louwe B. Kuijer (2016): Param- eters for Epistemic Gossip Problems. In: Proceedings of the 12th Conference on Logic and the Foundations of Game and Decision Theory (LOFT 2016). Available at https://pdfs.semanticscholar.org/ 74b5/2c025f335ba487cac612019e39ce6c818448.pdf

    work page 2016

  17. [17]

    Hans van Ditmarsch, Ioannis Kokkinis & Anders Stockmarr (2017):Reachability and Expectation in Gossiping. In Bo An, Ana Bazzan, Jo˜ao Leite, Serena Villata & Leendert van der Torre, editors: PRIMA 2017: Principles and Practice of Multi-Agent Systems, Springer International Publishing, Cham, pp. 93–109, doi:10.1007/978- 3-319-69131-2 6

    work page doi:10.1007/978- 2017

  18. [18]

    Halpern, Yoram Moses & Moshe Y

    Ronald Fagin, Joseph Y . Halpern, Yoram Moses & Moshe Y . Vardi (1997):Knowledge-Based Programs. Distributed Computing 10(4), pp. 199–225, doi:10.1007/s004460050038

    work page doi:10.1007/s004460050038 1997

  19. [19]

    In: International Conference on Relational and Algebraic Methods in Computer Science, Springer, pp

    Malvin Gattinger & Jana Wagemaker (2018): Towards an Analysis of Dynamic Gossip in NetKAT . In: International Conference on Relational and Algebraic Methods in Computer Science, Springer, pp. 280–297, doi:10.1007/978-3-030-02149-8 17

    work page doi:10.1007/978-3-030-02149-8 2018

  20. [20]

    Hedetniemi, Stephen T

    Sandra M. Hedetniemi, Stephen T. Hedetniemi & Arthur L. Liestman (1988): A survey of gossiping and broadcasting in communication networks. Networks 18(4), pp. 319–349, doi:10.1002/net.3230180406

    work page doi:10.1002/net.3230180406 1988

  21. [21]

    In: Proc of the 13th European Conference on Multi-Agent Systems (EUMAS 2015), Revised Selected Papers, 9571, Springer, pp

    Andreas Herzig & Faustine Maffre (2015): How to Share Knowledge by Gossiping . In: Proc of the 13th European Conference on Multi-Agent Systems (EUMAS 2015), Revised Selected Papers, 9571, Springer, pp. 249–263, doi:10.1007/978-3-319-33509-4 20

    work page doi:10.1007/978-3-319-33509-4 2015

  22. [22]

    AI Communications 30(1), pp

    Andreas Herzig & Faustine Maffre (2017): How to Share Knowledge by Gossiping. AI Communications 30(1), pp. 1–17, doi:10.3233/AIC-170723

    work page doi:10.3233/aic-170723 2017

  23. [23]

    Charles A. R. Hoare (1978): Communicating Sequential Processes. Commun. ACM 21(8), pp. 666–677, doi:10.1145/359576.359585

    work page doi:10.1145/359576.359585 1978

  24. [24]

    Texts in Theoretical Computer Science

    Juraj Hromkoviˇc, Ralf Klasing, Andrzej Pelc, Peter Ruzicka & Walter Unger (2005): Dissemination of Information in Communication Networks - Broadcasting, Gossiping, Leader Election, and Fault-Tolerance. Texts in Theoretical Computer Science. An EATCS Series, Springer, doi:10.1007/b137871

    work page doi:10.1007/b137871 2005

  25. [25]

    In: Proc

    David Kempe, Alin Dobra & Johannes Gehrke (2003): Gossip-based computation of aggregate information. In: Proc. of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’03, IEEE, pp. 482–491, doi:10.1109/SFCS.2003.1238221

    work page doi:10.1109/sfcs.2003.1238221 2003

  26. [26]

    Operating Systems Review 41(5), pp

    Anne-Marie Kermarrec & Maarten van Steen (2007): Gossiping in distributed systems. Operating Systems Review 41(5), pp. 2–7, doi:10.1145/1317379.1317381

    work page doi:10.1145/1317379.1317381 2007

  27. [27]

    ACM Transactions on Computer Systems (TOCS) 10(4), pp

    Rivka Ladin, Barbara Liskov, Liuba Shrira & Sanjay Ghemawat (1992): Providing high availabil- ity using lazy replication . ACM Transactions on Computer Systems (TOCS) 10(4), pp. 360–391, doi:10.1145/138873.138877

    work page doi:10.1145/138873.138877 1992

  28. [28]

    Lecture Notes in Computer Science92, Springer, doi:10.1007/3-540-10235-3

    Robin Milner (1980): A Calculus of Communicating Systems. Lecture Notes in Computer Science92, Springer, doi:10.1007/3-540-10235-3

    work page doi:10.1007/3-540-10235-3 1980

  29. [29]

    ACM Trans

    Davide Sangiorgi (2009): On the origins of bisimulation and coinduction. ACM Trans. Program. Lang. Syst. 31(4), pp. 15:1–15:41, doi:10.1145/1516507.1516510

    work page doi:10.1145/1516507.1516510 2009

  30. [30]

    In: International Conference on Foundations of Software Technology and Theoretical Computer Science, Springer, pp

    Holger Spakowski & J ¨org V ogel (2000): Θp 2-Completeness: A Classical Approach for New Results . In: International Conference on Foundations of Software Technology and Theoretical Computer Science, Springer, pp. 348–360, doi:10.1007/3-540-44450-5 28

    work page doi:10.1007/3-540-44450-5 2000

  31. [31]

    Nieuw Archief voor Wiskunde 3(XIX), pp

    Robert Tijdeman (1971): On a telephone problem. Nieuw Archief voor Wiskunde 3(XIX), pp. 188–192

    work page 1971

  32. [32]

    Theoretical Computer Science 51(1-2), pp

    Klaus W Wagner (1987): More complicated questions about maxima and minima, and some closures of NP. Theoretical Computer Science 51(1-2), pp. 53–80, doi:10.1016/0304-3975(87)90049-1

    work page doi:10.1016/0304-3975(87)90049-1 1987