More Web Proxy on the site http://driver.im/

research-article

How to share knowledge by gossiping

Authors: Andreas Herzig, Faustine MaffreAuthors Info & Claims

AI Communications, Volume 30, Issue 1

Pages 1 - 17

https://doi.org/10.3233/AIC-170723

Published: 01 January 2017 Publication History

Abstract

We provide a logical investigation of a simple case of communication in a network of agents called the gossip problem. Its classical version is: given n agents each of which has a secret – a fact not known to anybody else –, how many calls does it take to achieve shared knowledge of all secrets, i.e., to reach a state where every agent knows every secret? Several protocols achieving shared knowledge in 2 ( n − 2 ) calls exist and were proved to be optimal: no shorter sequence of calls exists. We generalize that problem and focus on higher-order shared knowledge: how many calls does it take to obtain that everybody knows that everybody knows all secrets? More generally, how many calls does it take to obtain shared knowledge of order k? This cannot be achieved simply by communicating facts: the agents also have to communicate higher-order knowledge of facts. We give an algorithm that works in ( k + 1 ) ( n − 2 ) calls. We analyse its properties in a logic that we have investigated in previous work and that is based on the concept of observability of propositional variables by agents: Dynamic Epistemic Logic of Propositional Assignment and Observation DEL-PAO. This enables us in particular to give a formal proof of correctness of the algorithm.

References

[1]

E.A. Akkoyunlu, K. Ekanadham and R.V. Hubert, Some constraints and tradeoffs in the design of network communications, in: Proceedings of the 5th ACM Symposium on Operating Systems Principles, ACM Press, 1975, pp. 67–74.

[2]

R. Alur, T.A. Henzinger, F.Y.C. Mang, S. Qadeer, S.K. Rajamani and S. Tasiran, MOCHA: Modularity in model checking, in: Computer Aided Verification, 10th International Conference, CAV ’98, Proceedings, Vancouver, BC, Canada, June 28–July 2, 1998, A.J. Hu and M.Y. Vardi, eds, Lecture Notes in Computer Science, Vol. 1427, Springer, 1998, pp. 521–525.

[3]

K.R. Apt, D. Grossi and W. van der Hoek, Epistemic protocols for distributed gossiping, in: Proceedings Fifteenth Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2015, Carnegie Mellon University, Pittsburgh, USA, June 4–6, 2015, R. Ramanujam, ed., EPTCS, Vol. 215, 2015, pp. 51–66.

[4]

M. Attamah, H. van Ditmarsch, D. Grossi and W. van der Hoek, A framework for epistemic gossip protocols, in: Multi-Agent Systems – 12th European Conference, EUMAS 2014, Prague, Czech Republic, December 18–19, 2014, Revised Selected Papers, N. Bulling, ed., Lecture Notes in Computer Science, Vol. 8953, Springer, 2014, pp. 193–209.

[5]

M. Attamah, H. van Ditmarsch, D. Grossi and W. van der Hoek, Knowledge and gossip, in: Proceedings of 21st ECAI, 2014, pp. 21–26.

[6]

M. Attamah, H. van Ditmarsch, D. Grossi and W. van der Hoek, The pleasure of gossip, in: Rohit Parikh on Logic, Language and Society, L.M.C. Baskent and R. Ramanujam, eds, Springer, to appear.

[7]

G. Aucher and T. Bolander, Undecidability in epistemic planning, in: IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3–9, 2013, F. Rossi, ed., IJCAI/AAAI, 2013, pp. 27–33.

[8]

B. Baker and R. Shostak, Gossips and telephones, Discrete Mathematics 2(3) (1972), 191–193.

Digital Library

[9]

P. Balbiani, O. Gasquet and F. Schwarzentruber, Agents that look at one another, Logic Journal of the IGPL 21(3) (2013), 438–467.

[10]

A. Baltag and L.S. Moss, Logics for epistemic programs, Synthese 139(2) (2004), 165–224.

[11]

A. Baltag, L.S. Moss and S. Solecki, The logic of public announcements, common knowledge, and private suspicions, in: Proc. TARK’98, Morgan Kaufmann, 1998, pp. 43–56.

[12]

T. Bolander, Seeing is believing: Formalising false-belief tasks in dynamic epistemic logic, in: Proceedings of the European Conference on Social Intelligence (ECSI-2014), Barcelona, Spain, November 3–5, 2014, A. Herzig and E. Lorini, eds, CEUR Workshop Proceedings, Vol. 1283, 2014, pp. 87–107, CEUR-WS.org.

