Byzantine agreement in polynomial time with near-optimal resilience
Shang-En Huang, Seth Pettie, Leqi Zhu · 2022
It has been known since the early 1980s that Byzantine Agreement in the full information, asynchronous model is impossible to solve deterministically against even one crash fault [FLP 1985], but that it can be solved with probability 1 [Ben-Or 1983], even against an adversary that controls the scheduling of all messages and corrupts up to f