Abstract It is known that without synchronization via a global clock one cannot obtain common knowledge by communication. Moreover, it is folklore that without communicating higher-level information one cannot obtain arbitrary higher-order shared knowledge. Here, we make this result precise in the setting of gossip where agents make one-to-one telephone calls to share secrets: we prove that “everyone knows that everyone knows that everyone knows all secrets” is unsatisfiable in a logic of knowledge for gossiping. We also prove that, given n agents, $2n-3$ calls are optimal to reach “someone knows that everyone knows all secrets” and that $n - 2 + \binom{n}{2}$ calls are optimal to reach “everyone knows that everyone knows all secrets.”

We study wireless ad-hoc networks from an agent-based perspective. In our model agents with different strategies such as being selfish, tit-for-tat or battery-based compete and cooperate. If only different levels of selfishness are allowed then being selfish is clearly the dominant strategy. However, introduction of more advanced strategies allows to some extent to combat selfishness. In particular we present a battery-based approach and a hybrid of battery-based and tit-for-tat approaches. The findings give hope that the introduction of widely available ad-hoc networks might at some point be possible. Even when users are given full control of their devices, effective strategies allow for the networks overall to be effective and feasible.

Dynamic Epistemic Logic (DEL) can model complex information scenarios in a way that appeals to logicians. However, existing DEL implementations are ad-hoc, so we do not know how the framework really performs. For this purpose, we want to hook up with the best available model checking and SAT techniques in computational logic. We do this by first providing a bridge: a new faithful representation of DEL models as so-called knowledge structures that allow for symbolic model checking. For more complex epistemic change we introduce knowledge transformers analogous to action models. Next, we show that we can now solve well-known benchmark problems in epistemic scenarios much faster than with existing methods for DEL. We also compare our approach to model checking for temporal logics. Finally, we show that our method is not just a matter of implementation, but that it raises significant issues about logical representation and update.