Byzantine Agreement with Faulty Majority using Bounded BroadcastByzantine Agreement • October 29th, 2018
Contract Type FiledOctober 29th, 2018Byzantine Agreement introduced in [Pease, Shostak, Lamport, 80] is a widely used building block of reliable distributed protocols. It sim- ulates broadcast despite the presence of faulty parties within the network, traditionally using only private unicast links. Under such condi- tions, Byzantine Agreement requires more than 2/3 of the parties to be compliant. [Fitzi, Mau- rer, 00], constructed a Byzantine Agreement pro- tocol for any compliant majority based on an ad- ditional 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 suffi- cient for implementing broadcast with h compli- ant and f faulty parties using k-cast channels.