A priori Belief Updates as a Method for Agent Self-recovery

Giorgio Cignarale and Roman Kuznets [PDF]

Abstract

Standard epistemic logic is concerned with describing agents’ epistemic attitudes given the current set of alternatives the agents consider possible. While distributed systems can be (and often are) discussed without mentioning epistemics, it has been well established that epistemic phenomena lie at the heart of what agents, or processes, can and cannot do. Dynamic epistemic logic (DEL) aims to describe how epistemic attitudes of the agents/processes change based on the new information they receive, e.g., based on their observations of events and actions in a distributed system. In a broader philosophical view, this appeals to an a posteriori kind of reasoning, where agents update the set of alternatives considered possible based on their “experiences.” Until recently, there was little incentive to formalize a priori reasoning, which plays a role in designing and maintaining distributed systems, e.g., in determining which states must be considered possible by agents in order to solve the distributed task at hand, and consequently in updating these states when unforeseen situations arise during runtime. With systems becoming more and more complex and large, the task of fixing design errors “on the fly” is shifted to individual agents, such as in the increasingly popular self-adaptive and self-organizing (SASO) systems. Rather than updating agents’ a posteriori beliefs, this requires modifying their a priori beliefs about the system’s global design and parameters. The goal of this paper is to provide a formalization of such a priori reasoning by using standard epistemic semantic tools, including Kripke models and DEL-style updates, and provide heuristics that would pave the way to streamlining this inherently nondeterministic and ad hoc process for SASO systems.

Keywords

Distributed systems, Dynamic epistemic logic, a priori beliefs, Philosophy of computation, Self-adaptive and self-organizing systems

References

