This paper addresses the following question: what is the minimum-sized synchronous window needed to solve consensus in an otherwise asynchronous system? In answer to this question, we present the first optimally-resilient algorithm ASAP that solves consensus as soon as possible in an eventually synchronous system, i.e., a system that from some time GST onwards, delivers messages in a timely fashion. ASAP guarantees that, in an execution with at most f failures, every process decides no later than round GST + f + 2, which is optimal.
展开▼
机译：本文解决了以下问题：在异步系统中解决共识所需的最小同步窗口是多少？为了回答这个问题，我们提出了第一个最优弹性算法ASAP，该算法可以在最终同步的系统（即从GST开始的某个时间起，可以及时传递消息的系统）中尽快解决共识问题。 ASAP保证，在执行最多失败次数为f的执行中，每个进程的决策不迟于GST + f + 2，这是最佳选择。
展开▼
