PaperlayerView exact revision on arXiv

Source-linked AI summary

Consistency in Non-Transactional Distributed Storage Systems

Paolo Viotti, Marko Vukolić

arXiv:1512.00168v4cs.DC

TL;DR

Distributed-systems research has accumulated many consistency notions without a structured, comprehensive overview. This paper surveys and formally organizes more than 50 non-transactional semantics, then relates them to practical systems and research prototypes; its scope complements transactional-consistency surveys.

  • Problem

    After roughly four decades of research, the literature lacked a structured and comprehensive overview of consistency notions relevant to distributed and storage systems.

  • Method

    The paper surveys more than 50 non-transactional consistency semantics using an abstract-execution framework, defining many formally, ordering their strengths, and mapping them to systems and prototypes.

  • Results

    The survey provides formal definitions, informal descriptions, a semantic partial order, and references connecting consistency models with practical systems and research prototypes.

  • Takeaways & Limitations

    The framework and ordering help clarify subtle differences and tradeoffs among consistency models for evaluating and comparing distributed systems.

  • Takeaways & Limitations

    The survey focuses on read/write storage and non-transactional single-object semantics, complementing rather than covering transactional database consistency.

Abstract

from arXiv · show

Over the years, different meanings have been associated to the word consistency in the distributed systems community. While in the '80s "consistency" typically meant strong consistency, later defined also as linearizability, in recent years, with the advent of highly available and scalable systems, the notion of "consistency" has been at the same time both weakened and blurred. In this paper we aim to fill the void in literature, by providing a structured and comprehensive overview of different consistency notions that appeared in distributed systems, and in particular storage systems research, in the last four decades. We overview more than 50 different consistency notions, ranging from linearizability to eventual and weak consistency, defining precisely many of these, in particular where the previous definitions were ambiguous. We further provide a partial order among different consistency predicates, ordering them by their semantic "strength", which we believe will reveal useful in future research. Finally, we map the consistency semantics to different practical systems and research prototypes. The scope of this paper is restricted to non-transactional semantics, i.e., those that apply to single storage object operations. As such, our paper complements the existing surveys done in the context of transactional, database consistency semantics.

1 Introduction

The paper addresses the lack of a structured overview of consistency notions in distributed storage research. It develops a framework and survey covering more than 50 semantics, their relative strength, and practical implementations.

  • Motivation and contributions: The paper fills a stated gap: after four decades of research, distributed systems literature lacked a structured and comprehensive overview of consistency notions.
  • Motivation and contributions: Over 50 consistency notions are surveyed, spanning linearizability, eventual consistency, and weak consistency, with ambiguous definitions clarified.The survey also provides references to primary definitions and related implementations.
  • Scope: The scope is restricted to non-transactional semantics for single storage-object operations, complementing surveys of transactional database consistency.
  • Framework and organization: The framework models distributed systems asynchronously and represents executions through histories and abstract executions that capture operation behavior and conflict propagation.Abstract executions augment histories with orderings accounting for write conflicts and their propagation.
  • Framework and organization: A partial order ranks consistency notions by semantic strength, while ten loosely defined families group models by common traits.The ordering is derived from declarative logic-predicate definitions over graph entities.

2 System model

The system model represents asynchronous distributed executions using operations, histories, and abstract executions. Visibility and arbitration relations explain propagation and conflict resolution, while replicated data types define valid return values.

  • Preliminaries: The model assumes finite processes and shared objects communicating over a fully connected asynchronous network, generally treating processes and objects as non-failing.
  • Operations and histories: An operation records its process, type, object, input and output values, invocation time, and return time.Reads use a special input value, and non-returning operations use a distinguished return-time value.
  • Operations and histories: A history is the set of operations in an execution, with relations capturing real-time precedence, same-session order, same-object membership, and concurrency.The model defines returns-before, same-session, session-order, same-object, and concurrent-operation relations.
  • Abstract executions: An abstract execution augments a history with visibility and arbitration relations that explain operation outcomes, write propagation, and conflict resolution.Visibility is acyclic, whereas arbitration totally orders operations and can be implemented using timestamps, consensus, serialization, or deterministic conflict resolution.
  • Replicated data types and consistency: The framework uses replicated data types and a return-value function to specify which outputs are valid for an operation given its context.Return-value consistency requires every operation's output to belong to its intended set of return values.

