We introduce a novel hybrid failure model, which facilitates an
accurate and detailed analysis of round-based synchronous,
partially synchronous and asynchronous distributed algorithms
under both process and link failures. Granting every process
in the system up to f_l send and receive link failures (with f_la
arbitrary faulty ones among those) in every round, without being
considered faulty, we show that the well-known randomized Byzantine
agreement algorithm of (Srikanth & Toueg 1987) needs just n >=
4f_l+ 2f_la +3f_a +1 processes for coping with f_a Byzantine faulty
processes. The probability of disagreement after R iterations is
only 2^{-R}, which is the same as in the FLP model and thus much
smaller than the lower bound O(1/R) known for synchronous
systems with lossy links. Moreover, we show that 2-stubborn links
are sufficient for this algorithm. Hence, contrasting widespread
belief, a perfect communications subsystem is not required for
efficiently solving randomized Byzantine agreement.

Fault-tolerant distributed systems, partially synchronous systems,
failure models, link failures, randomized Byzantine agreement,
consensus, stubborn links.