This paper shows that deterministic consensus with written messages
is possible in the presence of link faults. As in our analysis
of consensus with oral messages (OMH), we circumvent the
impossibility result of (Gray, 1978) by limiting the degree of
inconsistency caused by link faults in the broadcasts of a single
sender resp. the receptions of a single receiver. Relying upon a
suitable perception-based hybrid fault model, we prove
that the m+1-round Authenticated Hybrid Oral Messages
(``Byzantine Generals'') algorithm OMHA(m) of (Gong, Lincoln &
Rushby, 1995) needs n> 2\ls + \lr + 2(\a+\s) + \c + m processes for
tolerating at most \lr receive link faults per process, \ls broadcast
link faults per process, and \a <= m-1, \s, \c arbitrary, symmetric,
and manifest process faults. A considerably better fault-tolerance degree is
established for their simple authenticated algorithm ZA(m),
which needs only n > \ls + \lr + \a + \s + \c + 1 processes
for coping with the same number of faults. In case of broken
signatures, OMHA degrades to OMH and hence requires an additional
\lra in the above lower bound for n, where \lra is the number of
non-omission link faults. For ZA, a process with a
compromised signature must be considered as arbitrary faulty and
hence be counted in \a. Authenticated algorithms for consensus
are therefore reasonably applicable even in wireless systems,
where link faults and intrusions are the dominating source of errors.

Keywords: Fault-tolerant distributed systems, fault models,
link faults, consensus, Byzantine generals, written messages,
authentication.