This paper shows that
deterministic consensus in synchronous distributed systems with link
failures is possible, despite the impossibility result [Gray
1978]. Instead of using randomization, we overcome this
impossibility result by moderately restricting the inconsistency that
link failures may cause system-wide. Relying upon a novel
hybrid failure model that provides different classes of failures for both
processes and links in a round-by-round fashion, we prove that the $m+1$-round
Byzantine agreement algorithms OMH [Lincoln and Rushby 1993]
and its authenticated variants OMHA, ZA [Gong et al.\ 1995] require

n > 3\l + \la + 2(\a+\s) + \o + \c + m
n > 3\l + 2(\a+\s) + \o + \c + m
n > 2\l + \a + \s  +\o + \c + 1

processes for transparently masking at most $\l$ link failures
(including at most $\la$ arbitrary ones) per process in each round,
in addition to at most $\a$, $\s$, $\o$, $\c$ arbitrary, symmetric,
omission, and manifest process failures, provided that $m\geq
\a+\o+1$. If authentication fails,
we show that OMHA degrades to OMH, whereas ZA can be made
tolerant to broken signatures by increasing $\a$ accordingly.
A uniform variant of OMH is also proposed, which guarantees
validity and agreement even on benign faulty processes. These specific
results are complemented by a systematic theoretical study of
consensus under link failures. We provide impossibility results and
(tight) lower bounds for the required number of processes and rounds,
as well as a precise characterization of what makes a process failure
Byzantine resp.\ omissive. Moreover, we explore the applicability of our
approach to systems with incomplete communication graphs.  Finally, an
analysis of the assumption coverage in systems where links fail
independently is provided, which reveals that the probability of
violating the failure model can be made arbitrarily small by
sufficiently increasing $n$.


Keywords: Assumption coverage, authentication, Byzantine agreement, 
failure models, fault-tolerant distributed systems, impossibility results,
link failures, lower bounds, uniform consensus