On interactive knowledge with bounded communication

Journal of Applied Non-Classical Logics 21 (3-4):323-354 (2011)
  Copy   BIBTEX


The effect of upper bounds on message delivery times in a computer network upon the dynamics of knowledge gain is investigated. Recent work has identified centipedes and brooms—causal structures that combine message chains with time bound information—as necessary conditions for knowledge gain and common knowledge gain, respectively. This paper shows that, under the full-information protocol, these structures are both necessary and sufficient for such epistemic gain. We then apply this analysis to gain insights into the relation between “everyone knows” and common knowledge. We prove a tight threshold on the depth k, beyond which Ek G (everyone in G knows nested to depth k) collapses into CG (common knowledge), when this knowledge concerns the occurrence of a spontaneous event. The threshold depends on the size of the group G of agents, as well as the time that has elapsed since the event of interest occurred. The existence of such a threshold is not guaranteed for all protocols, which is demonstrated here by presenting a counterexample in which no such threshold exists.



    Upload a copy of this work     Papers currently archived: 92,323

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles


Added to PP

31 (#519,270)

6 months
1 (#1,478,551)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Ido Ben-Zvi
Technion, Israel Institute of Technology

Citations of this work

Agent-time epistemics and coordination.Ido Ben-Zvi & Yoram Moses - 2013 - In Kamal Lodaya (ed.), Logic and its Applications. Springer. pp. 97--108.

Add more citations

References found in this work

Convention: A Philosophical Study.David Kellogg Lewis - 1969 - Cambridge, MA, USA: Wiley-Blackwell.
Convention: A Philosophical Study.David Lewis - 1969 - Synthese 26 (1):153-157.
Convention: A Philosophical Study.David K. Lewis - 1971 - Philosophy and Rhetoric 4 (2):137-138.
Dynamic Epistemic Logic.Hans van Ditmarsch, Wiebe van der Hoek & Barteld Kooi - 2016 - Internet Encyclopedia of Philosophy.

View all 12 references / Add more references