Editing Byzantine fault (section)

== Definition ==

A Byzantine fault is any fault presenting different symptoms to different observers.<ref name="DriscollHall2004">{{cite book| last1=Driscoll| first1=K.| title=The 23rd Digital Avionics Systems Conference (IEEE Cat. No.04CH37576)| last2=Hall| first2=B.| last3=Paulitsch| first3=M.| last4=Zumsteg| first4=P. |last5=Sivencrona| first5=H.| chapter=The Real Byzantine Generals| year=2004| pages=6.D.4–61–11| doi=10.1109/DASC.2004.1390734| isbn=978-0-7803-8539-9| s2cid=15549497}}</ref> A Byzantine failure is the loss of a system service due to a Byzantine fault in systems that require [[Consensus (computer science)|consensus]] among multiple components.<ref name="DriscollHall2003">{{cite book| last1=Driscoll| first1=Kevin| title=Computer Safety, Reliability, and Security| last2=Hall| first2=Brendan| last3=Sivencrona| first3=Håkan| last4=Zumsteg| first4=Phil | s2cid=12690337| chapter=Byzantine Fault Tolerance, from Theory to Reality| volume=2788| year=2003| pages=235–248| issn=0302-9743| doi=10.1007/978-3-540-39878-3_19| series=Lecture Notes in Computer Science| isbn=978-3-540-20126-7}}</ref>

[[File:Byzantine Generals.png|thumb|upright=1.3|If all generals attack in coordination, the battle is won (left). If two generals falsely declare that they intend to attack, but instead retreat, the battle is lost (right).]]
The Byzantine allegory considers a number of generals who are attacking a fortress. The generals must decide as a group whether to attack or retreat; some may prefer to attack, while others prefer to retreat. The important thing is that all generals agree on a common decision, for a halfhearted attack by a few generals would become a [[rout]], and would be worse than either a coordinated attack or a coordinated retreat.

The problem is complicated by the presence of treacherous generals who may not only cast a vote for a suboptimal strategy; they may do so selectively. For instance, if nine generals are voting, four of whom support attacking while four others are in favor of retreat, the ninth general may send a vote of retreat to those generals in favor of retreat, and a vote of attack to the rest. Those who received a retreat vote from the ninth general will retreat, while the rest will attack (which may not go well for the attackers). The problem is complicated further by the generals being physically separated and having to send their votes via messengers who may fail to deliver votes or may forge false votes.

Without message signing, Byzantine fault tolerance can only be achieved if the total number of generals is greater than three times the number of disloyal (faulty) generals. There can be a default vote value given to missing messages. For example, missing messages can be given a [[Uninitialized variable|"null" value]]. Further, if the agreement is that the null votes are in the majority, a pre-assigned default strategy can be used (e.g., retreat).<ref name="BGP_Paper">{{Cite journal|last1=Lamport|first1=L.|author-link1=Leslie Lamport|last2=Shostak|first2=R.|last3=Pease|first3=M.|year=1982|title=The Byzantine Generals Problem|url=http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf|journal=ACM Transactions on Programming Languages and Systems|volume=4|issue=3|pages=387–389|citeseerx=10.1.1.64.2312|doi=10.1145/357172.357176|s2cid=55899582 |archive-url=https://web.archive.org/web/20170207104645/http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf|archive-date=7 February 2017}}</ref>

The typical mapping of this allegory onto computer systems is that the computers are the generals and their digital communication system links are the messengers. Although the problem is formulated in the allegory as a decision-making and security problem, in electronics, it cannot be solved by [[cryptographic]] [[digital signature]]s alone, because failures such as incorrect voltages can propagate through the encryption process. Thus, a faulty message could be sent such that some recipients detect the message as faulty (bad signature), others see it is having a good signature, and a third group also sees a good signature but with different message contents than the second group.<ref name="DriscollHall2004">{{cite book| last1=Driscoll| first1=K.| title=The 23rd Digital Avionics Systems Conference (IEEE Cat. No.04CH37576)| last2=Hall| first2=B.| last3=Paulitsch| first3=M.| last4=Zumsteg| first4=P. |last5=Sivencrona| first5=H.| chapter=The Real Byzantine Generals| year=2004| pages=6.D.4–61–11| doi=10.1109/DASC.2004.1390734| isbn=978-0-7803-8539-9| s2cid=15549497}}</ref>