Editing Byzantine fault (section)

== History ==

The problem of obtaining Byzantine consensus was conceived and formalized by [[Robert Shostak]], who dubbed it the ''interactive consistency'' problem. This work was done in 1978 in the context of the NASA-sponsored SIFT<ref name=":0" /> project in the Computer Science Lab at [[SRI International]]. SIFT (for Software Implemented Fault Tolerance) was the brainchild of John Wensley, and was based on the idea of using multiple general-purpose computers that would communicate through pairwise messaging in order to reach a consensus, even if some of the computers were faulty.

At the beginning of the project, it was not clear how many computers in total were needed to guarantee that a conspiracy of ''n'' faulty computers could not "thwart" the efforts of the correctly-operating ones to reach consensus. Shostak showed that a minimum of 3''n+''1 are needed, and devised a two-round 3''n+1'' messaging protocol that would work for ''n''=1. His colleague Marshall Pease generalized the algorithm for any n > 0, proving that 3''n''+1 is both necessary and sufficient. These results, together with a later proof by [[Leslie Lamport]] of the sufficiency of 3''n'' using digital signatures, were published in the seminal paper, ''Reaching Agreement in the Presence of Faults.''<ref>{{Cite journal|last1=Pease|first1=Marshall|last2=Shostak|first2=Robert|last3=Lamport|first3=Leslie|date=April 1980|title=Reaching Agreement in the Presence of Faults|journal=Journal of the Association for Computing Machinery|volume=27|issue=2|pages=228–234|doi=10.1145/322186.322188|citeseerx=10.1.1.68.4044|s2cid=6429068}}</ref> The authors were awarded the 2005 [[Edsger W. Dijkstra Prize]] for this paper.

To make the interactive consistency problem easier to understand, Lamport devised a colorful allegory in which a group of army generals formulate a plan for attacking a city. In its original version, the story cast the generals as commanders of the [[Albania]]n army. The name was changed, eventually settling on "[[Byzantine Empire|Byzantine]]", at the suggestion of Jack Goldberg to future-proof any potential offense-giving.<ref>{{cite journal |last1=Lamport |first1=Leslie |title=The Byzantine Generals Problem |url=https://www.microsoft.com/en-us/research/publication/byzantine-generals-problem/ |journal=ACM Transactions on Programming Languages and Systems |publisher=SRI International |access-date=18 March 2019|date=2016-12-19 }}</ref> This formulation of the problem, together with some additional results, were presented by the same authors in their 1982 paper, "The Byzantine Generals Problem".<ref name=BGP_Paper />