Consensus-Oriented Parallelization: How to Earn Your First Million – To appear in Middleware ’15 –

Consensus protocols employed in Byzantine fault-tolerant systems are notoriously compute intensive. Unfortunately, the traditional approach to execute instances of such pro-tocols in a pipelined fashion is not well suited for mod-ern multi-core processors and fundamentally restricts the overall performance of systems based on them. To solve this problem, we present the consensus-oriented paralleliza-tion (COP) scheme, which disentangles consecutive consen-sus instances and executes them in parallel by independent pipelines; or to put it in the terminology of our main target, today’s processors: COP is the introduction of superscalar-ity to the field of consensus protocols. In doing so, COP achieves 2.4 million operations per second on commodity server hardware, a factor of 6 compared to a contemporary pipelined approach measured on the same code base and a factor of over 20 compared to the highest throughput num-bers published for such systems so far. More important, however, is: COP provides up to 3 times as much through-put on a single core than its competitors and it can make use of additional cores where other approaches are confined by the slowest stage in their pipeline. This enables Byzan-tine fault tolerance for the emerging market of extremely demanding transactional systems and gives more room for conventional deployments to increase their quality of service