eprintid: 27700
rev_number: 8
eprint_status: archive
userid: 19147
dir: disk0/00/02/77/00
datestamp: 2018-12-10 13:26:25
lastmod: 2021-04-02 15:58:35
status_changed: 2018-12-10 13:26:25
type: article
metadata_visibility: show
creators_name: Herzig, Andreas
creators_name: Maffre, Faustine
creators_idrefppn: 074664794
creators_idrefppn: 199221677
title: How to share knowledge by gossiping
ispublished: pub
subjects: subjects_INFO
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.
date: 2017-03
date_type: published
publisher: IOS Press
id_number: 10.3233/AIC-170723
faculty: info
divisions: IRIT
keywords: Gossip protocol
keywords: epistemic logic
keywords: shared knowledge
keywords: common knowledge
keywords: theory of mind
keywords: dynamic epistemic logic
keywords: visibility
keywords: observability
language: en
has_fulltext: TRUE
view_date_year: 2017
full_text_status: public
publication: AI Communications
volume: vol. 30
number: n° 1
pagerange: 1-17
refereed: TRUE
issn: 0921-7126
oai_identifier: BibTeX_He2017.4
harvester_local_overwrite: subjects
harvester_local_overwrite: eprintid
harvester_local_overwrite: userid
harvester_local_overwrite: date
harvester_local_overwrite: dir
harvester_local_overwrite: edition
harvester_local_overwrite: publisher
harvester_local_overwrite: date_type
harvester_local_overwrite: language
harvester_local_overwrite: volume
harvester_local_overwrite: faculty
harvester_local_overwrite: book_title
harvester_local_overwrite: sub_title
harvester_local_overwrite: site
harvester_local_overwrite: divisions
harvester_local_overwrite: editors_name
harvester_local_overwrite: title
harvester_local_overwrite: type
harvester_local_overwrite: publication
harvester_local_overwrite: abstract
harvester_local_overwrite: place_of_pub
harvester_local_overwrite: pagerange
harvester_local_overwrite: creators_name
harvester_local_overwrite: refereed
harvester_local_overwrite: official_url
harvester_local_overwrite: keywords
harvester_local_overwrite: book_chapter
harvester_local_overwrite: number
harvester_local_overwrite: contributors_type
harvester_local_overwrite: ispublished
harvester_local_overwrite: issn
harvester_local_overwrite: id_number
harvester_local_overwrite: creators_idrefppn
site: ut1
citation:   Herzig, Andreas <https://www.idref.fr/074664794> and Maffre, Faustine <https://www.idref.fr/199221677>  (2017) How to share knowledge by gossiping.    AI Communications, vol. 30 (n° 1).  pp. 1-17.       
document_url: https://publications.ut-capitole.fr/id/eprint/27700/1/herzig.pdf