You can only be lucky once: optimal gossip for epistemic goals

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+(ⁿ₂) calls are optimal to reach “everyone knows that everyone knows all secrets.”