The New CAP Theorem on Blockchain Consensus Systems

One of the most emblematic theorems in the theory of distributed databases is the Eric Brewer’s CAP theorem. It stresses the tradeoffs between Consistency, Availability and Partition and states that it is impossible to guarantee all three of them simultaneously. Inspired by this, we introduce the new CAP theorem for autonomous consensus systems, and we demonstrate that of the three elementary properties, Consensus achievement (C), Autonomy (A) and entropic Performance (P), two at the most can be optimized at any given time. To formalize and analyze this tradeoff, we utilize the IoT micro-Blockchain as a universal, minimal, consensus-enabling framework. We define a set of quantitative functions relating each of the properties to the number of event-witnesses in the system. We identify the existing mutual exclusions, and we demonstrate that (A), (C), and (P) cannot be optimized simultaneously. This imposes an intrinsic limitation on the design and the optimization of distributed Blockchain consensus mechanisms.