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. (2017) AI Communications, 30 (1). 1-17. ISSN 0921-7126

(Document in English)

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

Official URL: http://doi.org/10.3233/AIC-170723


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.

Item Type:Article
Additional Information:https://content.iospress.com/articles/ai-communications/aic723
HAL Id:hal-03512916
Audience (journal):International peer-reviewed journal
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:08 Nov 2018 09:27

Repository Staff Only: item control page