  Byzantine Agreement introduced in [Pease, Shostak, Lamport, 80] is a widely
used building block of reliable distributed protocols. It simulates broadcast
despite the presence of faulty parties within the network, traditionally using
only private unicast links. Under such conditions, Byzantine Agreement requires
more than 2/3 of the parties to be compliant. [Fitzi, Maurer, 00], constructed
a Byzantine Agreement protocol for any compliant majority based on an
additional primitive allowing transmission to any two parties simultaneously.
They proposed a problem of generalizing these results to wider channels and
fewer compliant parties. We prove that 2f < kh condition is necessary and
sufficient for implementing broadcast with h compliant and f faulty parties
using k-cast channels.
