Breaking the O(√ n)-Bit Barrier
Elette Boyle, Ran Cohen, Aarushi Goel
Abstract
Byzantine agreement (BA), the task of n parties to agree on one of their input bits in the face of malicious agents, is a powerful primitive that lies at the core of a vast range of distributed protocols. Interestingly, in BA protocols with the best overall communication, the demands of the parties are highly unbalanced: the amortized cost is Õ(1) bits per party, but some parties must send Ω(n) bits. In best known balanced protocols, the overall communication is sub-optimal, with each party communicating Õ(√n).
Topics & Concepts
Computer scienceBit (key)Task (project management)Core (optical fiber)Range (aeronautics)Computer networkTheoretical computer scienceComputer securityDistributed computingTelecommunicationsEngineeringAerospace engineeringSystems engineeringCryptography and Data SecurityDistributed systems and fault toleranceBlockchain Technology Applications and Security