Causality and epistemic reasoning in Byzantine multi-agent systems. (English) Zbl 07450035
Moss, Lawrence S. (ed.), Proceedings of the seventeenth conference on theoretical aspects of rationality and knowledge, TARK 2019, Toulouse, France, July 17–19, 2019. Waterloo: Open Publishing Association (OPA). Electron. Proc. Theor. Comput. Sci. (EPTCS) 297, 293-312 (2019).
Summary: Causality is an important concept both for proving impossibility results and for synthesizing efficient protocols in distributed computing. For asynchronous agents communicating over unreliable channels, causality is well studied and understood. This understanding, however, relies heavily on the assumption that agents themselves are correct and reliable. We provide the first epistemic analysis of causality in the presence of byzantine agents, i.e., agents that can deviate from their protocol and, thus, cannot be relied upon. Using our new framework for epistemic reasoning in fault-tolerant multi-agent systems, we determine the byzantine analog of the causal cone and describe a communication structure, which we call a multipede, necessary for verifying preconditions for actions in this setting.
For the entire collection see [Zbl 1446.68018].
For the entire collection see [Zbl 1446.68018].
MSC:
| 68T27 | Logic in artificial intelligence |
References:
| [1] | Ido Ben-Zvi & Yoram Moses (2014): Beyond Lamport’s Happened-before: On Time Bounds and the Order-ing of Events in Distributed Systems. Journal of the ACM 61(2:13), doi:10.1145/2542181. · Zbl 1295.68165 · doi:10.1145/2542181 |
| [2] | K. M. Chandy & Jayadev Misra (1986): How processes learn. Distributed Computing 1(1), pp. 40-52, doi:10.1007/BF01843569. · Zbl 0602.68026 · doi:10.1007/BF01843569 |
| [3] | Reinhard Diestel (2017): Graph Theory, Fifth edition. Springer, doi:10.1007/978-3-662-53622-3. · Zbl 1375.05002 · doi:10.1007/978-3-662-53622-3 |
| [4] | Cynthia Dwork & Yoram Moses (1990): Knowledge and Common Knowledge in a Byzantine Environment: Crash Failures. Information and Computation 88(2), pp. 156-186, doi:10.1016/0890-5401(90)90014-9. · Zbl 0705.68019 · doi:10.1016/0890-5401(90)90014-9 |
| [5] | Ronald Fagin, Joseph Y. Halpern, Yoram Moses & Moshe Y. Vardi (1995): Reasoning About Knowledge. MIT Press. · Zbl 0839.68095 |
| [6] | Ronald Fagin, Joseph Y. Halpern, Yoram Moses & Moshe Y. Vardi (1999): Common knowledge revisited. Annals of Pure and Applied Logic 96(1-3), pp. 89-105, doi:10.1016/S0168-0072(98)00033-5. · Zbl 0923.03008 · doi:10.1016/S0168-0072(98)00033-5 |
| [7] | Krisztina Fruzsa (2019): Hope for Epistemic Reasoning with Faulty Agents! In: Proceedings of ESSLLI 2019 Student Session. (To appear). |
| [8] | Guy Goren & Yoram Moses (2018): Silence. In: PODC ’18, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, ACM, pp. 285-294, doi:10.1145/3212734.3212768. · Zbl 1428.68072 · doi:10.1145/3212734.3212768 |
| [9] | Joseph Y. Halpern & Yoram Moses (1990): Knowledge and Common Knowledge in a Distributed Environ-ment. Journal of the ACM 37(3), pp. 549-587, doi:10.1145/79147.79161. · Zbl 0699.68115 · doi:10.1145/79147.79161 |
| [10] | Joseph Y. Halpern, Yoram Moses & Orli Waarts (2001): A characterization of eventual Byzantine agreement. SIAM Journal on Computing 31(3), pp. 838-865, doi:10.1137/S0097539798340217. · Zbl 1017.68007 · doi:10.1137/S0097539798340217 |
| [11] | Jaakko Hintikka (1962): Knowledge and Belief: An Introduction to the Logic of the Two Notions. Cornell University Press. · Zbl 1085.03001 |
| [12] | Roman Kuznets, Laurent Prosperi, Ulrich Schmid & Krisztina Fruzsa (2019): Epistemic Reasoning with Byzantine-Faulty Agents. In: Proceedings of FroCoS 2019. (To appear). · Zbl 1435.68317 |
| [13] | Roman Kuznets, Laurent Prosperi, Ulrich Schmid, Krisztina Fruzsa & Lucas Gréaux (2019): Knowledge in Byzantine Message-Passing Systems I: Framework and the Causal Cone. Technical Report TUW-260549, TU Wien. Available at https://publik.tuwien.ac.at/files/publik_260549.pdf. · Zbl 1435.68317 |
| [14] | Leslie Lamport (1978): Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM 21(7), pp. 558-565, doi:10.1145/359545.359563. · Zbl 0378.68027 · doi:10.1145/359545.359563 |
| [15] | Leslie Lamport, Robert Shostak & Marshall Pease (1982): The Byzantine Generals Problem. ACM Transac-tions on Programming Languages and Systems 4(3), pp. 382-401, doi:10.1145/357172.357176. · Zbl 0483.68021 · doi:10.1145/357172.357176 |
| [16] | Alexandre Maurer, Sébastien Tixeuil & Xavier Defago (2015): Reliable Communication in a Dynamic Net-work in the Presence of Byzantine Faults. eprint 1402.0121, arXiv. Available at https://arxiv.org/abs/ 1402.0121. |
| [17] | Yoram Moses (2015): Relating Knowledge and Coordinated Action: The Knowledge of Preconditions Prin-ciple. In R. Ramanujam, editor: Proceedings of TARK 2015, pp. 231-245, doi:10.4204/EPTCS.215.17. · Zbl 1483.68423 · doi:10.4204/EPTCS.215.17 |
| [18] | Yoram Moses & Yoav Shoham (1993): Belief as defeasible knowledge. Artificial Intelligence 64(2), pp. 299-321, doi:10.1016/0004-3702(93)90107-M. · Zbl 0787.68095 · doi:10.1016/0004-3702(93)90107-M |
| [19] | Yoram Moses & Mark R. Tuttle (1988): Programming Simultaneous Actions Using Common Knowledge. Algorithmica 3, pp. 121-169, doi:10.1007/BF01762112. · Zbl 0646.68031 · doi:10.1007/BF01762112 |
| [20] | T. K. Srikanth & Sam Toueg (1987): Optimal Clock Synchronization. Journal of the ACM 34(3), pp. 626-645, doi:10.1145/28869.28876. · doi:10.1145/28869.28876 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
