Byzantine error

Example of a Byzantine error: Clock 3 is faulty and causes a Byzantine error by sending 500 (instead of 1000) one time and 1500 the other.

In information technology , Byzantine errors are errors in which a system behaves incorrectly at will. For example, a server occasionally sends incorrect answers and occasionally reaches incorrect system states. A Byzantine fault generally describes a fault model that is difficult to grasp.

In multiprocessor systems, the Byzantine error denotes a class of errors. If a component delivers different (protocol-compliant) results to different processors, it is called a Byzantine error. The planning assumes that processors are malicious and want to disrupt the system as much as possible. ${\displaystyle x}$

Origin of the designation

The adjective Byzantine refers to the problem of the Byzantine generals . When a city is under siege, several generals have a communication problem. Because of the strong fortifications, it is necessary that the generals and their troops attack the city from different directions at the same time. The generals can communicate with each other via messengers. However, some of the generals intrigue against others. Their goal is to discredit their competitors - for example, by trying to force the others to attack prematurely through cleverly disseminated misinformation. None of the generals now know what information is authentic and whom they can trust.

So there is a problem of agreement, which consists in the fact that the military leaders have to decide unanimously whether to attack or not. The problem is compounded by the spatial separation of the commanders ; so they have to send messengers back and forth. There is also the possibility that there may be traitors among the generals who could intentionally send misleading information to the other generals.

Mathematically, it turned out that under these conditions the loyal generals only have a chance of reaching an agreement if the share of schemers is less than a third. So there was no solution, especially with three generals, one of whom is an intriguer - at least not with the help of classic communication methods such as messengers.

solutions

The first publication of solutions to the problem of the Byzantine generals goes back to Leslie Lamport , Robert Shostak and Marshall Pease in 1982. They attributed the problem to a problem of the commander and lieutenant, where all loyal lieutenants must act in unison and their actions go along with it must comply with the orders of the commander if he is loyal. In short, the general votes by treating all other orders as votes.

• One solution explained considers the scenario in which messages are forged. As long as the proportion of traitorous generals is less than a third, this solution is tolerant of a Byzantine error. The impossibility of dealing with a third or more traitors reduces the problem to proving that the case with one commander and two lieutenants is unsolvable when the commander is a traitor. If there are three commanders are, with the traitor and by the message "attack" and by the message "withdrawal" is, then can not yet determine who is the traitor, if they mutually news of send. does not necessarily have to be the traitor because yes or the news of may have changed. ${\displaystyle (A,B,C)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle C}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle A}$

It can be shown that when the number of generals is and the number of traitors is within , there is only one solution if is, i.e. . h that there is a traitor in until four generals a solution because: . So if you have two traitors you need at least seven generals because: ${\displaystyle n}$ ${\displaystyle t}$ ${\displaystyle n}$ ${\displaystyle n\geq 3\cdot t+1}$ ${\displaystyle n\geq 3\cdot 1+1\Rightarrow n\geq 4}$ ${\displaystyle n\geq 3\cdot 2+1\Rightarrow n\geq 7}$

• A second solution requires non - forgery-proof signatures (in modern computer systems this is achieved through public-key cryptography). This gains fault tolerance with any number of treacherous generals. An implementation related to this solution is the blockchain .
• Another solution is a variation of the first two solutions that achieve Byzantine Error Tolerance if not all generals can communicate directly with each other.

literature

• Hermann Kopetz : Real-Time Systems. Kluwer Academic Publishers, April 1997, ISBN 0-7923-9894-7 .
• L. Lamport, R. Shostak, M. Pease: The Byzantine Generals Problem . In: ACM Trans. Programming Languages ​​and Systems . tape 4 , no. 3 , July 1982, p. 382-401 ( PDF , Leslie Lamport: My Writings ).

Web links

• Axel Tillemans: Swiss quantum physicists tame Byzantine generals. Retrieved September 14, 2019 . 
• Doris Reim, Bartek Ochab: The Byzantine Generals. (PDF) In: The Byzantine Generals Problem by Leslie Lamport, Robert Shostak, Marshall Pease. Technical University of Berlin , accessed on October 16, 2016 . 
• Esra Ünal: Seminar paper Byzantine mistakes. (PDF) In: Proseminar technical informatics. Free University of Berlin - Institute for Computer Science, accessed on October 16, 2016 . 

Individual evidence

1. ↑ Doris Reim, Bartek Ochab: The Byzantine Generals. (PDF) In: The Byzantine Generals Problem by Leslie Lamport, Robert Shostak, Marshall Pease. Technische Universität Berlin, p. 8 , accessed on February 5, 2018 . 
2. ↑ Doris Reim, Bartek Ochab: The Byzantine Generals. (PDF) In: The Byzantine Generals Problem by Leslie Lamport, Robert Shostak, Marshall Pease. Technische Universität Berlin, p. 14 , accessed on February 5, 2018 .