-1

I am reading the paper The Byzantine Generals Problem of Lamport, Shostak, Pease and I am trying to follow the demonstrations with rigour.

I like the paper, and I think that I've understood it, but there is a passage that isn't clear to me.

That to say that the concept is clear, but the detail is not for my own issue. Here, I am looking for help to clarify my mind.

The passage is the construction of the three-generals solution.

The proof is by contradiction, so they start from assuming that 3m generals (Albanians) can cope with m traitors (that are part of the 3m). Starting from 3m or fewer generals, they construct a solution that works for the Byzantine Generals Problem with one general and two lieutenants that is impossible, therefore they clearly show that there is no solution for fewer than 3m + 1 generals coping with m traitors.

How to arrange 3m generals to form three subsets with one of them containing all the traitors is quite easy. My problem is the language of the text:

The three-general solution is obtained by having each of the Byzantine generals simulate approximately one-third of the Albanian generals, so that each Byzantine general is simulating at most m Albanian generals. The Byzantine commander simulates the Albanian commander plus at most m - 1 Albanian lieutenants (???), and each of the two Byzantine lieutenants simulates at most m Albanian lieutenants. Since only one Byzantine general can be a traitor, and he simulates at most m Albanians, at most m of the Albanian generals are traitors.

I am struggling with this text because we are dealing with generals. In my view, the passages should be:

  1. Starting from all 3m the Albanian generals form 3 subsets of Albanians generals {A1, A2, A3}, each one with at most m generals. One subset (A1) contains all the traitors (that are m)
  2. Map the 3 subsets of Albanian generals {A1, A2, A3} to 3 Byzantine generals {g1, g2, g3}. The Byzantine general g1 represents the subset A1 that contains all the traitors. Therefore g1 is the traitor and, given the construction, they cannot be more than m. The other two sets contains loyal Albanian generals.
  3. Given the condition 1' and 2 in the text, and the derived IC1, IC2, map the generals g2, g3 to lieutenants t1, t2.

Posed in this way it is pretty simple. Nevertheless, the text use terms such as commanders (?), Albanian lieutenants (?), mixed up in a few lines. Probably the construction is more general than mine. My point (2.) assumes exactly m traitors. Maybe they do not make this assumption?

With a more general assumption, we might pose it differently. Let's use n as the number of Albanian generals. Given that we are building a solution for n general such that

  1. n = l + m (loyal g. and traitor g.)
  2. n <= 3m
  3. |A1| + |A2| + |A3| = n
  4. |A1| <= m
  5. all m in A1 (?)

then |A1| = m.

Given the minds of the paper, I fear that there is something that I don't grasp and I am looking for help:

  • What is the initial composition of the Albanian set? How many Generals and how many lieutenants (why to put lieutenants in this point of the construction)?
  • What do they mean by the term commanders? Generals plus lieutenants?
  • Is the construction more general than mine?

Maybe, it is a really stupid question, but I am a little lost here.

0

2 Answers 2

0

Maybe, I've understood so I answer my own question.

The term commander means commanding general and conditions 1', 2 are general; they do not pose limitation on n.

  • We have n <= 3m (m traitors) Albanians Generals that we divide in set of approx 1/3 of n;
  • For 1', 2 we can solve for 1 Albanian General in command (the ith, that is the one and only commander). The others Albanian Generals are Lieutenants;

So,

  • The Byzantine General in command represents the (ith) Albanian General in command plus at most m - 1 Lieutenants.
  • The Byzantine Lieutenants represents at most m Albanian Lieutenants.

Now, it is clear to me! I had a problem with the term commander and 1', 2 must be applied in advance.

Sorry for the silly question.

0

I have been thinking about this also and came to the conclusion that it is a type of recursive paradox, any solution applied to the problem requires the prerequisite condition of planning the attack outside of the location where the battle or attack is about to take place, and therefore negates the initial need for a solution to the problem. In my opinion there can be no answer because the problem has inherent in it the quality of confusion or deceit, which cannot be logically countered or reduced to a mathematical solution, it is trying to create a solution where there is no initial problem, as the prerequisite condition for solving the problem solves the problem.

I did also have the thought though that one solution to the problem would be to instill a hierarchy in rank, so there is essentially one acting general, but that again removes the problem before the problem would appear, so I think it is more useful as a thinking exercise that can be applied to specific situations, like Bitcoin mining etc., but has no actual logical solution because the solution recurses to a state that precludes the initial problem.

Or, if you treat it like an algebraic problem that would have a definite result, the result is failure of the three generals by necessity to satisfy the logical conditions of the problem, in the form of a constant.

Your Answer

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

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