In a recent paper (Schmid & Weiss, 2001), we showed how to avoid the
impossibility of deterministic consensus in presence of link faults
(Gray, 1978) for the well-known Oral and Written Messages
Byzantine agreement algorithms (Lamport, Shostak & Pease, 1982). In
this paper (This research is part of our W2F-project, which
targets a wireline/wireless fieldbus based upon spread-sprectrum
(CDMA) communications, see http://www.auto.tuwien.ac.at/Projects/W2F/
for details. W2F is supported by the Austrian START programme Y41-MAT.),
we analyze several alternative algorithms that do not require
messages of exponential size: An improved version of the
Phase Queen and Phase King consensus algorithms of (Berman, Garay & Perry,
1992) and the non-authenticated Byzantine agreement algorithm of
(Srikanth & Toueg, 1987) are shown to require just one additional
round and
  n > 2\ls + 2\lr + 2\lra + 4\a+2\s + 2\o + \c
  n > 2\ls + 2\lr + 2\lra + 3\a+2\s + 2\o + \c
  n > \ls + \lsa +  2\lr + 2\lra + 3\a+2\s + 2\o + \c
nodes, respectively, for tolerating at most \ls broadcast and \lr
receive link faults (including at most \lsa and \lra arbitrary ones)
per node in each round, in addition to at most \a, \s,
\o, \c arbitrary, symmetric, omission, and manifest node faults.
Being sub-optimal with respect to link faults, those resiliences
can be considered as the price for the algorithms' message
efficiency. An analysis of the assumption coverage in systems where
links fail independently with probability p reveals that adding
nodes for tolerating link faults results in a vanishing probability of
violating the fault model as long as np < 1. This confirms that our
algorithms can reasonably be employed even in wireless networks,
which suffer from low bandwidth and link failure probabilities up to
p=10^{-2}.

Keywords: Fault-tolerant distributed systems, hybrid fault models,
link faults, consensus, Byzantine agreement.