article

Knowledge-based programs

Authors:

Joseph Y. Halpern,

Moshe Y. VardiAuthors Info & Claims

Distributed Computing, Volume 10, Issue 4

Pages 199 - 225

https://doi.org/10.1007/s004460050038

Published: 01 July 1997 Publication History

Abstract

Reasoning about activities in a distributed computer system at the level of the knowledge of individuals and groups allows us to abstract away from many concrete details of the system we are considering. In this paper, we make use of two notions introduced in our recent book to facilitate designing and reasoning about systems in terms of knowledge. The first notion is that of a knowledge-based program. A knowledge-based program is a syntactic object: a program with tests for knowledge. The second notion is that of a context, which captures the setting in which a program is to be executed. In a given context, a standard program (one without tests for knowledge) is represented by (i.e., corresponds in a precise sense to) a unique system. A knowledge-based program, on the other hand, may be represented by no system, one system, or many systems. In this paper, we provide a sufficient condition for a knowledge-based program to be represented in a unique way in a given context. This condition applies to many cases of interest, and covers many of the knowledge-based programs considered in the literature. We also completely characterize the complexity of determining whether a given knowledge-based program has a unique representation, or any representation at all, in a given finite-state context.

References

[1]

1. Abadi M, Lamport L: The existence of refinement mappings. Theor Comput Sci 82(2): 253-284 (1991).

Digital Library

[2]

2. Barwise J: Scenes and other situations. J Phil 78(7): 369-397 (1981).

[3]

3. Chandy KM, Misra J: Parallel program design: a foundation. Addison-Wesley, Reading, MA 1988.

[4]

4. Choueka Y: Theories of automata on ω-tapes: a simplified approach. J Comput Syst Sci 8: 117-141 (1974).

Digital Library

[5]

5. Clarke EM, Emerson EA, Sistla AP: Automatic verification of finite-state concurrent systems using temporal logic specifications. ACM Trans Prog Lang Syst 8(2): 244-263 (1986) {An early version appeared in: Proc 10th ACM Symposium on Principles of Programming Languages (1983)}.

Digital Library

[6]

6. Dwork C, Moses Y: Knowledge and common knowledge in a Byzantine environment: crash failures. Inform Comput 88(2): 156-186 (1990).

Digital Library

[7]

