Causality and Epistemic Reasoning in Byzantine Multi-Agent Systems

Roman Kuznets
(TU Wien)
Laurent Prosperi
(ENS Paris-Saclay)
Ulrich Schmid
(TU Wien)
Krisztina Fruzsa
(TU Wien)

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.

In Lawrence S. Moss: Proceedings Seventeenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2019), Toulouse, France, 17-19 July 2019, Electronic Proceedings in Theoretical Computer Science 297, pp. 293–312.
Published: 19th July 2019.

ArXived at: http://dx.doi.org/10.4204/EPTCS.297.19 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org