3 Non-transactional consistency semantics

The paper surveys non-transactional consistency semantics and organizes them by semantic strength. It spans strong, weak, eventual, causal, session, staleness, and synchronization-based models, while clarifying definitions and implementation scope.

  • The survey covers more than 50 non-transactional consistency semantics and arranges them in a partial order by semantic strength.It also groups related models into families.
  • Strong consistency: Linearizability is the central strong consistency model: each operation appears instantaneous between invocation and response, and linearizable objects compose modularly.
  • Strong consistency: Linearizability is difficult to implement because strong semantics constrain availability under network partitions, as captured by CAP.
  • Strong consistency: Safe and regular register semantics weaken atomic behavior only for reads concurrent with writes, allowing progressively broader return-value sets.Atomic reads may return 0 or 1, regular reads 0, 1, or 2, and safe reads any value in the illustrated execution.
  • Weak and eventual consistency: Weak consistency may support relaxed caching, whereas eventual consistency additionally requires replicas to converge when updates stop.Eventual consistency can leave applications responsible for transient anomalies and is suited to settings where coordination is impractical or costly.
  • Weak and eventual consistency: Strong eventual consistency combines eventual delivery, convergence, termination, and strong convergence so replicas with the same writes reach equivalent state and return consistent values.

3.3 PRAM and sequential consistency

PRAM consistency preserves each process’s write order but permits different processes to observe different orders. Sequential consistency adds one common serialization while preserving each process’s program order, whereas linearizability also respects real time.

  • PRAM consistency: PRAM consistency requires every process to observe each writer’s operations in that writer’s invocation order, without requiring a global total order.
  • Sequential consistency: Sequential consistency requires all processes to observe the same serialized operation order while preserving each process’s operation order.
  • Comparison: PRAM permits different process-specific serializations, sequential consistency permits one shared serialization, and linearizability selects the serialization consistent with real-time linearization points.

3.4 Session guarantees

Session guarantees constrain what a process can observe across its operations, including monotonic reads, read-your-writes, monotonic writes, and writes-follow-reads. The section situates these guarantees within causal consistency and contrasts causal order with weaker session-based behavior.

  • Session guarantees: Session guarantees constrain observations across a process’s session, including monotonic reads, read-your-writes, monotonic writes, and writes-follow-reads.Monotonic reads preserve an expanding set of observed writes, while read-your-writes requires prior writes to be visible before later reads.
  • Session guarantees: Monotonic reads require successive reads to reflect a non-decreasing set of writes already observed by the process.A later read cannot return a value written before the value returned by an earlier read.
  • Session guarantees: Read-your-writes requires replicas serving a read to have applied all writes previously invoked by the same process.The formal predicate links session order from a write to a later read with visibility of that write.
  • Session guarantees: Monotonic writes preserve the issuing session’s write order, while writes-follow-reads place later session writes after writes whose effects earlier reads observed.These guarantees constrain replica application order and cross-process dependencies.
  • Causal models: Causal consistency includes the session guarantees and orders operations according to causal relationships, unlike executions that satisfy PRAM without causal consistency.The paper defines causal consistency through causal visibility, causal arbitration, and valid return values.
  • Causal models: The paper notes that real-time causal consistency and causal+ consistency are incomparable under the cited definitions because real-time causality does not imply strong convergence.A variant could be devised to respect strong convergence as well.

3.6 Staleness-based models

