My question is what makes the Byzantine Generals Problem possible to solve in some cases where traitors exist, for example in the case where there are 4 generals with 1 traitor?

If the generals must either all attack or all retreat at the same time, then surely the traitorous general can simply say "yeah sure we'll attack" and then retreat as the other 3 generals plunge into their deaths.

I suspect the answer has something to do with different variations of the problem, but I was unable to find any other definition for the Byzantine Generals Problem other than "all must either attack or retreat". Almost all of the search results are blockchain related advertisement, and the Wikipedia article doesn't provide a different definition for the goal of the generals.

  • $\begingroup$ Look up lecture notes on byzantine generals. $\endgroup$ Dec 9 '18 at 17:34
  • $\begingroup$ Here is a good starting point: people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf $\endgroup$ Dec 9 '18 at 17:36
  • 1
    $\begingroup$ As another googling tip, you can use Google Scholar to find academic articles. While this will often be very technical (which may or may not be an issue for you), you will not have issues with digging through blockchain advertisements and you will get comprehensive definitions and an in-depth analysis up to and including proofs. In particular, the first hit is the original paper presenting the idea. $\endgroup$ Dec 9 '18 at 20:42

Quoting from the abstract of the original paper introducing the Byzantine Generals problem (with my emphasis):

The problem is to find an algorithm to ensure that the loyal generals will reach agreement.

If you read further in the paper, they reduce the problem to agreeing on a single bit: "Attack" or "Retreat". The question is can the loyal generals reach consensus amongst themselves when they don't know who the traitors are.

So for your proposed scenario, as far as the Byzantine Generals problem is concerned, the only question is whether all the loyal generals can agree on the plan, not whether the plan is workable. At any rate, "all attack" either means "all [loyal generals] attack" which is essentially what would be produced by a Byzantine fault-tolerance algorithm, or it means "all [generals, loyal and traitorous alike,] attack" which would simply be silly. In this thought experiment the generals know that there are potentially traitors so they would presumably not propose a plan that only works if there are no traitors. What is actually being agreed upon, e.g. the "goal", is outside the scope of the Byzantine fault-tolerance algorithm, of course. The algorithm doesn't care whether the question is "should we attack or retreat?" or "should we choose pink or chartreuse for the new standard?"

If the generals must either all attack or all retreat at the same time

That's a common mistake, but the correct is:

2/3 of the generals must either all attack or all retreat at the same time

It is not "all or nothing", but "2/3 or nothing" (or more).

In your example, we have 4 loyal generals and 1 traitor. This means 4 generals need to attack at the same time in order to succeed (3.33 generals, rounded to 4).

  • $\begingroup$ Nice answer. Nitpicking, it is not "rounded" in the usual sense of that word. It refers to more than 2/3 of the generals, which mean 4 or 5 generals here. $\endgroup$
    – John L.
    Mar 23 '19 at 22:29
  • $\begingroup$ The quoted text looks to me like "More than 2/3 or less than 1/3", not "More than 2/3 or none". $\endgroup$ Mar 24 '19 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.