# Impossibility for Byzantine Generals Problem where $n \leq 3m$

In the paper "Reaching Agreement in the Presence of Faults", M. Pease et al. proved that there is no protocol (of some kind) to solve the problem for $n \leq 3m$, where $n$ stands for the number of generals and $m$ stands for the number of traitors. The key of their proof this the impossibility of the case $n=3,m=1$. However, the method they used does not look like an information theoretic proof. Thus, it seems like that their result is not "impossibility of arbitrary protocol".

My question: Is there a infomation-theory-based proof for the case $n=3,m=1$? More formally, is there a proof or counterexample for the proposition "there does not exist any kind of protocol, which solves Byzantine generals problem where $n=3,m=1$"?

Note: The typical protocol $\mathrm{SM}(m)$ (it works for arbitrary $n,m$) suggested by L. Lamport et al. is NOT a suitable counterexample, because it needs a signature mechanism, which is NOT perfect reliable in the sense of information theory, if we assume that traitors have infinity computing resources.

• What is an "information-theory-based proof"? Why do you expect such a proof to exist in this case? – Yuval Filmus Jun 2 '17 at 6:19
• To @YuvalFilmus: I think that (maybe it is a false belief) the original proof of impossibility states that "there is no protocol in a given form for $n \leq 3m$", which is other than "there is no protocol for $n \leq 3m$". So I am seeking a proof (or counterexample) for the latter. Note that the typical protocol $\mathrm{SM}(m)$ (it works for arbitrary $n,m$) suggested by L. Lamport et al. is NOT a suitable counterexample, because it needs a signature mechanism, which is NOT perfect reliable in the sense of information theory, if we assume that traitors have infinity computing resources. – Lwins Jun 2 '17 at 6:41
• So what you're really asking is, what result exactly is proved in the paper "Reaching Agreement in the Presence of Faults". Presumably this is explained in the paper. – Yuval Filmus Jun 2 '17 at 6:44
• To @YuvalFilmus: Not exactly probably. As I mentioned above, I am seeking a proof (or counterexample) for the proposition "there is no protocol for $n \leq 3m$". – Lwins Jun 2 '17 at 6:47

In the synchronous model of communication, there are $n$ agents which share a clock. In each round of communication, each agent sends an arbitrary message to each other agent, and then receives the message sent her by every other agent.

A protocol for byzantine agreement on $n$ agents supporting $m$ byzantine agents is a communication protocol for the agents satisfying the following properties:

• Each agent receives an input bit.
• The agents all start talking at time 0.
• There are at most $m$ byzantine agents, whose behavior is arbitrary.
• The other agents follow the protocol.
• The protocol always terminates (this means that the non-byzantine agents always reach a special "terminate" state of the protocol, and then stop talking forever), with a return value which is also a bit.
• The return values must all agree (note that this only applies to the non-byzantine agents).
• If all input bits are the same, then the return values have to be the same bit.

The impossibility result states that such a protocol exists if and only if $n > 3m$.

There is a different model in which an agent can sign a message, and this signature cannot be tampered with. In this model (which I will not specify formally) the problem can be solved for any $n,m$.

One of the difficulties in the area of distributed systems is the complicated nature of the computation model. If you want to understand the meaning of impossibility results, you have to familiarize yourself with these models in full detail (even more detail than the rather informal treatment in this answer).

• Thanks for your patient explanation : ) And I have the last question: how could I find the proof of the impossibility on synchronous communication model? The proof in paper "Reaching Agreement in the Presence of Faults" seems not to be the one. Could you suggest some literature (say, paper or book) highly related to communication model with Byzantine nodes? – Lwins Jun 2 '17 at 7:22
• I am only aware of one proof, and it is the one in the paper. For the same proof in a slightly different model, see lecture notes of Chiu Yuen Koo. – Yuval Filmus Jun 2 '17 at 7:22
• Here is one textbook: Attiya and Welch, Distributed Computing: Fundamentals, Simulations, and Advanced Topics, second edition, Wiley, 2004. – Yuval Filmus Jun 2 '17 at 7:24