Abstract
We study the issue of data consistency in distributed systems. Specifically, we consider a distributed system that replicates its data at multiple sites, which is prone to partitions, and which is assumed to be available (in the sense that queries are always eventually answered). 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 available distributed systems. We focus on determining the strongest consistency criterion that can be implemented in a convergent and available distributed system that tolerates partitions. We focus on objects where the set of operations can be split into updates and queries. We show that no criterion stronger than Monotonic Prefix Consistency (MPC) can be implemented.
Introduction
The CAP theorem has long dictated the boundaries of distributed systems design, establishing a fundamental trade-off between consistency, availability, and partition tolerance. In any system that must remain available during a network partition, "strong consistency"—where every node maintains an identical state in real-time—is mathematically impossible. This reality has led to the development of various "weak" consistency models, such as Eventual Consistency or Causal Consistency.
However, a critical theoretical question remained: what is the absolute "ceiling" of consistency? If we cannot achieve strong consistency, what is the strongest possible guarantee we can provide while maintaining high availability and convergence? This research identifies that ceiling as Monotonic Prefix Consistency (MPC) and provides a formal proof that no stronger model can be implemented in a convergent, available, and partition-tolerant system.
Defining the Model: Availability and Convergence
The study focuses on distributed systems that replicate data across multiple sites. The authors assume two primary requirements for these systems:
- High Availability: Every query made to a site must eventually receive a response, even if that site is temporarily disconnected from the rest of the network.
- Convergence: The system must eventually reach a state where all updates made at any site are reflected across all other sites.
To analyze these systems, the researchers utilize a formal model of "traces." A trace records the observations of a client, including the set of updates performed and the sequence of queries returned at each site. By focusing on a "list" data type—where updates consist of appending elements—the authors can map how different sites perceive the growth of the shared data structure.
Monotonic Prefix Consistency (MPC)
The core contribution of the paper is the formalization and analysis of Monotonic Prefix Consistency. MPC is defined by three specific rules that govern how a site observes data:
- Monotonicity: A site’s view of the data can only grow; it never shrinks or reverts to an earlier state. Once a client sees an update, that update remains visible in all subsequent queries at that site.
- Prefix: There exists a single global sequence of updates. While different sites may see different lengths (prefixes) of this sequence at any given time, they must all agree on the order of the elements they do see.
- Consistency: The system is "honest" in that queries only return data that was actually written by an update operation.
The Impossibility Result
The researchers provide a mathematical proof (Theorem 1) demonstrating that MPC is the strongest achievable consistency model for available, convergent systems. The proof logic suggests that if a system attempts to enforce a consistency model strictly stronger than MPC—for example, by requiring sites to agree on the exact same prefix length at all times—the system will inevitably be forced to "stall" during a network partition. In such a scenario, the system would have to choose between violating its consistency rules or failing to provide a response, thereby sacrificing availability.
To demonstrate that MPC is indeed achievable, the authors provide a "toy" implementation using a centralized sequencer to order updates. This proves that while MPC is the upper limit, it is a functional and implementable baseline for distributed architecture.
Discussion: Blockchains and Causal Consistency
This theoretical framework provides significant insight into the design of modern decentralized systems, most notably blockchains. Popular protocols like Bitcoin essentially aim for MPC. In the Bitcoin network, honest participants agree on a common prefix of the blockchain. While different nodes may be at different block heights (different prefix lengths), they agree on the history of the chain, which only grows over time. This paper provides the formal justification for why blockchains settle for this specific consistency model: it is the best they can do without losing availability.
Furthermore, the paper clarifies the relationship between MPC and Causal Consistency. Interestingly, the two are "incomparable." MPC is stronger in the sense that it enforces a single global order for all updates across the entire system. Causal Consistency, conversely, is stronger in its respect for the specific "session" order of a single user's requests but allows unrelated updates to appear in different orders on different sites.
Conclusion and Future Work
By establishing MPC as the consistency ceiling, this research provides a definitive map for distributed systems engineers. It suggests that for any system where availability is non-negotiable, MPC represents the gold standard of data integrity.
Future research directions include expanding this proof to more complex data types beyond simple lists, such as stacks or registers where operations might simultaneously query and update state. Additionally, the authors aim to address the "origin problem"—investigating if the strongest achievable consistency changes when the physical location or timing of an update is visible to the client. Finally, extending these "hard" impossibility results to the probabilistic consistency models used in real-world blockchains remains a key area for further exploration.
Summary updated