[Back]

L. Prosperi, R. Kuznets, U. Schmid, K. Fruzsa, L. Gréaux:
"Knowledge in Byzantine Message-Passing Systems I: Framework and the Causal Cone";
Report for Institut für Technische Informatik; Report No. TUW-260549, 2019.

We present an extension incorporating Byzantine agents into the epistemic runs-and-systems framework for modeling distributed systems introduced by Fagin et al. [FHMV95]. Our framework relies on a careful separation of concerns for various actors involved in the evolution of a message-passing distributed system: the agents´ protocols, the underlying computational model, and the adversary controlling Byzantine faulty behavior, with each component adjustable individually. This modularity will allow our framework to be eventually extended to most existing distributed computing models. The main novelty of our framework is its ability to reason about knowledge of Byzantine agents who need not follow their protocols and may or may not be aware of their own faultiness.
We demonstrate the utility of this framework by first reproducing the standard results regarding Lamport´s happened-before causal relation [Lam78] and then identifying its Byzantine analog representing the necessary communication structure for attaining knowledge in asynchronous systems with Byzantine faulty agents.

Epistemic logic, fault-tolerant distributed systems, knowledge and reasoning, Byzantine agents,

https://publik.tuwien.ac.at/files/publik_260549.pdf