Valerie King (University of Victoria)
Calvin Lab Room 116
The problem of Byzantine agreement, to bring players to agreement on a bit held by at least one of the players, is a fundamental challenge that has been studied for over 40 years. It has long been known that an adversary which controls the scheduling of messages in an asynchronous system and the occurrence of a single crash fault can prevent agreement if the players are restricted to a deterministic protocol. In 1983, Ben-Or gave a randomized protocol which was resilient to an adversary with full information of the state of all players, the ability to control all message scheduling in an asynchronous model, and the ability to control the behavior of a constant fraction of players which it may choose to corrupt adaptively. However this protocol has exponential time.
In 2014, Jared Saia and I were able to bring the time down to polynomial by introducing a new idea: the identification of corrupted players though statistical detection of bias in their coinflipping; however our protocols were resilient to only a very small constant fraction of bad players. (See JACM 2016). In a paper to appear in STOC 2022, Shang—En Huang, Seth Pettie and Leqi Zhu bring the resilience down to nearly optimal, < n/4, but with an added polynomial factor of time.
The optimal time/resilience tradeoff remains an open question.