[Back]

R. Kuznets:
"The Byzantine Mind";
Talk: Seminar Logic and Theoretical Computer Science, University of Bern (2017), Bern, Schweiz (invited); 2017-11-16.

The idea to analyze communication in distributed systems using epistemic logic has been around for more than 25 years and yielded such seminal results as the necessity of common knowledge as a precondition for coordinated action. The goal of this ongoing project is to incorporate Byzantine agents, i.e., agents prone to failure, into the epistemic framework. Some limited types of Byzantine behaviours, e.g., crash failures, have already been studied in this respect by Dwork and Moses. But handling knowledge in such limited circumstances is more straightforward. We consider fully Byzantine agents whose behavior is maximally unrestricted but whose knowledge remains local. The failures of such agents to follow their protocol can be assigned either to malicious intent or to malfunction. It is the latter case that is of most interest from the epistemic perspective. One of the natural questions is whether such an agent can determine its own correctness or its own faultiness based solely on its local view of the system. In order to analyze such agents, we develop a detailed layered view of each transition step in a distributed system and prove first lower bounds on the communication necessary for performing actions despite at most f agents potentially failing. We demonstrate the potential of our framework by providing a modular way of incorporating into it various popular communication contexts, including synchronous agents, synchronous communication, broadcast (both hardware and software), coordinated action, etc. This is work in progress.

Joint work with Laurent Prosperi and Ulrich Schmid