1. Artemov, S. (2020). Observable models. Logical Foundations of Computer Science: In- ternational Symposium, LFCS 2020, Deerfield Beach, FL, USA, January 4–7, 2020, Proceedings, Volume 11972 of Lecture Notes in Computer Science, 12–26. Springer. https://doi.org/10.1007/978-3-030-36755-8_2
2. Artemov, S. (2022). Towards syntactic epistemic logic. Fundameta Informaticae, 186 (1–4), 45–62. https://fi.episciences.org/10792/
3. Baltag, A., Moss, L. S., and Solecki, S. (1998). The logic of public announcements, common knowledge, and private suspicions. Theoretical Aspects of Rationality and Knowledge: Proceedings of the Seventh Conference (TARK 1998), 43–56. Morgan Kaufmann. http://tark.org/proceedings/tark_jul22_98/p43-baltag.pdf
4. Baltag, A. and Smets, S. (2008). A qualitative theory of dynamic interactive belief revision. Logic and the Foundations of Game and Decision Theory (LOFT 7), Volume 3 of Texts in Logic and Games, 11–58. Amsterdam University Press. https://www.jstor.org/stable/j.ctt46mz4h.4
5. van Benthem, J. and Smets, S. (2015). Dynamic logics of belief change. Handbook of Epistemic Logic, 313–393. College Publications.
6. Ben-Zvi, I. and Moses, Y. (2014). Beyond Lamport’s Happened-before: On time bounds and the ordering of events in distributed systems. Journal of the ACM, 61(2), 13:1–13:26. https://doi.org/10.1145/2542181
7. Berns, A. and Ghosh, S. (2009). Dissecting self-* properties. SASO 2009: Third IEEE International Conference on Self-Adaptive and Self-Organizing Systems, 10–19. IEEE. https://doi.org/10.1109/SASO.2009.25
8. Castañeda, A., Gonczarowski, Y. A., and Moses, Y. (2022). Unbeatable consensus. Distributed Computing, 35(2), 123–143. https://doi.org/10.1007/s00446-021-00417-3
9. Chagrov, A. and Zakharyaschev, M. (1997). Modal Logic, Volume 35 of Oxford Logic Guides. Clarendon Press. https://doi.org/10.1093/oso/9780198537793.001.0001
10. Cignarale, G., Kuznets, R., and Schlögl, T. (2024). Minimizing agents’ state corruption resulting from leak-free epistemic communication modeling. Foundations of Information and Knowledge Systems: 13th International Symposium, FoIKS 2024, Sheffield, UK, April 8–11, 2024, Proceedings, Volume 14589 of Lecture Notes in Computer Science, 165–181. Springer. https://doi.org/10.1007/978-3-031-56940-1_9
11. Cignarale, G., Schmid, U., Tahko, T., and Kuznets, R. (2023). The role of a priori belief in the design and analysis of fault-tolerant distributed systems. Minds and Machines, 33(2), 293–319. https://doi.org/10.1007/s11023-023-09631-3
12. Coulouris, G., Dollimore, J., Kindberg, T., and Blair, G. (2011). Distributed Systems: Concepts and Design (5th ed.). Addison–Wesley.
13. van Ditmarsch, H. (2005). Prolegomena to dynamic logic for belief revision. Synthese, 147(2), 229–275. https://doi.org/10.1007/s11229-005-1349-7
14. van Ditmarsch, H., Goubault, É., Lazić, M., Ledent, J., and Rajsbaum, S. (2021). A dynamic epistemic logic analysis of equality negation and other epistemic covering tasks. Journal of Logical and Algebraic Methods in Programming, 121, 100662. https://doi.org/10.1016/j.jlamp.2021.100662
15. van Ditmarsch, H., van der Hoek, W., and Kooi, B. (2007). Dynamic Epistemic Logic, Volume 337 of Synthese Library. Springer. https://doi.org/10.1007/978-1-4020-5839-4
16. van Ditmarsch, H. and Kooi, B. (2015). One Hundred Prisoners and a Light Bulb. Springer. https://doi.org/10.1007/978-3-319-16694-0
17. Fagin, R., Halpern, J. Y., Moses, Y., and Vardi, M. Y. (1995). Reasoning About Knowledge. MIT Press. https://doi.org/10.7551/mitpress/5803.001.0001
18. Fruzsa, K., Kuznets, R., and Schmid, U. (2021). Fire! Proceedings of the Eighteenth Conference on Theoretical Aspects of Rationality and Knowledge, Beijing, China, June 25–27, 2021, Volume 335 of Electronic Proceedings in Theoretical Computer Science, 139–153. Open Publishing Association. https://doi.org/10.4204/EPTCS.335.13
19. Gerbrandy, J. and Groeneveld, W. (1997). Reasoning about information change. Journal of Logic, Language, and Information, 6(2), 147–169. https://doi.org/10.1023/A:1008222603071
20. Gettier, E. L. (1963). Is justified true belief knowledge? Analysis, 23(6), 121–123. https://doi.org/10.1093/analys/23.6.121
21. Goren, G. and Moses, Y. (2020). Silence. Journal of the ACM, 67(1), 3:1–3:26. https://doi.org/10.1145/3377883
22. Goubault, É., Ledent, J., and Rajsbaum, S. (2021). A simplicial complex model for dynamic epistemic logic to study distributed task computability. Information and Computation, 278, 104597. https://doi.org/10.1016/j.ic.2020.104597
23. Halpern, J. Y. and Moses, Y. (1990). Knowledge and common knowledge in a distributed environment. Journal of the ACM, 37(3), 549–587. https://doi.org/10.1145/79147.79161
24. Hintikka, J. (1962). Knowledge and Belief: An Introduction to the Logic of the Two Notions. Cornell University Press.
25. Kuznets, R., Prosperi, L., Schmid, U., and Fruzsa, K. (2019a). Causality and epistemic reasoning in byzantine multi-agent systems. Proceedings of the Seventeenth Conference on Theoretical Aspects of Rationality and Knowledge, Toulouse, France, 17–19 July 2019, Volume 297 of Electronic Proceedings in Theoretical Computer Science, 293–312. Open Publishing Association. https://doi.org/10.4204/EPTCS.297.19
26. Kuznets, R., Prosperi, L., Schmid, U., and Fruzsa, K. (2019b). Epistemic reasoning with byzantine-faulty agents. Frontiers of Combining Systems: 12th International Sympo- sium, FroCoS 2019, London, UK, September 4–6, 2019, Proceedings, Volume 11715 of Lecture Notes in Artificial Intelligence, 259–276. Springer. https://doi.org/10.1007/978-3-030-29007-8_15
27. Lewis, D. K. (1969). Convention: A Philosophical Study. Harvard University Press.
28. Lynch, N. A. (1996). Distributed Algorithms. Morgan Kaufmann.
29. Moses, Y. (2016). Relating knowledge and coordinated action: The knowledge of precondi- tions principle. Proceedings Fifteenth Conference on Theoretical Aspects of Rationality and Knowledge, Carnegie Mellon University, Pittsburgh, USA, June 4–6, 2015, Volume 215 of Electronic Proceedings in Theoretical Computer Science, 231–245. Open Pub lishing Association. https://doi.org/10.4204/EPTCS.215.17
30. Moses, Y. and Tuttle, M. R. (1988). Programming simultaneous actions using common knowledge. Algorithmica, 3(1–4), 121–169. https://doi.org/10.1007/BF01762112
31. Plaza, J. A. (1989). Logics of public communications. Proceedings of the Fourth International Symposium on Methodologies for Intelligent Systems: Poster Session Program, 201–216. Oak Ridge National Laboratory.
32. Quine, W. V. (1951). Two dogmas of empiricism. Philosophical Review, 60(1), 20–43. https://doi.org/10.2307/2181906
33. Schlögl, T. and Schmid, U. (2023). A sufficient condition for gaining belief in byzantine fault- tolerant distributed systems. Proceedings of the Nineteenth conference on Theoretical Aspects of Rationality and Knowledge, Oxford, United Kingdom, 28–30th June 2023, Volume 379 of Electronic Proceedings in Theoretical Computer Science, 487–497. Open Publishing Association. https://doi.org/10.4204/EPTCS.379.37
34. Tahko, T. E. (2008). A new definition of a priori knowledge: In search of a modal basis.Metaphysica, 9(1), 57–68. https://doi.org/10.1007/s12133-007-0022-7
35. Tahko, T. E. (2011). A priori and a posteriori: A bootstrapping relationship. Metaphysica, 12(2), 151–164. https://doi.org/10.1007/s12133-011-0083-5
36. Tomforde, S., Hähner, J., von Mammen, S., Gruhl, C., Sick, B., and Geihs, K. (2014). “Know thyself” — Computational self-reflection in intelligent technical systems. SaSow 2014: 2014 IEEE Eighth International Conference on Self-Adaptive and Self-Organizing Systems Workshops, 150–159. IEEE. https://doi.org/10.1109/SASOW.2014.25