Braud-Santoni, NicolasGuerraoui, RachidHuc, Florian2014-05-282014-05-282014-05-28201310.1145/2484239.2484243https://infoscience.epfl.ch/handle/20.500.14299/103743This paper presents the first probabilistic Byzantine Agreement algorithm whose communication and time complexities are poly-logarithmic. So far, the most effective probabilistic Byzantine Agreement algorithm had communication complexity and time complexity. Our algorithm is based on a novel, unbalanced, almost everywhere to everywhere Agreement protocol which is interesting in its own right.byzantine agreementrandomized algorithmtext::conference output::conference proceedings::conference paper