  Byzantine Agreement is a key component in many distributed systems. While
Dolev and Reischuk have proven a long time ago that quadratic communication
complexity is necessary for worst-case runs, the question of what can be done
in practically common runs with fewer failures remained open. In this paper we
present the first Byzantine Broadcast algorithm with $O(n(f+1))$ communication
complexity, where $0\leq f\leq t$ is the actual number of process failures in a
run. And for BA with strong unanimity, we present the first optimal-resilience
algorithm that has linear communication complexity in the failure-free case and
a quadratic cost otherwise.
