The DOI matches its Crossref record; 33 of the 33 references it cites were found in a registry or an index.
Knowledge and common knowledge in a distributed environment
Open accessAbstract
Reasoning about knowledge seems to play a fundamental role in distributed systems. Indeed, such reasoning is a central part of the informal intuitive arguments used in the design of distributed protocols. Communication in a distributed system can be viewed as the act of transforming the system's state of knowledge. This paper presents a general framework for formalizing and reasoning about knowledge in distributed systems. It is shown that states of knowledge of groups of processors are useful concepts for the design and analysis of distributed protocols. In particular, distributed knowledge corresponds to knowledge that is “distributed” among the members of the group, while common knowledge corresponds to a fact being “publicly known.” The relationship between common knowledge and a variety of desirable actions in a distributed system is illustrated. Furthermore, it is shown that, formally speaking, in practical systems common knowledge cannot be attained. A number of weaker variants of common knowledge that are attainable in many cases of interest are introduced and investigated.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Impossibility of distributed consensus with one faulty process
Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985) · Journal of the ACM · doi:10.1145/3149.214121 · Cited by 4,579
A lattice-theoretical fixpoint theorem and its applications
Tarski, A. (1955) · Pacific Journal of Mathematics · doi:10.2140/pjm.1955.5.285 · Cited by 2,704
Proceedings of the 16th international joint conference on Artificial Intelligence - IJCAI '99
Colton, S., Bundy, A., & Walsh, T. (1999) · Cited by 2,500
Distributed snapshots: determining global states of distributed systems
Chandy, K. M., & Lamport, L. (1985) · ACM Transactions on Computer Systems · doi:10.1145/214451.214456 · Cited by 2,443
Results on the propositional μ-calculus
Kozen, D. C. (1983) · Theoretical Computer Science · doi:10.1016/0304-3975(82)90125-6 · Cited by 1,881
Aumann, R. J. (1976) · The Annals of Statistics · doi:10.1214/aos/1176343654 · Cited by 1,573
Hintikka, J. (1962) · Cited by 1,536
Definite reference and mutual knowledge
Clark, H. H. (1981) · Medical Entomology and Zoology · Cited by 1,443
Elements of Discourse Understanding
MacWhinney, B., Joshi, A. K., Webber, B. L., & Sag, I. A. (1983) · Language · doi:10.2307/414072 · Cited by 1,309
Belief, awareness, and limited reasoning
Fagin, R., & Halpern, J. Y. (1987) · Artificial Intelligence · doi:10.1016/0004-3702(87)90003-8 · Cited by 885
Self-citationFormal Theories of the Commonsense World
Hobbs, J. R., & Moore, R. C. (1985) · Greenwood Publishing Group Inc. eBooks · Cited by 770
Using branching time temporal logic to synthesize synchronization skeletons
Emerson, E. A., & Clarke, E. M. (1982) · Science of Computer Programming · doi:10.1016/0167-6423(83)90017-5 · Cited by 660
A logic of implicit and explicit belief
Levesque, H. J. (1984) · Cited by 560
Synthesis of Communicating Processes from Temporal Logic Specifications
Manna, Z., & Wolper, P. (1984) · ACM Transactions on Programming Languages and Systems · doi:10.1145/357233.357237 · Cited by 526
A Formal Theory of Knowledge and Action
Moore, R. C. (1984) · Defense Technical Information Center (DTIC) · Cited by 512
Barwise, J. (1981) · The Journal of Philosophy · doi:10.2307/2026481 · Cited by 425
THE SYNTHESIS OF DIGITAL MACHINES WITH PROVABLE EPISTEMIC PROPERTIES
Rosenschein, S. J., & Kaelbling, L. P. (1986) · Theoretical Aspects of Reasoning About Knowledge · doi:10.1016/b978-0-934613-04-0.50009-0 · Cited by 282
Early stopping in Byzantine agreement
Dolev, D., Reischuk, R., & Strong, H. R. (1990) · Journal of the ACM · doi:10.1145/96559.96565 · Cited by 246
Chandy, K. M., & Misra, J. (1986) · Distributed Computing · doi:10.1007/bf01843569 · Cited by 218
Formal theories of knowledge in AI and robotics
Rosenschein, S. J. (1985) · New Generation Computing · doi:10.1007/bf03037076 · Cited by 177
A guide to the modal logics of knowledge and belief: preliminary draft
Halpern, J. Y., & Moses, Y. (1985) · International Joint Conference on Artificial Intelligence · Cited by 171
Self-citationProgramming simultaneous actions using common knowledge
Moses, Y., & Tuttle, M. R. (1988) · Algorithmica · doi:10.1007/bf01762112 · Cited by 171
Self-citationDistributed processes and the logic of knowledge
Parikh, R., & Ramanujam, R. (1985) · Lecture notes in computer science · doi:10.1007/3-540-15648-8_21 · Cited by 159
On the possibility and impossibility of achieving clock synchronization
Dolev, D., Halpern, J. Y., & Strong, H. R. (1986) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(86)90028-0 · Cited by 139
Self-citationA formal model of knowledge, action, and communication in distributed systems
Halpern, J. Y., & Fagin, R. (1985) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/323596.323617 · Cited by 86
Self-citationCheating husbands and other stories: A case study of knowledge, action, and communication
Moses, Y., Dolev, D., & Halpern, J. Y. (1986) · Distributed Computing · doi:10.1007/bf01661170 · Cited by 78
Self-citationUsing Reasoning About Knowledge to Analyze Distributed Systems
Halpern, J. Y. (1987) · Annual Review of Computer Science · doi:10.1146/annurev.cs.02.060187.000345 · Cited by 74
Self-citationKnowledge and Common Knowledge in a Byzantine Environment I: Crash failures
Dwork, C., & Moses, Y. (1986) · Elsevier eBooks · doi:10.1016/b978-0-934613-04-0.50013-2 · Cited by 69
Self-citationFOUNDATIONS OF KNOWLEDGE FOR DISTRIBUTED SYSTEMS
Fischer, M. J., & Immerman, N. (1986) · Elsevier eBooks · doi:10.1016/b978-0-934613-04-0.50014-4 · Cited by 61
The Logic of Distributed Protocols
Ladner, R. E., & Reif, J. H. (1986) · Elsevier eBooks · doi:10.1016/b978-0-934613-04-0.50016-8 · Cited by 61
'Eventual' is earlier than 'immediate'
Dolev, D., Reischuk, R., & Strong, H. R. (1982) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1982.51 · Cited by 57
Substituting for real time and common knowledge in asynchronous distributed systems
Neiger, G., & Toueg, S. (1987) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/41840.41864 · Cited by 41
What can machines know? On the epistemic properties of machines
Fagin, R., Halpern, J. Y., & Vardi, M. Y. (1986) · Cited by 21
Self-citation
Cited by
(1994) · Mathematical Social Sciences · doi:10.1016/0165-4896(94)90005-1 · Cited by 3,517
Toward a mechanistic psychology of dialogue.
Pickering, M. J., & Garrod, S. (2004) · Behavioral and Brain Sciences · doi:10.1017/s0140525x04000056 · Cited by 2,678
EMERSON, E. A. (1990) · Formal Models and Semantics · doi:10.1016/b978-0-444-88074-1.50021-4 · Cited by 2,585
Burrows, M., Abadi, M., & Needham, R. (1990) · ACM Transactions on Computer Systems · doi:10.1145/77648.77649 · Cited by 2,523
Unreliable failure detectors for reliable distributed systems
Chandra, T. D., & Toueg, S. (1996) · Journal of the ACM · doi:10.1145/226643.226647 · Cited by 2,513
Metadata
- Authors
- Halpern, J. Y., & Moses, Y.
- Venue
- Journal of the ACM
- Published
- 1990-07
- Volume
- 37
- Issue
- 3
- Pages
- 549-587
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2022205872
- Cited by
- 955
- References
- 33
- FWCI
- 41.51
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.