Knowledge and Common Knowledge in a Distributed Environment

Halpern, J. Y., & Moses, Y. (1990). Knowledge and Common Knowledge in a Distributed Environment. Journal of the ACM, 37(3), 549-587.

Type

Journal article

Intellectual base

Primary research

Year

1990

DOI

10.1145/79147.79161

Link

https://doi.org/10.1145/79147.79161

Cited from

cognitive_science, economics_finance

Cited by

2 citations across 2 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Common Ground
  • Linguistic pragmatics and conversation analysis: anaphora ("she"), definite reference ("the meeting"), ellipsis ("yes, on Tuesday"), and presupposition triggers all draw on a stabilised body of mutually recognised propositions; grounding theory describes how that body is built turn by turn. Distributed systems and consensus: consensus algorithms ensure that a committed value is not merely known to a majority but known to be known to a majority — the "common knowledge problem" is the formal version of common ground, and acting on merely mutually-known state is unsafe.
• Common Knowledge
  • This is the content of the Coordinated Attack / two-generals result, where no finite exchange ever upgrades mutual to common knowledge.

    This sourceFormalizes the hierarchy of nested knowledge and proves the coordinated-attack impossibility — no finite message exchange over a lossy channel attains common knowledge.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:4f4fe0bc9133 · see in the full table