Byzantine Fault Tolerance

Consider the simple (!) problem of getting a value of a variable from a distributed (containing multiple servers) storage system that uses replication to ensure correctness.

Basic problem in such a system would be inaccessible servers. Assuming that there would be inaccessible servers, as long as there are servers in the system, value of queried from this system would be correct.

However, things get uglier if servers can behave the worst possible way: lie about the value of a variable.

If in addition to inaccessible servers, servers can lie about a value of a variable, the number of servers we would need to provide correctness would be due to the fact that it is not possible to differentiate between right and wrong answers. The solution is to use majority ().

Systems tolerant to lying parts are called “Byzantine fault-tolerant” systems. The term was coined in  this paper and the name comes from a representation of the problem at hand in a war scenario: Byzantine generals trying to get to a consensus for a decision on “attack” or “retreat”.