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.