[13]

T. Bolander and M.B. Andersen, Epistemic planning for single and multi-agent systems, Journal of Applied Non-Classical Logics 21(1) (2011), 9–34.

[14]

T. Charrier, A. Herzig, E. Lorini and F. Schwarzentruber, Building epistemic logic from observations and public announcements, in: International Conference on Principles of Knowledge Representation and Reasoning (KR), Cape Town, AAAI Press, 2016, pp. 268–277, http://www.aaai.org/Press/press.php.

[15]

T. Charrier, B. Maubert and F. Schwarzentruber, On the impact of modal depth in epistemic planning, in: Kambhampati [28], pp. 1030–1036.

[16]

T. Charrier and F. Schwarzentruber, Arbitrary public announcement logic with mental programs, in: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, Istanbul, Turkey, May 4–8, 2015, G. Weiss, P. Yolum, R.H. Bordini and E. Elkind, eds, ACM, 2015, pp. 1471–1479.

[17]

M.C. Cooper, A. Herzig, F. Maffre, F. Maris and P. Régnier, A simple account of multi-agent epistemic planning, in: Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), 2016, pp. 193–201.

[18]

M.C. Cooper, A. Herzig, F. Maffre, F. Maris and P. Régnier, Simple epistemic planning: Generalised gossiping, in: Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), 2016, pp. 1563–1564.

[19]

R. Fagin, J.Y. Halpern, Y. Moses and M.Y. Vardi, Reasoning About Knowledge, MIT Press, 1995.

[20]

O. Gasquet, V. Goranko and F. Schwarzentruber, Big brother logic: Logical modeling and reasoning about agents equipped with surveillance cameras in the plane, in: Proceedings of the 10th International Conference on Autonomous Agents and Multi-Agent Systems, AAMAS ’14, A.L.C. Bazzan, M.N. Huhns, A. Lomuscio and P. Scerri, eds, IFAAMAS/ACM, 2014, pp. 325–332.

[21]

J. Gerbrandy, Bisimulations on Planet Kripke, PhD thesis, University of Amsterdam, 1999.

[22]

J. Gerbrandy and W. Groeneveld, Reasoning about information change, J. of Logic, Language and Information 6(2) (1997).

Digital Library

[23]

S. Ghosh, T. Halder, K. Sharma and R. Verbrugge, Human strategic reasoning in dynamic games: Experiments, logics, cognitive models, in: van der Hoek et al. [34], pp. 116–128.

[24]

A. Hajnal, E.C.B. Milner and E. Szemerédi, A cure for the telephone disease, Canadian Mathematical Bulletin 15(3) (1972), 447–450.

[25]

A. Herzig, E. Lorini and F. Maffre, A poor man’s epistemic logic based on propositional assignment and higher-order observation, in: International Conference on Logic, Rationality and Interaction (LORI), Taipei, October 28–31, 2015, LNCS, Vol. 9394, Springer Verlag, 2015, pp. 156–168.

[26]

A. Herzig, E. Lorini, F. Maffre and F. Schwarzentruber, Epistemic boolean games based on a logic of visibility and control, in: Kambhampati [28], pp. 1116–1122.

[27]

C.A.J. Hurkens, Spreading gossip efficiently, Nieuw Archief voor Wiskunde 5/1(2) (2000), 208–210.

[28]

S. Kambhampati (ed.), Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9–15 July 2016, IJCAI/AAAI Press, 2016.

[29]

F. Maffre, Ignorance is bliss: observability-based dynamic epistemic logics and their applications, PhD thesis, Ecole doctorale Math., Info. et Télécom. de Toulouse, 2016.

[30]

K. Su, A. Sattar and X. Luo, Model checking temporal logics of knowledge via OBDDs, Comput. J. 50(4) (2007), 403–420.

Digital Library

[31]

R. Tijdeman, On a telephone problem, Nieuw Archief voor Wiskunde 19(3) (1971), 188–192.

[32]

H. van Ditmarsch, D. Grossi, A. Herzig, W. van der Hoek and L.B. Kuijer, Parameters for epistemic gossip problems, in: Proc. LOFT 2016, 2016.

[33]

J. van Benthem, J. van Eijck, M. Gattinger and K. Su, Symbolic model checking for dynamic epistemic logic, in: van der Hoek et al. [34], pp. 366–378.

[34]

