The epistemic gossip problem
| Autor: | Faustine Maffre, Martin C. Cooper, Frédéric Maris, Andreas Herzig, Pierre Régnier |
|---|---|
| Přispěvatelé: | Institut National Polytechnique de Toulouse - INPT (FRANCE), Centre National de la Recherche Scientifique - CNRS (FRANCE), Université Toulouse III - Paul Sabatier - UT3 (FRANCE), Université Toulouse - Jean Jaurès - UT2J (FRANCE), Université Toulouse 1 Capitole - UT1 (FRANCE), Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse III - Paul Sabatier (UT3), Logique, Interaction, Langue et Calcul (IRIT-LILaC), Centre National de la Recherche Scientifique (CNRS), Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
Logique en informatique Communication protocol Counterintuitive Complete graph [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] 0102 computer and information sciences 02 engineering and technology 01 natural sciences ComputingMethodologies_ARTIFICIALINTELLIGENCE Theoretical Computer Science Epistemology Graph theory 010201 computation theory & mathematics Gossip Parallel communication 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Graph (abstract data type) 020201 artificial intelligence & image processing Epistemic logic Mathematics |
| Zdroj: | Discrete Mathematics Discrete Mathematics, Elsevier, 2019, 342 (3), pp.654-663. ⟨10.1016/j.disc.2018.10.041⟩ |
| ISSN: | 0012-365X |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect