OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

How to share knowledge by gossiping

Herzig, Andreas and Maffre, Faustine How to share knowledge by gossiping. (2016) In: 13th International Conference on Agreement Technologies in European Conference on Multi-Agent Systems (EUMAS/AT 2015), 17 December 2015 - 18 December 2015 (Athens, Greece).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1007/978-3-319-33509-4


Given n agents each of which has a secret (a fact not known to anybody else), the classical version of the gossip problem is to achieve shared knowledge of all secrets in a minimal number of phone calls. There exist protocols achieving shared knowledge in 2(n−2) calls: when the protocol terminates everybody knows all the secrets. 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 requires not only the communication of secrets, but also the communication of knowledge about secrets. We give a protocol that works in (k+1)(n−2) steps and prove that it is correct: it achieves shared knowledge of level k. The proof is presented in a dynamic epistemic logic that is based on the observability of propositional variables by agents.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to Springer editor. This papers appears in Volume 9571 of Lecture Notes in Computer Science ISSN : 0302-9743 ISBN: 978-3-319-33509-4 The original PDF is available at: https://link.springer.com/chapter/10.1007%2F978-3-319-33509-4_20
HAL Id:hal-01567082
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Laboratory name:
Deposited On:05 Jul 2017 09:42

Repository Staff Only: item control page