OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

The epistemic gossip problem

Cooper, Martin and Herzig, Andreas and Maffre, Faustine and Maris, Frédéric and Régnier, Pierre The epistemic gossip problem. (2019) Discrete Mathematics, 342 (3). 654-663. ISSN 0012-365X

(Document in English)

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

Official URL: https://doi.org/10.1016/j.disc.2018.10.041


In the gossip problem information (‘secrets’) must be shared among a certain number of agents using the minimum number of calls. We extend the gossip problem to arbitrary epistemic depths. For example, we may require not only that all agents know all secrets but also that all agents know that all agents know all secrets. We give optimal protocols for various versions of this epistemic gossip problem, depending on the graph of communication links, in the case of two-way communication, one-way communication and parallel communication. We show, among other things, that increasing epistemic depth from 1 (all agents know all secrets) to 2 (so that all agents know that all agents know all secrets) does not double the required number of calls but increases this number by 3/2 (for a complete graph). We also show that the following counterintuitive result generalises to the epistemic gossip problem: asymptotically the same number of calls are required whether calls are two-way or one-way.

Item Type:Article
Additional Information:https://www.sciencedirect.com/science/article/pii/S0012365X18303753
HAL Id:hal-02147986
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:10 May 2019 13:12

Repository Staff Only: item control page