nucleation

LIT-1213: Knowledge and common knowledge in a distributed environment

1 min read

Properties4
StatusActive — read 2026-10-29 (NOTE-1381) in full, from the authors' arXiv deposit of the JACM version; worth reading as the paper that makes "knowing" precise for processors in a system of runs and proves that guaranteed coordinated action needs common knowledge, that a channel which can lose any message cannot create it, and that any uncertainty in timing already rules it out, with weaker ε-, eventual and timestamped variants that are attainable. Read it knowing that the protocols are deterministic, that several results (the S5 properties, Theorems 11–12) are proved elsewhere or left to the reader, and that it credits the coordinated attack problem to Gray (1978) without citing Akkoyunlu et al. (1975).
Version2
Tagslogic, epistemology, network-science
Cited as “paper” byNOTE-1381 — Halpern and Moses — Knowledge and common knowledge in a distributed environment

Graph View

Halpern, J. Y. & Moses, Y. (1990). Knowledge and common knowledge in a distributed environment. Journal of the ACM 37(3): 549–587. doi:10.1145/79147.79161. First in Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing (PODC ‘84), pp. 50–61, doi:10.1145/800222.806735.

Read in full on 2026-10-29 (NOTE-1381), from the authors’ arXiv deposit (arXiv:cs/0006009).

Why this is here

A36 of the exchange used the coordinated-attack result, without a source, for the epistemic obstruction it separated from feasibility and aggregation. This is the paper that proves common knowledge unattainable over unreliable channels. Bears on CLAIM-346.

Backlinks