Buterin's Scalability Trilemma viewed through a State-change-based Classification for Common Consensus Algorithms

Abstract

Consensus algorithms in distributed systems have attracted much attention in recent studies. However, there is a need for a classification that leads to better understanding and helps direct the deployment of such algorithms. In this paper, we classify common consensus algorithms based on how they decide the order of system state changes. We then determine the extent to which each category prioritizes scalability, decentralization, and security. As with other engineering design scenarios, this is a choose-two tradeoff. Our key contribution is that, based on this taxonomy of tradeoffs, we are able to discern the types of consensus algorithms that work well within the application area(s) for a given distributed system. We find that a dichotomy of algorithms between leader-based and voting-based consensus algorithms emerges from this taxonomy. Applications of this classification scheme include several different categories of distributed ledgers such as blockchains and directed acyclic graphs (DAGs).