Extras Flashcards
How does Raft improve over Paxos?
Simplicity: Raft is easier to understand and implement compared to Paxos.
Stronger leadership model: Raft elects a leader for log replication, while Paxos has more complex leader selection.
Log structure: Raft enforces a stronger log consistency mechanism than Paxos.
What is the difference between Raft and Byzantine Fault Tolerance (BFT) algorithms?
Raft assumes crash-recovery failures only (nodes either fail or recover).
BFT handles malicious nodes (nodes may lie, send conflicting messages).
BFT requires more nodes: At least 3f+1 nodes to tolerate f faulty nodes, while Raft needs 2f+1 nodes.
Where is Byzantine Fault Tolerance used?
Blockchain (e.g., Tendermint, PBFT) – Prevents malicious nodes from altering transactions.
Hyperledger Fabric – Uses a PBFT-like consensus for enterprise blockchains.
Secure distributed systems – Used where trust cannot be assumed (e.g., financial networks).
How is Raft used in Kubernetes (etcd)?
Kubernetes uses etcd, a Raft-based key-value store, to maintain cluster state, leader elections, and service discovery.
Why is linearizability expensive in real-world systems?
Requires waiting for a quorum of replicas to respond.
If a network partition occurs, all writes must halt.
Leads to higher latency and reduced availability.
What happens if a system has monotonic reads but not read-your-writes consistency?
Users may see old versions of their own writes.
Example: Editing a document, refreshing, and seeing an older version.
What is a vector clock, and how does it help resolve conflicts?
A logical timestamping system that tracks causal relationships between updates.
Used in DynamoDB, Riak, and version control systems to resolve conflicts.
Example: If two users modify the same key, vector clocks determine which happened first.
How do CRDTs ensure conflict-free merging?
Use mathematically proven merge functions.
Example:
LWW Register (Last-Writer-Wins): Picks the update with the latest timestamp. PN Counters: Merges counters without conflicts (used in Redis).
Why is consistency critical in distributed systems?
When data is replicated, inconsistencies can occur due to network delays, failures, and concurrency.
Most systems provide eventual consistency, meaning replicas will eventually converge to the same value.
When do eventual consistency edge cases appear?
System failures (e.g., a partitioned replica gets outdated).
High concurrency (e.g., two clients updating the same record simultaneously).
What is the difference between transaction isolation and distributed consistency?
Transaction Isolation (ACID focus)
Prevents race conditions within a single database instance.
Isolation levels:
Serializable (Strongest)
Repeatable Read
Read Committed
Read Uncommitted (Weakest)
Distributed Consistency (Replication focus)
Ensures all replicas see updates correctly.
Common models:
Strict Consistency
Linearizability
Causal Consistency
Monotonic Reads/Writes
Read-Your-Writes Consistency
What does ACID consistency mean?
The database transforms from one valid state to another, preserving application-specific rules.
Example: A bank transfer must either complete fully or not at all.
How does read-after-write consistency differ?
Ensures a client sees its own recent updates immediately.
Example: Uploading a profile picture → It should appear 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.
What are the steps in 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?
The system blocks until the coordinator recovers.
Solution: Use Paxos Commit for failure recovery.
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.
How does linearizability differ from serializability?
Serializability: Ensures transactions execute in a serial order.
Linearizability: Ensures individual operations execute in a real-time 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 linearizability difficult in real-world systems?
Requires waiting for a quorum of replicas to respond.
Network partitions force operations to halt to prevent stale reads.
Leads to higher latency and reduced availability.
What does the CAP theorem state?
A system cannot be both:
Consistent (Linearizable) Available Partition-Tolerant
If a network partition occurs, the system must choose between C (Consistency) or A (Availability).
How does the PACELC theorem refine CAP?
If Partitioned (P), the system must pick Availability (A) or Consistency (C).
Else (E), even when there is no failure, the system must pick Latency (L) or Consistency (C).
Example:
Google Spanner → CP (Strong consistency, lower availability). AWS DynamoDB → AP (High availability, eventual consistency).
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 are Conflict-Free Replicated Data Types (CRDTs)?
A family of algorithms ensuring conflict resolution without coordination.
Examples: Counters, sets, lists, maps, trees.
How does Google Docs handle collaboration?
Uses Operational Transformations (OT) to merge edits.
Centralized server resolves conflicts.
Where are CRDTs used in real-world systems?
Google Docs (OT-based resolution).
Apple Notes (State-based CRDTs).
Redis, Riak, RiotGames, Microsoft Fluid.
