  The recent surge of blockchain systems has renewed the interest in
traditional Byzantine fault-tolerant consensus protocols. Many such consensus
protocols have a primary-backup design in which an assigned replica, the
primary, is responsible for coordinating the consensus protocol. Although the
primary-backup design leads to relatively simple and high performance consensus
protocols, it places an unreasonable burden on a good primary and allows
malicious primaries to substantially affect the system performance. In this
paper, we propose a protocol-agnostic approach to improve the design of primary
backup consensus protocols. At the core of our approach is a novel wait-free
approach of running several instances of the underlying consensus protocol in
parallel. To yield a high performance parallelized design, we present
coordination-free techniques to order operations across parallel instances,
deal with instance failures, and assign clients to specific instances.
Consequently, the design we present is able to reduce the load on individual
instances and primaries, while also reducing the adverse effects of any
malicious replicas.
