Byzantine Consensus in Directed Graphs with Message Authentication
Provides foundational graph-theoretic conditions for Byzantine consensus in directed networks, relevant to distributed systems and fault-tolerant computing.
The paper identifies necessary and sufficient conditions on directed communication graphs for Byzantine consensus with message authentication, solving exact consensus in synchronous systems and approximate consensus in asynchronous systems.
We consider the problem of reaching consensus in communication networks that are modeled by directed graphs. We assume the existence of a message authentication mechanism (such as digital signatures) to verify the integrity of messages. We identify the necessary and sufficient conditions on the directed communication graph for the following problems to be solvable: (i) exact consensus in synchronous systems; and (ii) approximate consensus in asynchronous systems.