Subtracks & Tasks
Physical Time and Its Failures
Read System Clock and Detect Backward Jumps
System clocks can go backward due to NTP adjustments. Your task is to read the clock repeatedly and detect backward jumps. Implement a `clock_sample`...
Implement Monotonic Clock Wrapper
A MonotonicClock wraps the system clock and guarantees the returned value never decreases. Implement this wrapper and track what information is lost. ...
Simulate Split-Brain Caused by Clock Drift
Time-based leases break when clocks drift. Two nodes can both believe they hold a valid lease simultaneously, causing **split-brain**. Implement leas...
Implement Mock TrueTime API
Google Spanner's TrueTime API returns a time interval instead of a point: `now() -> [earliest, latest]`. The true time is guaranteed to be within this...
Wait-Out-Uncertainty for External Consistency
Spanner achieves external consistency by waiting out the uncertainty window: before committing a transaction at timestamp T, wait until `TrueTime.now(...
Lamport Clocks
Implement a Lamport Clock from Scratch
A Lamport clock is the simplest logical clock. Each node maintains a single integer counter that increases with every event. The rules are: 1. **Inte...
Prove Lamport Clock Causality and Its Limitation
Lamport clocks guarantee: if event A **happened-before** event B, then L(A) < L(B). But the converse is NOT true - L(A) < L(B) does NOT mean A caused ...
Implement Distributed Mutual Exclusion with Lamport Clocks
Lamport's mutual exclusion algorithm uses Lamport clocks to totally order lock requests. Each node maintains a request queue sorted by (timestamp, nod...
Simulate Concurrent Mutex Requests from Multiple Nodes
Simulate 5 nodes all requesting the mutex simultaneously. With Lamport's algorithm, only one can hold it at a time. The request with the lowest (times...
Compare Mutex Algorithms: Lamport vs Token Ring vs Centralized
Different distributed mutex algorithms have different tradeoffs. Compare three approaches: 1. **Lamport's algorithm**: 3(N-1) messages per CS entry, ...
Vector Clocks
Implement Vector Clocks
Vector clocks extend Lamport clocks by maintaining a vector of N integers (one per node) instead of a single counter. This lets you determine causal r...
Implement Happens-Before and Concurrency Detection
Vector clocks let you determine the causal relationship between any two events. Given two vector clock stamps `a` and `b`: - **a happens-before b** (...
Build a Causal-Order Chat System
Build a distributed chat system where messages are displayed in causal order even when they arrive out of network order. Each message carries the send...
Implement Dotted Version Vectors
Standard vector clocks have an O(N) storage cost that grows with every node that ever participated. Dotted version vectors (DVVs), used in Riak, solve...
Build a Conflict-Detecting Key-Value Store
Use vector clocks to detect write-write conflicts in a key-value store. When two nodes write to the same key concurrently (neither write causally depe...
Hybrid Logical Clocks
Implement Hybrid Logical Clocks
A Hybrid Logical Clock (HLC) combines the best of physical clocks (real-time proximity) and logical clocks (causal ordering). Used in CockroachDB and ...
Prove HLC Preserves Causality Within Epsilon
HLC has a critical property: it preserves causality AND stays within a bounded distance (epsilon) of physical time. This is what makes it practical fo...
Implement a Distributed Lock Using HLC Timestamps
Build a distributed lock where the lock is granted based on HLC timestamps. The process with the lowest HLC timestamp in the request queue gets the lo...
Build a Time Oracle Service with Failover
Build a centralized time oracle service that nodes query for globally consistent HLC timestamps. This avoids the problem of unbounded clock skew betwe...
Architecture Decision Record: Choosing a Clock System
Write an Architecture Decision Record (ADR) for choosing a clock system for a multi-region distributed database. Compare five clock systems across mul...
Concepts Covered
Prerequisites
It is recommended to complete the previous tracks before starting this one. Concepts build progressively throughout the curriculum.