L8/9 - Consistency Flashcards
Why are consistency guarantees needed in distributed systems?
When data is replicated, inconsistencies can occur due to network delays, failures, and concurrency.
Most systems provide eventual consistency, meaning replicas eventually converge to the same value.
When do the edge cases of eventual consistency become apparent?
Under system failures or high concurrency.
Example: A client may read stale data if updates haven’t yet propagated.
What is the difference between transaction isolation levels and distributed consistency?
Transaction Isolation (ACID focus): Ensures transactions execute without race conditions.
Serializable (Strongest) Repeatable Read Read Committed Read Uncommitted (Weakest)
Distributed Consistency (Replication focus): Ensures replicas are synchronized correctly.
Strict Consistency Linearizability Causal Consistency Monotonic Reads/Writes Read-Your-Writes Consistency
What does ACID consistency mean?
The database transforms from one consistent state to another, preserving application-specific constraints.
Example: A course must have at least one lecturer if students are enrolled.
How does read-after-write consistency differ?
Ensures a client reads its own updates immediately.
Example: If a user uploads a profile picture, it should appear immediately upon refresh.
What is the Atomic Commitment Problem in distributed transactions?
If a transaction updates multiple nodes, either all nodes must commit, or all must abort.
If any node crashes, the transaction must abort to maintain consistency.
How is atomic commit different from consensus?
Consensus: Nodes propose values, and one value is chosen.
Atomic Commit: Nodes vote to commit or abort, and all must agree on the decision.
What is Two-Phase Commit (2PC)?
Prepare Phase – Coordinator asks participants if they can commit.
Commit Phase – If all vote yes, commit; if any vote no, abort.
What happens if the coordinator crashes before sending the commit message?
The system blocks until the coordinator recovers and resends the decision.
Solution: Use Paxos Commit to ensure total order broadcast.
What is linearizability?
Ensures that all operations appear to take effect atomically between their start and end time.
All replicas behave as if there is only one copy of the data.
What are real-world use cases for linearizability?
Leader Election (ZooKeeper, etcd) – Ensures only one leader exists at a time.
Unique Constraints – E.g., preventing duplicate usernames.
Cross-Channel Dependencies – Coordinating distributed messaging systems.
How does serializability differ from linearizability?
Serializability: Ensures transactions execute in a serial order.
Linearizability: Ensures individual operations execute in an up-to-date order.
Can a system provide both linearizability and serializability?
Yes! This is called Strict Serializability (1SR).
Example: Systems using Two-Phase Locking (2PL).
Why is quorum-based consistency not always linearizable?
If some replicas receive updates before others, clients may read stale data.
Example:
Replica A gets 𝑣1, but Replicas B and C still see 𝑣0. A client reading from B or C may get 𝑣0, violating linearizability.
How can quorum reads/writes be made linearizable?
ABD Algorithm (Attiya et al., 1995):
Reads must fetch from all replicas. If newer values exist, clients must write them back to stale replicas (read-repair).
What is eventual consistency?
Guarantees that if no new updates occur, all replicas will eventually converge.
Example: DNS servers take time to update but will eventually show the same records.
What does the CAP Theorem state?
A system cannot be both:
Consistent (Linearizable) Available Partition-Tolerant
In case of a network partition, the system must choose between consistency or availability.
What is causal consistency?
Ensures that cause-and-effect relationships are preserved.
Example: If Alice sends a message before Bob replies, Bob’s message must appear after Alice’s.
How does causal consistency differ from linearizability?
Linearizability: Total order – every operation has a global order.
Causality: Partial order – only related events must be ordered.
Why is causal consistency more scalable?
Unlike linearizability, causal consistency does not require coordination across all nodes.
More efficient for distributed databases (e.g., Facebook’s TAO).
What are the challenges in collaborative applications (e.g., Google Docs)?
Users make concurrent changes.
The system must merge updates without conflicts.
What are CRDTs (Conflict-Free Replicated Data Types)?
A family of algorithms ensuring conflict resolution without coordination.
Examples: Counters, sets, lists, maps, trees.
How do state-based and operation-based CRDTs differ?
State-Based: Nodes merge their states periodically.
Operation-Based: Nodes broadcast every operation reliably.
Where are CRDTs used in practice?
Google Docs (Operational Transformations).
Apple Notes (State-based CRDTs).
Redis, Riak, Microsoft Fluid, RiotGames (League of Legends).
