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:
- 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)
- 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.
- 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
- n = l + m (loyal g. and traitor g.)
- n <= 3m
- |A1| + |A2| + |A3| = n
- |A1| <= m
- 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.