Error-free Multi-valued Broadcast and Byzantine Agreement with Optimal Communication ComplexityJune 13th, 2011
FiledJune 13th, 2011In this paper we present first ever error-free, asynchronous broadcast (called as A-cast) and Byzan- tine Agreement (called as ABA) protocols with optimal communication complexity and fault tolerance. Our protocols are multi-valued, meaning that they deal with l bit input and achieve communication com- plexity of (nl) bits for large enough l for a set of n 3t+l parties in which at most t can be Byzantine corrupted.