{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:32:00Z","timestamp":1742913120411,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031433689"},{"type":"electronic","value":"9783031433696"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T00:00:00Z","timestamp":1694563200000},"content-version":"vor","delay-in-days":255,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Byzantine fault-tolerant distributed systems are designed to provide resiliency despite arbitrary faults, i.e., even in the presence of agents who do not follow the common protocol and\/or despite compromised communication. It is, therefore, common to focus on the perspective of correct agents, to the point that the epistemic state of byzantine agents is completely ignored. Since this view relies on the assumption that faulty agents may behave arbitrarily adversarially, it is overly conservative in many cases. In blockchain settings, for example, dishonest players are usually not malicious, but rather selfish, and thus just follow some \u201chidden\u201d protocol that is different from the protocol of the honest players. Similarly, in high-availability large-scale distributed systems, software updates cannot be globally instantaneous, but are rather performed node-by-node. Consequently, updated and non-updated nodes may simultaneously be involved in a protocol for solving a distributed task like consensus or transaction commit. Clearly, the usual assumption of common knowledge of the protocol is inappropriate in such a setting. On the other hand, joint protocol execution and, sometimes, even basic communication becomes problematic without this assumption: How are agents supposed to interpret each other\u2019s messages without knowing their mutual communication protocols? We propose a novel epistemic modality <jats:italic>creed<\/jats:italic> for epistemic reasoning in heterogeneous distributed systems with agents that are uncertain of the actual communication protocol used by their peers. We show that the resulting logic is quite closely related to modal logic\u00a0<jats:inline-formula><jats:tex-math>$$\\textsf{S5}$$<\/jats:tex-math><\/jats:inline-formula>, the standard logic of epistemic reasoning in distributed systems. We demonstrate the utility of our approach by several examples\n.<\/jats:p>","DOI":"10.1007\/978-3-031-43369-6_7","type":"book-chapter","created":{"date-parts":[[2023,9,14]],"date-time":"2023-09-14T14:32:18Z","timestamp":1694701938000},"page":"119-136","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Logic of\u00a0Communication Interpretation: How to\u00a0Not Get Lost in\u00a0Translation"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6779-4023","authenticated-orcid":false,"given":"Giorgio","family":"Cignarale","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5894-8724","authenticated-orcid":false,"given":"Roman","family":"Kuznets","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8152-1275","authenticated-orcid":false,"given":"Hugo","family":"Rincon Galeana","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9831-8583","authenticated-orcid":false,"given":"Ulrich","family":"Schmid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,13]]},"reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1007\/11785477_26","volume-title":"ECOOP 2006 \u2013 Object-Oriented Programming","author":"S Ajmani","year":"2006","unstructured":"Ajmani, S., Liskov, B., Shrira, L.: Modular software upgrades for distributed systems. In: Thomas, D. (ed.) ECOOP 2006. LNCS, vol. 4067, pp. 452\u2013476. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11785477_26"},{"key":"7_CR2","unstructured":"Amoussou-Guenou, Y., Biais, B., Potop-Butucaru, M., Tucci-Piergiovanni, S.: Rational vs byzantine players in consensus-based blockchains. In: AAMAS 2020: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pp. 43\u201351. IFAAMAS (2020). https:\/\/dl.acm.org\/doi\/abs\/10.5555\/3398761.3398772"},{"key":"7_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/978-3-030-36755-8_2","volume-title":"Logical Foundations of Computer Science","author":"S Artemov","year":"2020","unstructured":"Artemov, S.: Observable models. In: Artemov, S., Nerode, A. (eds.) LFCS 2020. LNCS, vol. 11972, pp. 12\u201326. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-36755-8_2"},{"key":"7_CR4","doi-asserted-by":"publisher","DOI":"10.1002\/0471478210","volume-title":"Distributed Computing: Fundamentals, Simulations and Advanced Topics","author":"H Attiya","year":"2004","unstructured":"Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. Wiley, Hoboken (2004)","edition":"2"},{"key":"7_CR5","doi-asserted-by":"publisher","unstructured":"B\u00edlkov\u00e1, M., Christoff, Z., Roy, O.: Revisiting epistemic logic with names. In: Proceedings Eighteenth Conference on Theoretical Aspects of Rationality and Knowledge: Beijing, China, June 25\u201327, 2021. Electronic Proceedings in Theoretical Computer Science, vol. 335, pp. 39\u201354. Open Publishing Association (2021). https:\/\/doi.org\/10.4204\/eptcs.335.4","DOI":"10.4204\/eptcs.335.4"},{"issue":"2","key":"7_CR6","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/s00446-021-00417-3","volume":"35","author":"A Casta\u00f1eda","year":"2022","unstructured":"Casta\u00f1eda, A., Gonczarowski, Y.A., Moses, Y.: Unbeatable consensus. Distrib. Comput. 35(2), 123\u2013143 (2022). https:\/\/doi.org\/10.1007\/s00446-021-00417-3","journal-title":"Distrib. Comput."},{"issue":"2","key":"7_CR7","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s11023-023-09631-3","volume":"33","author":"G Cignarale","year":"2023","unstructured":"Cignarale, G., Schmid, U., Tahko, T., Kuznets, R.: The role of a priori belief in the design and analysis of fault-tolerant distributed systems. Mind. Mach. 33(2), 293\u2013319 (2023). https:\/\/doi.org\/10.1007\/s11023-023-09631-3","journal-title":"Mind. Mach."},{"key":"7_CR8","volume-title":"Distributed Systems: Concepts and Design","author":"G Coulouris","year":"2011","unstructured":"Coulouris, G., Dollimore, J., Kindberg, T., Blair, G.: Distributed Systems: Concepts and Design, 5th edn. Addison-Wesley, Boston (2011)","edition":"5"},{"key":"7_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4020-5839-4","volume-title":"Dynamic Epistemic Logic, Synthese Library","author":"H van Ditmarsch","year":"2007","unstructured":"van Ditmarsch, H., van der Hoek, W., Kooi, B.: Dynamic Epistemic Logic, Synthese Library, vol. 337. Springer, Dordrecht (2007). https:\/\/doi.org\/10.1007\/978-1-4020-5839-4"},{"key":"7_CR10","unstructured":"Fruzsa, K., Kuznets, R., van Ditmarsch, H.: A new hope. In: Fern\u00e1ndez-Duque, D., Palmigiano, A., Pinchinat, S. (eds.) Advances in Modal Logic, vol. 14, pp. 349\u2013370. College Publications (2022)"},{"key":"7_CR11","doi-asserted-by":"publisher","unstructured":"Fruzsa, K., Kuznets, R., Schmid, U.: Fire! In: Proceedings Eighteenth Conference on Theoretical Aspects of Rationality and Knowledge: Beijing, China, June 25\u201327, 2021. Electronic Proceedings in Theoretical Computer Science, vol. 335, pp. 139\u2013153. Open Publishing Association (2021). https:\/\/doi.org\/10.4204\/EPTCS.335.13","DOI":"10.4204\/EPTCS.335.13"},{"key":"7_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/978-3-642-31585-5_50","volume-title":"Automata, Languages, and Programming","author":"A Groce","year":"2012","unstructured":"Groce, A., Katz, J., Thiruvengadam, A., Zikas, V.: Byzantine agreement with a rational adversary. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7392, pp. 561\u2013572. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31585-5_50"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1146\/annurev.cs.02.060187.000345","volume":"2","author":"JY Halpern","year":"1987","unstructured":"Halpern, J.Y.: Using reasoning about knowledge to analyze distributed systems. Ann. Rev. Comput. Sci. 2, 37\u201368 (1987). https:\/\/doi.org\/10.1146\/annurev.cs.02.060187.000345","journal-title":"Ann. Rev. Comput. Sci."},{"issue":"3","key":"7_CR14","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/79147.79161","volume":"37","author":"JY Halpern","year":"1990","unstructured":"Halpern, J.Y., Moses, Y.: Knowledge and common knowledge in a distributed environment. J. ACM 37(3), 549\u2013587 (1990). https:\/\/doi.org\/10.1145\/79147.79161","journal-title":"J. ACM"},{"key":"7_CR15","volume-title":"Knowledge and Belief: An Introduction to the Logic of the Two Notions","author":"J Hintikka","year":"1962","unstructured":"Hintikka, J.: Knowledge and Belief: An Introduction to the Logic of the Two Notions. Cornell University Press, New York (1962)"},{"key":"7_CR16","doi-asserted-by":"publisher","unstructured":"Kuznets, R., Prosperi, L., Schmid, U., Fruzsa, K.: Causality and epistemic reasoning in byzantine multi-agent systems. In: Moss, L.S. (ed.) Proceedings Seventeenth Conference on Theoretical Aspects of Rationality and Knowledge: Toulouse, France, 17\u201319 July 2019. Electronic Proceedings in Theoretical Computer Science, vol. 297, pp. 293\u2013312. Open Publishing Association (2019). https:\/\/doi.org\/10.4204\/EPTCS.297.19","DOI":"10.4204\/EPTCS.297.19"},{"key":"7_CR17","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/978-3-030-29007-8_15","volume-title":"Frontiers of Combining Systems","author":"R Kuznets","year":"2019","unstructured":"Kuznets, R., Prosperi, L., Schmid, U., Fruzsa, K.: Epistemic reasoning with byzantine-faulty agents. In: Herzig, A., Popescu, A. (eds.) FroCoS 2019. LNCS (LNAI), vol. 11715, pp. 259\u2013276. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-29007-8_15"},{"key":"7_CR18","unstructured":"Kuznets, R., Prosperi, L., Schmid, U., Fruzsa, K., Gr\u00e9aux, L.: Knowledge in byzantine message-passing systems I: framework and the causal cone. Technical report. TUW-260549, TU Wien (2019). https:\/\/publik.tuwien.ac.at\/files\/publik_260549.pdf"},{"issue":"3","key":"7_CR19","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L Lamport","year":"1982","unstructured":"Lamport, L., Shostak, R., Pease, M.: The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst. 4(3), 382\u2013401 (1982). https:\/\/doi.org\/10.1145\/357172.357176","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"1","key":"7_CR20","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/s11023-012-9287-x","volume":"23","author":"F Liu","year":"2013","unstructured":"Liu, F., Wang, Y.: Reasoning about agent types and the hardest logic puzzle ever. Mind. Mach. 23(1), 123\u2013161 (2013). https:\/\/doi.org\/10.1007\/s11023-012-9287-x","journal-title":"Mind. Mach."},{"key":"7_CR21","unstructured":"Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, Burlington (1996)"},{"key":"7_CR22","doi-asserted-by":"publisher","unstructured":"Moses, Y.: Relating knowledge and coordinated action: the knowledge of preconditions principle. In: Ramanujam, R. (ed.) Proceedings Fifteenth Conference on Theoretical Aspects of Rationality and Knowledge: Carnegie Mellon University, Pittsburgh, USA, June 4\u20136, 2015. Electronic Proceedings in Theoretical Computer Science, vol. 215, pp. 231\u2013245. Open Publishing Association (2015). https:\/\/doi.org\/10.4204\/EPTCS.215.17","DOI":"10.4204\/EPTCS.215.17"},{"issue":"4","key":"7_CR23","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1137\/S0097539799364006","volume":"31","author":"Y Moses","year":"2002","unstructured":"Moses, Y., Rajsbaum, S.: A layered analysis of consensus. SIAM J. Comput. 31(4), 989\u20131021 (2002). https:\/\/doi.org\/10.1137\/S0097539799364006","journal-title":"SIAM J. Comput."},{"issue":"2","key":"7_CR24","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0004-3702(93)90107-M","volume":"64","author":"Y Moses","year":"1993","unstructured":"Moses, Y., Shoham, Y.: Belief as defeasible knowledge. Artif. Intell. 64(2), 299\u2013321 (1993). https:\/\/doi.org\/10.1016\/0004-3702(93)90107-M","journal-title":"Artif. Intell."},{"key":"7_CR25","doi-asserted-by":"publisher","unstructured":"Saur, K., Collard, J., Foster, N., Guha, A., Vanbever, L., Hicks, M.: Safe and flexible controller upgrades for SDNs. In: Symposium on Software Defined Networking (SDN) Research (SOSR 2016): March 14\u201315, 2016, in Santa Clara, CA. ACM (2016). https:\/\/doi.org\/10.1145\/2890955.2890966","DOI":"10.1145\/2890955.2890966"},{"key":"7_CR26","volume-title":"What is the Name of this Book? The Riddle of Dracula and Other Logical Puzzles","author":"RM Smullyan","year":"1978","unstructured":"Smullyan, R.M.: What is the Name of this Book? The Riddle of Dracula and Other Logical Puzzles. Prentice-Hall, Hoboken (1978)"}],"container-title":["Lecture Notes in Computer Science","Frontiers of Combining Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43369-6_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,14]],"date-time":"2023-09-14T14:32:48Z","timestamp":1694701968000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43369-6_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031433689","9783031433696"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43369-6_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"13 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FroCoS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Frontiers of Combining Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Prague","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Czech Republic","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"frocos2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/frocos2023.github.io\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}