Staleness-based models permit reads to return older values while providing stronger guarantees than eventual consistency and weaker requirements than linearizability. They bound staleness by time or versions and combine these bounds with ordering or causality constraints.

  • Staleness-based models: Staleness-based models allow old values but trade weaker guarantees than linearizability for more efficient implementations than strong consistency.Common staleness metrics measure elapsed real time or object-version distance.
  • Time-based staleness: Time-based models bound when writes become visible or when reads may return stale values, using parameters such as delta or ∆.Delta consistency, timed consistency, and bounded staleness impose related time-based constraints with differing definitions and mechanisms.
  • Timed causal and serial consistency: Timed causal consistency combines causal ordering with an on-time read requirement, making it stronger than causal consistency.Timed serial consistency adds global real-time ordering, and with ∆=0 it becomes linearizable.
  • Figures and examples: Figure 6 depicts read outcomes whose admissibility depends on a fixed timing tolerance ∆.The figure highlights the ∆ parameter associated with staleness-based reads.
  • Prefix consistency: Prefix consistency preserves an agreed ordering of writes even when reads do not return the most recent value.The paper distinguishes prefix sequential consistency from prefix linearizable consistency according to whether real-time constraints are respected.
  • Version-based and probabilistic staleness: K-safe, K-regular, and K-atomic semantics permit reads to return one of the latest K values, while PBS models bound staleness or visibility probabilistically.K-linearizability generalizes register consistency by allowing bounded version-based staleness.

3.7 Fork-based models

Fork-based models address consistency under Byzantine or untrusted storage by constraining how divergent process views may evolve. Relaxations such as fork* and weak fork-linearizability trade stronger history agreement for improved performance, liveness, or availability.

  • Fault model: Fork-based consistency models reshape correctness conditions for storage systems facing Byzantine faults and untrusted repositories.Byzantine processes or objects may tamper with data or perform arbitrary operations, although some systems can still implement strong consistency.
  • Fork consistency: Fork-linearizability prevents processes whose visible histories diverge from later observing each other’s writes without exposing the server as faulty.The model captures this constraint through a no-join condition on forked views.
  • Fork* consistency: Fork* consistency relaxes fork consistency by allowing forked process groups to observe at most one common operation from a correct process.This relaxation is intended to support better performance and liveness guarantees.
  • Fork-sequential consistency: Fork-sequential consistency requires processes sharing an operation to share the same preceding visible history.A reader of another process’s write therefore shares the visible operations preceding that write.
  • Fork-join causal consistency: Fork-join causal consistency preserves causal ordering among correct processes while targeting safety and availability despite Byzantine faults.A dependent write becomes visible after the write on which it depends at every correct process.
  • Weak fork-linearizability: Weak fork-linearizability relaxes fork-linearizability through at-most-one-join and weak real-time order, enabling improved liveness guarantees.The paper notes that weak fork-linearizability and fork* consistency are incomparable.

3.8 Composite and tunable semantics

Composite and tunable semantics combine strong and weak consistency or adapt consistency levels to application needs, performance, and correctness requirements. The surveyed approaches include hybrid, eventual, QoS-driven, metric-based, invariant-aware, and metadata-based designs.

  • Composite semantics: Composite semantics combine different consistency levels, often executing operations locally under eventual consistency or synchronously serializing them when required.The motivation is to bridge strong consistency with efficient implementations through adaptive trade-offs.
  • Hybrid semantics: Hybrid consistency gives strong operations sequential visibility while allowing weak operations to execute quickly and become visible eventually.The model distinguishes operations by type and assigns them different consistency requirements.
  • Eventual ordering: Eventual serializability requires operations to converge from a partial order to a total order, with strict operations stable immediately and non-strict operations reorderable afterward.Eventual linearizability similarly permits weak operations to violate linearizability temporarily while requiring eventual ordering by real-time order.
  • Tunable semantics: Tunable consistency lets applications express requirements and directs operations to replica groups using synchronous or lazy replication.Runtime adaptation can also account for economic concerns, application needs, quality-of-service policies, or service-level agreements.
  • Quantified consistency: Consistency spectra quantify replica divergence using dimensions such as staleness, order error, numerical error, time, update count, and object value.Conit and vector-field consistency represent these bounds with multidimensional consistency vectors.
  • Invariant-aware and combined semantics: Explicit consistency supplements eventual consistency with application-specific invariants, while consistency anchors and hardening use separately stored metadata to obtain linearizability from eventual data storage.These approaches combine different storage or semantic mechanisms to strengthen selected guarantees.