W. van der Hoek, W.H. Holliday and W. Wang (eds), Logic, Rationality, and Interaction – 5th International Workshop, LORI 2015, Proceedings, Taipei, Taiwan, October 28–31, 2015, Lecture Notes in Computer Science, Vol. 9394, Springer, 2015.

[35]

W. van der Hoek, P. Iliev and M. Wooldridge, A logic of revelation and concealment, in: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, W. van der Hoek, L. Padgham, V. Conitzer and M. Winikoff, eds, IFAAMAS, 2012, pp. 1115–1122.

[36]

W. van der Hoek, N. Troquard and M. Wooldridge, Knowledge and control, in: Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems, L. Sonenberg, P. Stone, K. Tumer and P. Yolum, eds, IFAAMAS, 2011, pp. 719–726.

[37]

H. van Ditmarsch, W. van der Hoek and B. Kooi, Dynamic Epistemic Logic, 1st edn, Springer Publishing Company, Incorporated, 2007.

[38]

H. van Ditmarsch, J. van Eijck, P. Pardo, R. Ramezanian and F. Schwarzentruber, Dynamic gossip, CoRR (2015),.

Cited By

van Ditmarsch HGattinger MRamezanian R(2023)Everyone Knows That Everyone Knows: Gossip Protocols for Super ExpertsStudia Logica10.1007/s11225-022-10032-3111:3(453-499)Online publication date: 30-Jan-2023
https://dl.acm.org/doi/10.1007/s11225-022-10032-3
van Ditmarsch HGattinger M(2022)The Limits to Gossip: Second-Order Shared Knowledge of All Secrets is UnsatisfiableLogic, Language, Information, and Computation10.1007/978-3-031-15298-6_15(237-249)Online publication date: 20-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-15298-6_15
Livesey JWojtczak D(2021)Minimal Number of Calls in Propositional ProtocolsReachability Problems10.1007/978-3-030-89716-1_9(132-148)Online publication date: 25-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-89716-1_9
Show More Cited By

Index Terms

How to share knowledge by gossiping
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Cooperation and coordination
      2. Multi-agent systems
2. Theory of computation

Index terms have been assigned to the content through auto-classification.

Recommendations

Quantified Announcements and Common Knowledge
AAMAS '21: Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems

Public announcement logic (PAL) extends multi-agent epistemic logic with dynamic operators modelling the effects of public communication. Allowing quantification over public announcements lets us reason about theexistence of an announcement to reach a ...
Justified common knowledge
Clifford lectures and the mathematical foundations of programming semantics

In this paper we introduce the justified knowledge operator J with the intended meaning of J ϕ as 'there is a justification for ϕ.' Though justified knowledge appears here in a case study of common knowledge systems, a similar approach is applicable in ...
Quantifying over information change with common knowledge
Abstract
Public announcement logic (PAL) extends multi-agent epistemic logic with dynamic operators modelling the effects of public communication. Allowing quantification over public announcements lets us reason about the existence of an announcement that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image AI Communications

AI Communications Volume 30, Issue 1

2017

98 pages

ISSN:0921-7126

Issue’s Table of Contents

IOS Press and the authors. All rights reserved.

Publisher

IOS Press

Netherlands

Publication History

Published: 01 January 2017

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

van Ditmarsch HGattinger MRamezanian R(2023)Everyone Knows That Everyone Knows: Gossip Protocols for Super ExpertsStudia Logica10.1007/s11225-022-10032-3111:3(453-499)Online publication date: 30-Jan-2023
https://dl.acm.org/doi/10.1007/s11225-022-10032-3
van Ditmarsch HGattinger M(2022)The Limits to Gossip: Second-Order Shared Knowledge of All Secrets is UnsatisfiableLogic, Language, Information, and Computation10.1007/978-3-031-15298-6_15(237-249)Online publication date: 20-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-15298-6_15
Livesey JWojtczak D(2021)Minimal Number of Calls in Propositional ProtocolsReachability Problems10.1007/978-3-030-89716-1_9(132-148)Online publication date: 25-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-89716-1_9
Livesey JWojtczak D(2021)Propositional Gossip ProtocolsFundamentals of Computation Theory10.1007/978-3-030-86593-1_25(354-370)Online publication date: 12-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-86593-1_25
Apt KWojtczak D(2018)Verification of distributed epistemic gossip protocolsJournal of Artificial Intelligence Research10.1613/jair.1.1120462:1(101-132)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1613/jair.1.11204
Apt KKopczynski EWojtczak D(2017)On the computational complexity of gossip protocolsProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171642.3171752(765-771)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171642.3171752

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents