Distributed System Concepts

When data lives on a single machine, consistency is straightforward: there's one copy, and all access goes through one system. But distributed systems replicate data across multiple nodes—for fault tolerance, for performance, for geographic coverage. This replication creates one of the most challenging problems in distributed computing: maintaining consistency.

What does it mean for distributed data to be 'consistent'? If I write a value in New York, when should it be visible in Tokyo? If two users update the same record simultaneously, which update wins? If a network partition prevents nodes from communicating, can they both continue accepting writes safely?

These questions have no easy answers. The solutions involve fundamental tradeoffs that shape every distributed system architecture. Understanding consistency—its models, impossibility results, and practical approaches—is essential for building and reasoning about distributed systems.

Why Consistency Is Hard:

In a distributed system with replicated data, the consistency problem arises from fundamental physical constraints:

1. Network Latency Is Non-Zero

Information cannot travel faster than light. Sydney to London is ~17,000 km; at c = 300,000 km/s, minimum round-trip is ~113ms. No protocol can make data instantly consistent globally.

2. Messages Can Be Delayed or Lost

Networks are unreliable. A message to synchronize replicas might take milliseconds or seconds, or might never arrive. Systems must handle all possibilities.

3. Nodes Can Fail Independently

While Node A processes an update, Node B might crash, leaving replicas in different states. Recovery must handle partial update scenarios.

4. Concurrent Operations Create Conflicts

Two nodes might accept conflicting updates to the same data simultaneously, with no way to know about each other until later.

The Central Question:

Given these constraints, how do we ensure that when users access data—from any replica—they see a reasonable, predictable view of the data? Different answers define different consistency models.

Consistency models define the contract between a distributed storage system and its clients regarding what values can be returned by reads. They form a spectrum from strongest (most restrictive, easiest to reason about) to weakest (most permissive, hardest to program against).

Linearizability (also called atomic consistency or strong consistency) is the strongest single-object consistency model. It provides the illusion that there is only one copy of the data, and all operations on it are atomic.

Formal Definition:

An execution is linearizable if:

1. Each operation appears to take effect instantaneously at some point (the linearization point) between its invocation and response.
2. All operations can be ordered in a sequence consistent with their linearization points.
3. This sequence respects read/write semantics: each read returns the value of the most recent preceding write.

What Linearizability Provides:

• Real-time guarantees: If operation A completes before operation B starts, A's effects are visible to B.
• Single-copy semantics: The system behaves as if there's one copy of each object.
• Composability: Linearizable operations on individual objects are linearizable as a group.

What Linearizability Does NOT Provide:

