  The Byzantine agreement problem requires a set of $n$ processes to agree on a
value sent by a transmitter, despite a subset of $b$ processes behaving in an
arbitrary, i.e. Byzantine, manner and sending corrupted messages to all
processes in the system. It is well known that the problem has a solution in a
(an eventually) synchronous message passing distributed system iff the number
of processes in the Byzantine subset is less than one third of the total number
of processes, i.e. iff $n > 3b+1$. The rest of the processes are expected to be
correct: they should never deviate from the algorithm assigned to them and send
corrupted messages. But what if they still do?
  We show in this paper that it is possible to solve Byzantine agreement even
if, beyond the $ b$ ($< n/3 $) Byzantine processes, some of the other processes
also send corrupted messages, as long as they do not send them to all. More
specifically, we generalize the classical Byzantine model and consider that
Byzantine failures might be partial. In each communication step, some of the
processes might send corrupted messages to a subset of the processes. This
subset of processes - to which corrupted messages might be sent - could change
over time. We compute the exact number of processes that can commit such
faults, besides those that commit classical Byzantine failures, while still
solving Byzantine agreement. We present a corresponding Byzantine agreement
algorithm and prove its optimality by giving resilience and complexity bounds.
