2
$\begingroup$

I am unable to understand why there is a requirement of 3m+1 generals overall given m traitors. As per my understanding, the steps are as follows:

  1. Each general decides a strategy and forwards their strategy to all the other ($3m$) generals.
  2. Each general forwards a vector containing the strategies (of all the other generals they received) to all the generals ($m$)
  3. Now, each general has a list of vectors corresponding to the vote made by each general and using a majority criteria (majority vote) decides each general's strategy and thus, the strategy that it itself chooses.

If there are $3m+1$ generals then, with $m$ (loyal) generals choosing to 'attack' and $m+1$ (loyal) generals choosing to 'defend' and $m$ traitors, then since every loyal general forwards the message correctly, each of the $m$ 'attacking' generals will receive $m-1 + m$ (from the other 'attacking' generals and the $m$ 'defending' generals) confirmations of attack for all the other $m-1$ 'attacking' generals, similarly $m-1 + m$ confirmations of 'defend' for the strategy adopted by each one of the defending generals. The traitors however can alter either by sending whatever they'd like (different bits) to the attackers and the defenders [send d for all the defenders and a for all the attackers, but send conflicting values — d to the defenders and a to the attackers — for all the traitors' values], thus making them follow a different plan (defenders will defend, while attackers will attack).

This can't be right, because all the papers and presentations I've gone through state that $3m+1$ with only $m$ traitors will definitely give you the correct solution (all loyal generals follow the same plan). Can anybody go through my understanding, find the flaw and re-explain it to me?

Also, I have understood the $m = 1$ example, it would be nice if someone could explain to me how it fails when $m = 2$ and there are 6 generals and how it succeeds if $m = 2$ and there are 7 generals... I've tried a lot and am stuck.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Reposted from CSTheory. Please don't post the same question on multiple sites. I realize as a brand new user your options are limited, but at least you should have linked the questions to each other, so that people don't waste time duplicating answers that someone might already have posted on the other site. If you had at least 15 reputation, you should have flagged your CSTheory post to have it migrated here. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Sep 10, 2012 at 13:50
  • $\begingroup$ I actually modified the question greatly, adding more explanation. Also, I was asked to post it here. $\endgroup$
    – Ingrid Morstrad
    Commented Sep 10, 2012 at 15:08
  • $\begingroup$ A proof of this impossibility result is given in section 3 this paper. It is fairly simple. Suppose there are 3 parties A, B, C with C faulty and A & B wanting output 0. Then a strategy for the faulty C should be to internally run an honest interaction of C-A-B-C (4 components hooked up in this way), where each component wants output 1. $\endgroup$
    – user2781
    Commented Sep 11, 2012 at 3:13

1 Answer 1

Reset to default
1
$\begingroup$

all the papers [...] state that $3m+1$ with only $m$ traitors will definitely give you the correct solution

They should actually state that when $3m+1$ then correct algorithms exist, but not all algorithms are correct.

Algorithms are like cooking recipes (in fact recipes are algorithms): Consider the problem of baking bread. There are books that tell you that you require flour, water and yeast (or similar). But not every recipe of the three will at the end resemble bread. Consider this one: Mix a spoon yeast, a spoon of flour and 5 litres of water, fill in glasses and refrigerate overnight, serve cold... Definitely not bread ;-)

What your example shows is that the algorithm given in 1),2),3) is not one that solves the Byzantine Generals problem. (Note that it is well known that a correct algorithm will (in the worst case) need at least m+1 rounds.)

Answer to original question on CSTheory:

I think your miss-conception lies in the assumption

m+1 loyal generals should vote the same way

Why should this hold?

Assuming you are talking about the problem as defined in LSP82: For simplicity let's set $m=1$. Then with just $2m+1=3$ generals you have one commanding general and two lieutenant generals. When the commanding general is correct, he and the correct general will vote the same way. So in this case your assumption holds. But what if the commanding general himself is Byzantine? Then he can give different instructions to the two correct (lieutenant) generals, and they are no longer guaranteed to vote the same way.

In general, if the proposer/commanding general is faulty then there is no way to guarantee that all correct processes will vote in the same way.

Improve this answer
$\endgroup$
6
  • $\begingroup$ The way I understand it a byzantine lieutenant A decides his vote (let's say "Attack" and sends it to all the other generals), similary the other generals do the same. Now, if all the loyal generals decide to "attack" and all the traitors "retreat", then when each loyal general receives the 3m+1 bit vector that contain the votes of all the other generals, he can easily figure out which action to take as long as the traitors are in the minority (less than 1/2 of the rest). I am not able to see why it should be less than 1/3. Even in the case where m=1, for 1 general to decide, the traitors... $\endgroup$
    – Ingrid Morstrad
    Commented Sep 10, 2012 at 9:04
  • $\begingroup$ (contd...) should be in the minority of the remaining (and since there can be 1 general and 1 traitor, the traitor is not in the minority and the 1/2 condition is not satisfied). I think I misunderstand a vital part of this problem. When the general sends the message, have none of the lieutenants have decided their course of action? $\endgroup$
    – Ingrid Morstrad
    Commented Sep 10, 2012 at 9:07
  • $\begingroup$ Oh I just re-read your post, missed this part: I think your miss-conception lies in the assumption m+1 loyal generals should vote the same way. Why should this hold? I think I may have misunderstood how each general/lieutenant decides his vote. I assumed they all have a strategy that they each individually want to follow at the beginning, before voting. During voting, their strategies may change if the majority vote is against their strategy. So, in short, are you saying that it is possibly that 1/2 the loyal generals may vote "attack" and 1/2 may choose "defence" at the very beginning? $\endgroup$
    – Ingrid Morstrad
    Commented Sep 10, 2012 at 9:10
  • $\begingroup$ @IngridMorstrad: Yes, initially, we can have any number of generals who prefer "attack" (with the rest preferring to "retreat"). $\endgroup$
    – subsub
    Commented Sep 11, 2012 at 10:01
  • $\begingroup$ Could you tell me how to modify the algorithm I've written in steps 1)2) and 3) above so that it is correct? I had actually tried to write the 'correct' algorithm as I understood it, but can't seem to pinpoint where I've gone off the right track. $\endgroup$
    – Ingrid Morstrad
    Commented Sep 12, 2012 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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