Consensus is one of the most fundamental distributed computing problems. In particular, it serves as a building block in many replication based fault-tolerant systems and in particular in multiple recent blockchain solutions. Depending on its exact variant and other environmental assumptions, solving consensus requires multiple communication rounds. Yet, there are known optimistic protocols that guarantee termination in a single communication round under favorable conditions. In this paper we present a generic optimizer than can turn any consensus protocol into an optimized protocol that terminates in a single communication round whenever all nodes start with the same predetermined value and no Byzantine failures occur (although node crashes are allowed). This is regardless of the network timing assumptions and additional oracle capabilities assumed by the base consensus protocol being optimized. In the case of benign failures, our optimizer works whenever the number of faulty nodes @math . For Byzantine behavior, our optimizer's resiliency depends on the validity variant sought. In the case of classical validity, it can accommodate @math Byzantine failures. With the more recent external validity function assumption, it works whenever @math . Either way, our optimizer only relies on oral messages, thereby imposing very light-weight crypto requirements.
The first work to explore one communication round consensus in the benign failure model is @cite_10 . The basic protocol in @cite_10 requires @math . That protocol is also extended to support a preferred value which improves the resiliency requirement to @math , similar to our work. The main contribution of this paper compared to @cite_10 is in our exploration of this problem under Byzantine failures and in the fact that we present a single generic optimizer for both failure models.
@cite_10
1516351775
This paper presents a very simple consensus protocol that converges in a single communication step in favorable circumstances. Those situations occur when "enough" processes propose the same value. ("Enough" means "at least (n-f)" where f is the maximum number of processes that can crash in a set of n processes.) The protocol requires f < n 3. It is shown that this requirement is necessary. Moreover, if all the processes that propose a value do propose the same value, the protocol always terminates in one communication step. It is also shown that additional assumptions can help weaken the f < n 3 requirement to f < n 2.