• Transactions spanning multiple objects (requires additional mechanisms)
• Protection against application-level races
• Guarantees about durability (that's a separate concern)

Achieving Linearizability:

Linearizability requires coordination—all replicas must agree on the order of all operations. Common approaches:

1. Single Leader

• One node (primary) orders all writes
• Reads from primary are linearizable
• Reads from replicas may be stale (not linearizable)
• Simple but single point of failure

2. Consensus Protocols

• Paxos, Raft agree on operation order
• All committed operations have agreed order
• Tolerates minority failures
• Latency for multi-node agreement

3. Synchronized Clocks (Google Spanner)

• TrueTime provides bounded clock uncertainty
• Operations assigned timestamps with uncertainty interval
• Wait until interval passes before returning
• Linearizable without per-operation consensus

The CAP theorem (Consistency, Availability, Partition tolerance), formulated by Eric Brewer and proven by Gilbert and Lynch (2002), is the most famous impossibility result in distributed systems. It states that a distributed data store can provide at most two of these three properties:

C — Consistency (Linearizability) Every read receives the most recent write or an error.

A — Availability Every request to a non-failing node receives a response (no timeout or error).

P — Partition Tolerance The system continues to operate despite arbitrary partition of the network (messages between nodes may be lost or delayed indefinitely).

The Impossibility:

During a network partition, you must choose:

• Stop processing (sacrifice availability for consistency) — Refuse to respond to requests if you can't confirm you have the latest data
• Continue processing (sacrifice consistency for availability) — Respond with potentially stale data because you can't communicate with other replicas

CAP Nuances and Clarifications:

1. It's About Partitions

CAP only forces a choice during partitions. When the network is healthy, you can have both consistency and availability. The question is what happens when things go wrong.

2. Partition Tolerance Is Not Optional

Network partitions are a fact of life in distributed systems. 'CA' (without P) would mean the system simply doesn't work during partitions—not a useful system. Real choices are CP or AP.

3. Consistency Has a Specific Meaning

CAP's 'consistency' means linearizability, specifically. Weaker consistency models (eventual, causal) can provide high availability during partitions.

4. The Choice Is Per-Operation

A system can make different choices for different operations. Write operations might be CP (strong consistency) while reads might be AP (always respond, possibly stale).

Eventual consistency is the consistency model of many highly scalable distributed systems. It's often misunderstood—let's examine it precisely.

Definition:

If no new updates are made to a data item, eventually all replicas will converge to the same value.

What 'Eventually' Means:

• The system makes a best effort to propagate updates
• No bound on how long convergence takes
• During propagation, different replicas may have different values
• Reads may return stale data

What Eventual Consistency Allows:

• Replicas operate independently (no coordination for writes)
• System remains available during partitions
• Low latency for writes (no waiting for propagation)
• High throughput (no coordination bottleneck)

What Eventual Consistency Does NOT Guarantee:

• When updates will be visible at other replicas
• What intermediate states clients might observe
• That concurrent updates will resolve consistently

The Challenge of Concurrent Updates:

When two replicas accept conflicting updates to the same data:

Time:
  t1: Replica A sets x = 1
  t2: Replica B sets x = 2
  t3: Replicas synchronize... what is x?

Eventual consistency doesn't specify how conflicts resolve—only that replicas eventually agree. Additional mechanisms are needed:

Conflict Resolution Strategies:

1. Last-Writer-Wins (LWW)

   • Each write has a timestamp
   • Highest timestamp wins
   • Simple but loses updates
   • Depends on clock synchronization

2. Merge Functions (CRDTs)

   • Data structures with mathematically proven merge
   • Concurrent updates merge deterministically
   • Examples: counters, sets, registers

3. Application-Level Resolution

   • Store all conflicting values (siblings)
   • Application picks or merges at read time
   • Most flexible but complex

Quorum systems are a powerful technique for providing tunable consistency in replicated systems. By adjusting the number of replicas that must participate in reads and writes, systems can trade off between consistency and availability.

The Quorum Principle:

With N total replicas:

• W = number of replicas that must acknowledge a write
• R = number of replicas that must respond to a read

If W + R > N, reads and writes overlap—at least one replica in every read quorum has the latest write. This provides strong consistency.

Examples:

N = 3 replicas

W = 2, R = 2: W + R = 4 > 3 ✓ (strong consistency)
  - Write to majority, read from majority
  - Tolerates 1 failure for both reads and writes

W = 3, R = 1: W + R = 4 > 3 ✓ (write-heavy)
  - All replicas must acknowledge writes
  - Any replica can answer reads
  - Fast reads, slower writes

W = 1, R = 3: W + R = 4 > 3 ✓ (read-heavy)
  - Write to any replica
  - Must read all replicas
  - Fast writes, slower reads

W = 1, R = 1: W + R = 2 ≤ 3 ✗ (eventual consistency)
  - May miss latest write
  - Fast but potentially stale

Quorums in Practice:

Cassandra uses tunable quorum:

• QUORUM: majority (N/2 + 1)
• ONE: single replica (eventual)
• ALL: all replicas (strongest)
• Per-query configuration possible

Riak and DynamoDB similarly allow tuning W and R.

Limitations:

• Quorum overlap only ensures 'some' overlap, not 'which' values
• Without additional mechanisms, conflicting concurrent writes need resolution
• Sloppy quorums (during partitions, non-home replicas count) weaken guarantees

Causal consistency is a compelling middle ground between strong and eventual consistency. It preserves intuitive cause-and-effect relationships while allowing high availability.

Definition:

If operation A causally precedes operation B (denoted A → B), then all clients observe A before B. Concurrent operations (neither causally precedes the other) may be observed in any order.

Causality Relationships:

• Same client: If the same client does A then B, A → B
• Read-from: If B reads a value written by A, A → B
• Transitive: If A → B and B → C, then A → C

Concurrent: If neither A → B nor B → A, they are concurrent.

Example: Social Media Post

Alice posts: "I got a job!"
Bob reads Alice's post
Bob comments: "Congratulations!"

With causal consistency:

• All users see Alice's post before Bob's comment
• Cause (original post) always precedes effect (reply)

With only eventual consistency:

• Some users might see Bob's comment before Alice's post
• Confusing and violates user expectations

Tracking Causality:

Implementing causal consistency requires tracking causal dependencies:

Vector Clocks:

• Each node maintains a vector of logical clocks
• Vector captures which operations at other nodes have been observed
• Comparison determines causality or concurrency

Dependency Metadata:

• Operations carry metadata about operations they depend on
• Reads delayed until dependencies are satisfied

CRDTs (Conflict-free Replicated Data Types) are data structures designed to be replicated across distributed nodes without coordination, while guaranteeing eventual convergence. They mathematically ensure that concurrent modifications merge automatically and deterministically.

The CRDT Insight:

Traditional data types conflict on concurrent modification:

• Two nodes increment a counter: could double-count or lose increments
• Two nodes add to a set: concurrent adds might conflict

CRDTs define operations and merge functions that commute, associate, and are idempotent—ensuring that all orderings of operations produce the same result.

Types of CRDTs:

Operation-based (CmRDT):

• Operations broadcast to all replicas
• Operations applied in any order (must commute)
• Requires reliable broadcast

State-based (CvRDT):

• Full state periodically synchronized
• States merged using join operation (must form a semilattice)
• Simpler network requirements

CRDTs in Practice:

• Riak: OR-Sets, PN-Counters, Maps built in
• Redis: CRDT-based Redis Enterprise for geo-replication
• Apple Notes: Uses CRDTs for real-time collaboration
• Figma: CRDT-based collaborative design
• Yjs / Automerge: CRDT libraries for collaborative editing

Limitations:

• Not all operations have CRDT equivalents (arbitrary data logic)
• Space overhead for metadata (especially version tracking)
• Semantics may differ from expected (counters absorb concurrent decrements)
• Deletion and removal require care (tombstones, garbage collection)

Choosing the right consistency model is a critical architectural decision. The right choice depends on application requirements, user expectations, and operational constraints.

Decision Framework:

Mixing Consistency Levels:

Most real systems use different consistency levels for different operations:

Example: E-Commerce Platform

Operational Considerations:

• Stronger consistency = more monitoring, more failure modes
• Weaker consistency = more application complexity for handling anomalies
• Team expertise matters: eventual consistency requires careful programming
• Start stronger, relax as needed: easier than tightening later

Consistency is perhaps the most nuanced challenge in distributed systems. Let's consolidate the key insights:

Module Complete:

You've now completed the foundational module on Distributed System Concepts. You understand what distributed systems are, how they achieve transparency, the principles of scalability, mechanisms for fault tolerance, and the challenges of consistency. This foundation prepares you for deeper exploration of distributed communication, coordination, file systems, and cloud computing in subsequent modules.