Byzantine fault tolerance

A Byzantine fault referred to in multiprocessor systems, an error class. If a component on different processors provides different ( protocol- compliant ) results, one speaks of a Byzantine fault. When planning, it is assumed that x processors operate maliciously and want to disturb the system maximum.

Origin of name

The adjective Byzantine refers to the problem of Byzantine Generals. It is a problem of the agreement, which is that the commander must decide unanimously whether to attack an enemy army or not. The problem is complicated by the spatial separation of the commander; so they must messengers back and forth. There is also the possibility that among the generals are traitors can that can intentionally send it to the other generals misleading information.

Solutions

The first publication with solutions to the problem of Byzantine Generals goes back to Lamport, Shostak and Pease in 1982. They led the problem to a " commander and lieutenant " problem back, with all loyal lieutenants must act in unison and their actions with the must match commands of the commander if he is loyal. In short, the general chooses, by dealing with all other commands as votes.

• An Illustrated solution considered the scenario in which messages are fake. As long as the proportion of traitorous generals is less than one-third, this solution is tolerant of Byzantine faults. The inability to deal with a third or more of betrayers, the problem reduces to the proof that a " one commander and two lieutenants " problem is not solvable if the commander is a traitor. If there are three commanders (A, B, C), where A is the traitor, and B of A, the message "attack", and C of A receives the message " retreat ", then neither B nor C determine who the traitor is when they send each other the news of A. A need not necessarily be the traitor, since we also have B or C may have changed the message of A.

• A second solution requires not fälschbare signatures ( in modern computer systems, this is achieved through public-key cryptography). It receives forgiveness on any number of treacherous generals.
• Another solution is reached, a variation of the first two solutions, the Byzantine fault tolerance, if not all generals can communicate directly with each other.