3.9 Per-object semantics

Per-object semantics constrain ordering separately for each object, enabling weaker or more efficient alternatives to global ordering while spanning shared-memory consistency models and synchronization-based relaxations.

  • Per-object ordering semantics can enable more efficient implementations than global ordering by exploiting sharding and state partitioning.
  • Slow memory weakens PRAM consistency per object by requiring processes to observe each process’s writes to a given object in the same order.
  • Coherence requires writes to a specific memory location to become visible to all processors in some sequential order.
  • Processor consistency combines PRAM ordering for writes issued by each process with a common order for writes to the same object.
  • Release consistency weakens weak ordering by distinguishing strong and weak operations, while lazy release postpones enforcement from release until the next acquire.
  • Entry, scope, and location consistency further localize synchronization or ordering constraints, with location consistency abandoning memory coherence in favor of a partial order on writes.

4 Related work

Prior surveys address shared-memory, distributed-storage, and consistency-measurement perspectives, but remain limited in coverage, formality, or scope for modern non-transactional storage systems.

  • Earlier shared-memory surveys classified access policies, summarized models and trade-offs, and developed formal frameworks for composing and ordering consistency semantics.
  • Those shared-memory works cover only a limited portion of consistency semantics relevant to modern non-transactional storage systems.
  • Distributed-storage surveys use practical client-centric versus data-centric categorizations, but their informal dichotomy falls short of capturing the full consistency spectrum.
  • This paper extends Burckhardt’s formal model with first-order logic predicates and graph theory to cover more than 50 consistency semantics beyond session and eventual models.
  • Consistency-measurement research proposes metrics and client-side anomaly measures, while this survey organizes a more comprehensive set of metrics for evaluating consistency.
  • The survey complements transactional-consistency treatments by focusing on non-transactional storage semantics.

5 Conclusion

The paper surveys non-transactional consistency models using a formal framework, then organizes their definitions and relationships to clarify distinctions and trade-offs.

  • The survey presents an overview of the most relevant consistency models for non-transactional storage systems.
  • The resulting organization highlights subtle differences and helps scholars and practitioners understand the trade-offs among consistency models.
  • A graph-theoretic and first-order-logic framework extends prior work to capture factors involved in distributed-storage executions.
  • Formal definitions, clustering, and a partial ordering organize over 50 semantics by common traits and semantic strength.

A Summary of consistency predicates

The appendix summarizes consistency predicates used in the paper, including predicates for single ordering, quiescence, and timed visibility or causality.

  • SINGLEORDER expresses visibility as an arbitration order after optionally excluding a subset of operations.
  • QUIESCENTCONSISTENCY requires that, after finitely many writes, only finitely many operations per session violate a convergence condition.
  • TIMEDVISIBILITY constrains visibility using a time interval, and TIMEDCAUSALITY combines timed visibility with causality.
  • The summary table lists the consistency predicates defined throughout the paper.

B Primary references

This section catalogs consistency semantics alongside selected literature implementations. Table 4 organizes the material around definitions and implementations across many named semantics.

  • The references also cover specialized variants such as fork-join causal, fork-sequential, k-atomic, k-regular, k-safe, and k-staleness semantics.
  • The catalog spans strong, causal, eventual, fork-based, staleness, and tunable consistency families.
  • Named entries include linearizability, atomicity, bounded staleness, causal consistency, eventual consistency, and tunable consistency.
  • Table 4 pairs consistency-semantics definitions with selected implementations from the literature.
Loading 1512.00168v4…