Fisheye Consistency: Keeping Data in Synch in a Georeplicated World

Roy Friedman, Michel Raynal, François Taı̈aniLecture Notes in Computer Science 2015 · DOI · arXiv · OpenAlex

Abstract

Georeplicated distributed systems face a fundamental tension between strong consistency guarantees and low-latency performance. While strong models like Sequential Consistency simplify programming, they incur significant overhead in wide-area networks. Conversely, weak models like Causal Consistency offer high availability but introduce complex anomalies. This paper introduces Fisheye Consistency, a hybrid model that bridges this gap by making consistency a function of network proximity. By enforcing Sequential Consistency for local nodes and Causal Consistency for distant ones, the model provides an intuitive programming experience for local operations without sacrificing global scalability. We formalize the model using a Proximity Graph and provide distributed algorithms for its implementation.

Introduction

The rise of global-scale cloud services has made georeplication a necessity for both fault tolerance and low-latency access. However, managing data across geographically dispersed data centers remains a challenge. The CAP theorem dictates that under network partitions, systems must choose between consistency and availability. In practice, this often translates to a trade-off between the strength of consistency guarantees and the latency of operations. This paper proposes a novel approach called Fisheye Consistency, which leverages the physical or logical distance between nodes to provide a tiered consistency model.

The Problem: The Latency-Consistency Trade-off

Traditional consistency models often treat all nodes uniformly. Strong models, such as Linearizability or Sequential Consistency (SC), require global coordination, which is prohibitively slow when nodes are separated by transcontinental distances. Weak models, such as Causal Consistency (CC), allow for high concurrency and low latency but can lead to "ordering anomalies." For instance, two nodes in the same data center might observe concurrent writes in different orders, complicating the development of correct applications.

The authors identify that proximity is a key factor often ignored in formal consistency definitions. Nodes that are "close" (e.g., in the same rack or data center) can afford the synchronization costs of SC, whereas "distant" nodes should fall back to CC to maintain performance. The goal is to formalize a model where consistency is a function of network proximity.

The Fisheye Consistency Model

The core of the proposal is the G-fisheye (SC, CC)-consistency model, defined over a Proximity Graph ($\mathcal{G}$). In this graph, vertices represent processes, and edges represent proximity. The model mandates two conditions:

  1. Global Causality: All operations in the system must satisfy Causal Consistency.
  2. Local Sequentiality: Operations performed by nodes that are neighbors in the proximity graph must additionally satisfy Sequential Consistency.

This "fisheye" approach provides high detail (stronger guarantees) for local interactions and lower detail (weaker guarantees) for remote ones. The model is highly flexible; it can represent pure CC if the graph has no edges, or pure SC if the graph is a complete clique.

Implementation and Algorithms

To realize this model, the authors present a Hybrid Broadcast Algorithm. This algorithm implements a "toco-broadcast" (Total and Causal Order), which ensures that messages are delivered according to causal order globally and in a total order among neighbors. The implementation utilizes vector clocks to track causality and logical clocks paired with FIFO channels to enforce total ordering within local neighborhoods.

Furthermore, the paper describes a read/write register implementation. It employs a "fast-read" strategy where read operations are local and non-blocking. Write operations, however, are broadcast to all replicas and block the sender until its own write is delivered back, ensuring the necessary ordering constraints are met before subsequent operations proceed.

Key Insights and Results

  • Distance as a First-Class Citizen: Proximity isn't just an optimization; it's baked into the formal semantics of the data. This allows developers to reason about what "remote" changes might look like versus "local" ones.
  • Functional vs. Operational: Unlike operational definitions found in systems like Apache Cassandra (e.g., QUORUM vs. LOCAL_QUORUM), Fisheye Consistency is defined functionally based on the history of operations and user perception.
  • Eliminating Ambiguity: The authors demonstrate through scenarios (e.g., a "Paris-Berlin-New York" setup) how Fisheye Consistency prevents specific ordering anomalies that occur in pure Causal Consistency, such as two nearby nodes seeing their own concurrent writes in conflicting orders.
  • Formal Proofs: The primary result is a rigorous mathematical proof that their distributed algorithms correctly implement the Fisheye Consistency model.

Limitations and Future Work

While the theoretical benefits are clear, the paper does not provide experimental results showing exactly how much latency is saved or how throughput scales in a real-world deployment like AWS or Azure. Additionally, the current algorithm assumes reliable channels and doesn't deeply explore node failures or dynamic changes to the proximity graph.

Future research could explore other hybrid pairings, such as Linearizability and Sequential Consistency, or integrate these concepts into Conflict-free Replicated Data Types (CRDTs) to handle non-commutative operations within local "islands" of strong consistency.

Summary updated

BibTeX
@inproceedings{friedman2015fisheye,
  author = {Roy Friedman and Michel Raynal and François Taı̈ani},
  title = {{Fisheye Consistency: Keeping Data in Synch in a Georeplicated World}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2015},
  doi = {10.1007/978-3-319-26850-7\_17},
}
Figure