Why You Can't Beat Blockchains: Consistency and High Availability in Distributed Systems
We study the issue of data consistency in highly-available distributed systems. Specifically, we consider a distributed system that replicates its data at multiple sites, which is prone to partitions, and which is expected to be highly available. In such a setting, strong consistency, where all replicas of the system apply synchronously every operation, is not possible to implement. However, many weaker consistency criteria that allow a greater number of behaviors than strong consistency, are implementable in distributed systems. We focus on determining the strongest consistency criterion that can be implemented in a distributed system that tolerates partitions. We show that no criterion stronger than Monotonic Prefix Consistency (MPC) can be implemented. MPC is the consistency criterion underlying blockchains.
1710.09209.pdf
Preprint
openaccess
215.41 KB
Adobe PDF
0bcb007e5367cc0d5f7c62f7f684a849