7. Fagin R, Halpern JY, Moses Y, Vardi MY: An operational semantics for knowledge bases. In: Proc National Conference on Artificial Intelligence (AAAI '94), pp 1142-1144 (1994).

[8]

8. Fagin R, Halpern JY, Moses Y, Vardi MY: Reasoning about knowledge. MIT Press, Cambridge, MA 1995.

[9]

9. Fudenberg D, Tirole J: Game theory. MIT Press, Cambridge, MA 1991.

[10]

10. Garey M, Johnson DS: Computers and intractability: A guide to the theory of NP-completeness. Freeman, San Francisco, CA 1979.

[11]

11. Halpern JY, Fagin R: A formal model of knowledge, action, and communication in distributed systems: preliminary report. In: Proc 4th ACM Symp on Principles of Distributed Computing, pp 224-236 (1985).

Digital Library

[12]

12. Halpern JY, Fagin R: Modelling knowledge and action in distributed systems. Distrib Comput 3(4): 159-179 (1989). {A preliminary version appeared in: Proc 4th ACM Symposium on Principles of Distributed Computing (1985) with the title "A formal model of knowledge, action, and communication in distributed systems: preliminary report"}.

Digital Library

[13]

13. Halpern JY, Moses Y: Knowledge and common knowledge in a distributed environment. J ACM 37(3): 549-587 (1990). {A preliminary version appeared in: Proc 3rd ACM Symposium on Principles of Distributed Computing (1984)}.

Digital Library

[14]

14. Halpern JY, Moses Y: A guide to completeness and complexity for modal logics of knowledge and belief. Artif Intell 54: 319-379 (1992).

Digital Library

[15]

15. Halpern JY, Moses Y, Waarts O: A characterization of eventual Byzantine agreement. In: Proc 9th ACM Symp on Principles of Distributed Computing, pp 333-346 (1990).

Digital Library

[16]

16. Halpern JY, Zuck LD: A little knowledge goes a long way: knowledge-based derivations and correctness proofs for a family of protocols. J ACM 39(9): 449-478 (1992).

Digital Library

[17]

17. Jerrum MR, Valiant LG, Vazirani VV: Random generation of combinatorial structures from a uniform distribution. Theoret Comput Sci 43: 169-188 (1986).

Digital Library

[18]

18. Katz S, Taubenfeld G: What processes know: definitions and proof methods. In: Proc 5th ACM Symp on Principles of Distributed Computing, pp 249-262 (1986).

Digital Library

[19]

19. Kurki-Suonio R: Towards programming with knowledge expressions. In: Proc. 13th ACM Symp on Principles of Programming Languages, pp 140-149 (1986).

Digital Library

[20]

20. Manna Z, Pnueli A: The temporal logic of reactive and concurrent systems, vol 1. Springer, Berlin Heidelberg New York 1992.

[21]

21. Mazer MS: Implementing distributed knowledge-based protocols. Submitted for publication (1991).

[22]

22. Moses Y: Resource-bound knowledge. In: Vardi MY (ed) Proc Second Conference on Theoretical Aspects of Reasoning about Knowledge, pp 261-276. Morgan Kaufmann, San Francisco, CA 1988.

[23]

23. Moses Y, Kislev O: Knowledge-oriented programming. In: Proc 12th ACM Symp. on Principles of Distributed Computing, pp 261-270 (1993).

[24]

24. Moses Y, Tuttle MR: Programming simultaneous actions using common knowledge. Algorithmica 3: 121-169 (1988).

Digital Library

[25]

25. Neiger G: Knowledge consistency: a useful suspension of disbelief. In: Vardi MY (ed) Proc. Second Conference on Theoretical Aspects of Reasoning about Knowledge, pp 295-308, Morgan Kaufmann, San Francisco, CA 1988.

[26]

26. Neiger G, Bazzi R: Using knowledge to optimally achieve coordination in distributed systems. In: Moses Y (ed) Theoretical aspects of reasoning about knowledge: Proc Fourth Conference, pp 43-59. Morgan Kaufmann, San Francisco, CA 1992.

[27]

27. Neiger G, Toueg S: Simulating real-time clocks and common knowledge in distributed systems. J ACM 40(2): 334-367 (1993).

Digital Library

[28]

28. Owicki S, Lamport L: Proving liveness properties of concurrent programs. ACM Trans. Progr Lang Syst 4(3): 455-495 (1982).

Digital Library

[29]

29. Papadimitriou CH, Yanakakis M: The complexity of facets (and some facets of complexity). J Comput Syst Sci 28(2): 244-259 (1982).

[30]

30. Sanders B: A predicate transformer approach to knowledge and knowledge-based protocols. In: Proc 10th ACM Symp on Principles of Distributed Computing, pp 217-230 (1991). {A revised report appears as: ETH Informatik Technical Report 181 (1992)}.

[31]

31. Savitch WJ: Relationships between nondeterministic and deterministic tape complexities. J Comput Syst Sci 4: 177-192 (1970).

Digital Library

[32]

32. Shoham Y: Agent oriented programming. Artif Intell 60(1): 51-92 (1993).

Digital Library

[33]

33. Sistla AP, Clarke EM: The complexity of propositional linear temporal logics. J ACM 32(3): 733-749 (1985).

Digital Library

[34]

34. Vardi MY, Wolper P: An automata-theoretic approach to automatic program verification. In: Proc 1st IEEE Symp on Logic in Computer Science, pp 332-344 (1986).

[35]

35. Vardi MY, Wolper P: Reasoning about infinite computations. Inform Comput 115(1): 1-37 (1994).

Digital Library

Cited By

Huang XPeng BZhao XAlbrecht SWoolridge M(2022)Dependable learning-enabled multiagent systemsAI Communications10.3233/AIC-22012835:4(407-420)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.3233/AIC-220128
Gurov DGoranko VLundberg E(2022)Knowledge-based strategies for multi-agent teams playing against NatureArtificial Intelligence10.1016/j.artint.2022.103728309:COnline publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.artint.2022.103728
van Ditmarsch HGalmiche DGawek M(2022)An Epistemic Separation Logic with Action ModelsJournal of Logic, Language and Information10.1007/s10849-022-09372-z32:1(89-116)Online publication date: 10-Aug-2022
https://dl.acm.org/doi/10.1007/s10849-022-09372-z
Show More Cited By

Index Terms

Knowledge-based programs
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Multi-agent systems
    2. Knowledge representation and reasoning
  2. Machine learning
    1. Learning settings
2. Theory of computation
  1. Logic

Recommendations

Knowledge acquisition for knowledge-based engineering systems

This paper is essentially concerned with the development of formal representations of knowledge required prior to the development of knowledge-based engineering systems (KBESs). Initially, the paper provides a brief introduction to knowledge-based ...
Eliciting Knowledge and Transferring It Effectively to a Knowledge-Based System

The knowledge acquisition bottleneck impeding the development of expert systems is being alleviated by the development of computer-based knowledge acquisition tools. These work directly with experts to elicit knowledge, and structure it appropriately to ...
Implementing knowledge-based programs
TARK '96: Proceedings of the 6th conference on Theoretical aspects of rationality and knowledge

Reasoning about multi-agents systems at the <i>knowledge level</i> allows us to abstract away from many concrete details of the systems we are considering. Fagin et al. introduced two notions to facilitate designing and reasoning about systems in terms ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Distributed Computing

Distributed Computing Volume 10, Issue 4

July 1997

58 pages

ISSN:0178-2770

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 July 1997

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Huang XPeng BZhao XAlbrecht SWoolridge M(2022)Dependable learning-enabled multiagent systemsAI Communications10.3233/AIC-22012835:4(407-420)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.3233/AIC-220128
Gurov DGoranko VLundberg E(2022)Knowledge-based strategies for multi-agent teams playing against NatureArtificial Intelligence10.1016/j.artint.2022.103728309:COnline publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.artint.2022.103728
van Ditmarsch HGalmiche DGawek M(2022)An Epistemic Separation Logic with Action ModelsJournal of Logic, Language and Information10.1007/s10849-022-09372-z32:1(89-116)Online publication date: 10-Aug-2022
https://dl.acm.org/doi/10.1007/s10849-022-09372-z
Livesey JWojtczak D(2021)Minimal Number of Calls in Propositional ProtocolsReachability Problems10.1007/978-3-030-89716-1_9(132-148)Online publication date: 25-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-89716-1_9
Livesey JWojtczak D(2021)Propositional Gossip ProtocolsFundamentals of Computation Theory10.1007/978-3-030-86593-1_25(354-370)Online publication date: 12-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-86593-1_25
Kamburjan EKlungre VSchlatte RJohnsen EGiese M(2021)Programming and Debugging with Semantically Lifted StatesThe Semantic Web10.1007/978-3-030-77385-4_8(126-142)Online publication date: 6-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-77385-4_8
Vukotic IRahli VEsteves-Veríssimo P(2019)Asphalion: trustworthy shielding against Byzantine faultsProceedings of the ACM on Programming Languages10.1145/33605643:OOPSLA(1-32)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360564
Apt KWojtczak D(2018)Verification of distributed epistemic gossip protocolsJournal of Artificial Intelligence Research10.1613/jair.1.1120462:1(101-132)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1613/jair.1.11204
Huang XMeyden R(2018)An Epistemic Strategy LogicACM Transactions on Computational Logic10.1145/323376919:4(1-45)Online publication date: 30-Nov-2018
https://dl.acm.org/doi/10.1145/3233769
Apt KKopczynski EWojtczak D(2017)On the computational complexity of gossip protocolsProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171642.3171752(765-771)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171642.3171752
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents