Please enable JavaScript.
Coggle requires JavaScript to display documents.
Consistency and Consensus - Coggle Diagram
Consistency and Consensus
Consistency
Distributed Systems Faults
Fault tolerance requires data replication
Replication risks introducing data inconsistencies
Competing Consistency Philosophies
Eventual Consistency
Application handles contradictions and conflicts
Used in multi-leader or leaderless
Strong Consistency
System behaves like single node
Simpler approach for application developers
Performance cost and lower availability
Linearizability
Definition
Strongest consistency model in use
Guarantees immediate data recency
Operations appear completely atomic
Successful writes instantly visible globally
Prevents stale reads after updates
VS Serializability
Serializability
Multi-object transaction isolation level
Permits reading stale data values
Linearizability
Single-object read and write guarantee
Enforces strict operational timing dependencies
Relying on it
Locking and Leader Election
Prevents split-brain in single-leader
Foundations for ZooKeeper and etcd
Constraints and Uniqueness Guarantees
Mandatory for enforcing unique usernames
Prevents negative bank account balances
Cross-Channel Timing Dependencies
Eliminates external race conditions
Syncs multiple different communication channels
Implementation
Single-Copy Baseline
Ensures perfect atomicity
Vulnerable to catastrophic data loss
Single-Leader Replication
Reads and writes routed through leader
Delusional leaders can violate linearizability
Asynchronous failovers risk losing writes
Consensus Algorithms
Prevent split-brain with leader election
ZooKeeper and etcd use consensus
Non-leader reads can cause staleness
Multi-Leader Replication
Processes concurrent writes across nodes
Asynchronous replication creates write conflicts
Generally incapable of providing linearizability
Leaderless Replication
Quorums do not guarantee linearizability
LWW clocks cause nonlinearizable behavior
Network delays trigger quorum race conditions
Linearizable quorums require synchronous repair
Atomic CAS operations require consensus
Tradeoffs
Multi-Region Replication
Multi-leader replication
Async writes queued during partition
Good for geo-distributed deployments
Single-leader replication
Writes must reach leader region
Followers stale or unavailable
Network partition scenario
Regions isolated from each other
Forces linearizability vs availability choice
CAP Theorem
Core trade-off
CP: consistent, unavailable when partitioned
AP: available, non-linearizable when partitioned
Limitations
Little practical design value today
Narrow scope
Availability definition mismatches common usage
C is only linearizability
Some systems are neither CP/AP
Partitions cause under 8% incidents
Misleading framing
Not "pick two of three"
Partitions aren't optional choices
Better phrasing
Consistent or available when partitioned
Linearizability and Network Delays
Rarely achieved in practice
Even multi-core RAM isn't linearizable
CPU cache example
Store buffers cause stale reads
Needed for performance, not faults
Why systems drop linearizability
Performance reason, not fault tolerance
ID Generators and Logical Clocks
Single-Node ID Generation
Autoincrementing integers
Compact, 32/64-bit storage
Order reveals creation order
Fetch-and-add operation
Atomic CPU increment
Linearizable ordering guarantee
Core problems
Single point of failure
Slow for distant regions
Bottleneck at high throughput
Distributed ID Alternatives
Sharded ID assignment
Reserve bits for each shard
Loses cross-shard ordering
Preallocated ID blocks
Nodes claim ID ranges
Ordering still not guaranteed
Unique timestamp-based IDs
Timestamp plus unique suffix
Used by UUIDv7, Snowflake
Weak due to clock drift
Random UUIDs
128-bit random values
No meaningful order
Logical Clocks
General requirements
Compact, unique timestamps
Totally ordered comparisons
Consistent with causality
Lamport clocks
Pair of counter, node ID
Increment on every event
Can't grasp physical time -> need to store it separately
One node doesn't know of the other one's increments
Hybrid logical clocks
Combines physical and logical time
Monotonic despite clock jumps
Used by CockroachDB
Versus vector clocks
Per-node counter arrays
Detects true concurrency
Costs more storage space
Linearizable ID Generators
Cross-database timestamp mismatch
Single coordinating node
Persist and replicate counter
Batch ID allocation optimization
Spanner-style approach
Indicates the Clock uncertainty intervals
Wait out uncertainty window
Relies on physical clock with a range of timestamps
Constraints via Logical Clocks
Lowest timestamp wins
Fundamental limitation
Must hear all nodes
Fails under node outage
Requires true consensus
Consensus
FLP result
Due to nodes crashing reliable consensus not possible
Assumes async, deterministic model
Actually
Timeouts enable consensus
Randomness is also sufficient
Types
Single-value consensus
Implement locks, leases and uniqueness constraints
Similar to an atomic CAS operation
Properties
Agreement
No two nodes decide differently
Integrity
Node has decided -> stick to decision
Validity
Decision was proposed by a node
Termination
Every node that does not crash eventually decides a value
Requires majority alive
Compare-and-Set as Consensus
What CAS Does
Match: atomically updates value
No match: error, unchanged
CAS Solves Consensus
Start object as null
Nodes CAS-propose their value
Consensus Solves CAS
Consensus decides proposed value
Object set to decision
Conditional writes in object storage