[Zurück]

R. Kuznets, L. Prosperi, U. Schmid, K. Fruzsa:
"Byzantine Causal Cone";
Vortrag: Workshop on Formal Reasoning in Distributed Algorithms (FRiDA), Budapest, Hungary (eingeladen); 18.10.2019.

To prove the correctness of a given distributed algorithm, it is necessary to verify that each action is taken only when the global system state allows it. However, due to the incomplete local view of each agent, the Knowledge of Preconditions Principle (KoP), formulated by Yoram Moses, lifts preconditions to the epistemic level. KoP states that, for any condition that is specified as necessary for an agent to perform a certain action, this agent knowing that the condition is fulfilled is also necessary for performing this action. It is well known that causality in asynchronous distributed systems, i.e., those where agents do not have access to a global synchronized clock, is governed solely by messages the agents exchange: an agent cannot know what happened to another agent without a chain of messages delivering this information, leading to the concept of a causal cone, first introduced by Leslie Lamport.

In this talk, we discuss the impact of byzantine failures on causality in asynchronous systems. If any agent can arbitrarily violate its protocol, e.g., send incorrect information, possibly different information to different respondents, then a simple chain of messages is not sufficient anymore. We provide an elaborate modeling and analysis framework for multi-agent systems with byzantine faults and use it to describe the byzantine analog of Lamport´s causal cone, the limitations on what can be known in principle, as well as the necessary conditions for achievable states of knowledge in fault-tolerant distributed systems.