Paper review of "The Byzantine Generals Problem" by Lamport et al.
Name: Luiz Gustavo Bizarro Mirisola
They discuss an abstract problem involving reliable communication
among a set of entities, whose results after can be applied in
distributed systems development. Nevertheless, they suppose completely
arbitrary malfunctioning and a very high level of required
reliability, that imply in expensive algorithms that require a lot of
messages among all the communicating entities. In many systems you can
relax some of these assumptions, e.g. assuming that if there is a
response, it will be correct, and therefore avoid the expense of such
guaranteed reliability algorithms. But it is proved to be the only
solution to guarantee extreme reliability.
The abstract problem can be described as follows:
Given some divisions of an army (the Byzantine army - I guess that
they call it Byzantine because the nodes will be involved into a very
long quarrelling) camped around a city, they should communicate among
themselves and decide upon what action to take. There can be traitors
among the division-commander generals.
The algorithm must guarantee, that, after all the message
exchange:
A - All loyal generals decide upon the same plan (what implies
that they have agreed upon the same information)
B - a small number of traitors can not cause the loyal generals
not to agree upon the same plan. Of course it is interesting to know
how many traitors are permitted.
As A and B can be expressed as functions of each single value sent
by each general, the problem can be reduced to how a single commanding
general send an order to a group of lieutenants, with the following
conditions:
IC1 - All loyal lieutenants obey the same order;
IC2 - If the commanding general is loyal, then every loyal
lieutenant obeys his order.
The above problem can be used to solve the original Byzantine
Generals problem but the algorithm must satisfy both conditions even
if the commanding general is a traitor and sends different messages to
the different lieutenants.
They present algorithms to solve the Byzantine generals problem
under various hypothesis. With oral messages (without signature,
although the receiver knows who has sent the message), the problem can
be solved for m traitors if there are at least 3m+1 nodes.
With signed messages, the algorithm makes all the lieutenants sign
the original order received (signed) from the general, and exchange
signed orders until they have orders signed by all the
lieutenants. They can resolve the problem for any number of nodes,
although if you want to be protected against a higher number of
traitors, you should increase the size of the recursion.
Finally they modify the algorithm to be used in some classes of
non-complete graphs.
The paper extracts a generic abstract problem from the real life,
and solves it theoretically (transforming it in a simpler problem (one
general and lieutenants)), and after analyses in witch situations you
can apply that solution.