Conference paper

How to solve consensus in the smallest window of synchrony

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.

Related material