The Byzantine Agreement problem is widely known as a fundamental
problem in fault-tolerant distributed computing. It was introduced
by Lamport, Shostak and Pease in 1980. In 1978 Gray proved that it
is impossible to solve the related Coordinated Attack problem when
links may be faulty. However, Schmid and Weiss showed how to avoid
this result by limiting the uncertainty that faulty links can
generate in each round.

Usually very simple fault models are used in the analysis of
distributed algorithms, but by refining the model through
classifying faults the number of necessary processors can be
reduced tremendously. To account for processor and link faults
in a uniform way Schmid developed the perception-based fault
model, which he and Weiss later refined for use with Byzantine
agreement protocols.

Along with stating the problem Lamport, Shostak and Pease also
presented an algorithm for solving Consensus. Unfortunately this
algorithm needs messages of exponential size. Later research has
produced polynomial protocols, three of which I adapted to overcome
link faults. These protocols are all presented in this thesis.