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.
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.
Supported in partVerified against the work's full text
Halpern and Moses show that coordinated action needs full common knowledge, not merely nested mutual knowledge, and note definite reference presupposes common knowledge; they say nothing of majorities or consensus algorithms.
“However, simultaneous coordinated attack requires common knowledge (as is shown in Proposition 4); nothing less will do.”
- 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.
SupportedVerified against the work's full text
Halpern and Moses show each delivered message adds only one knowledge level, so no finite message exchange in coordinated attack reaches common knowledge.
“However, each message that the messenger delivers can add at most one level of knowledge about the desired attack, and no more.”
- This is the content of the Coordinated Attack / two-generals result, where no finite exchange ever upgrades mutual to common knowledge.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 2 of 2 citations: 1 supported, 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:4f4fe0bc9133 · see in the full table