Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 36 ยท Practice and Review

Practice Exercises with Solutions

Twelve hands-on distributed systems exercises with runnable Python solutions: Lamport and vector clocks, quorums, retries, CRDTs, sharding and Raft commits.

Reading about distributed systems is not the same as being able to reason about them. These twelve exercises train that reasoning: compute a clock value, pick a quorum, count how many keys move when a node joins, decide what a leader may commit. Each exercise states a problem, and each solution is a runnable program, so you can change numbers and watch the answer change.

Try the exercise on paper first, then open the solution. Every solution prints its result and contains assert checks, so if you edit the code and break an idea, the run tells you.

Twelve exercises, six themes

Clocks Lamport, vector clocks, skew (1 to 3).
Quorums Overlap and failures (4, 11).
Retries Backoff, idempotency, odds (5 to 7).
CRDTs Merge laws and add-wins sets (8, 9).

Then sharding (10) and consensus (12).

1 / 2

Clocks and ordering

Exercise 1: Lamport timestamps

Two processes, P and Q, start with clock 0. In order: P does a local event a; P sends message m1 (event b); Q receives m1 (c); Q has a local event d; Q sends m2 (e); P receives m2 (f); P has a local event g. What is each event's Lamport timestamp?

Rules: every event increments the clock by one; a receive sets the clock to max(own, message timestamp) + 1.

Python Solution 1: Lamport timestamps

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The timestamps are 1, 2, 3, 4, 5, 6, 7. Remember the one-way guarantee: if x happened before y, then ts(x) < ts(y). The reverse is false: ts(a) < ts(d) here, yet that tells you nothing unless a message chain connects them.

Exercise 2: Vector clock comparison

Write compare(a, b) for vector clocks that returns "before", "after", "equal" or "concurrent". Then classify every pair among x=(2,0,0), y=(2,1,0), z=(0,0,1) and w=(2,1,3).

Python Solution 2: vector clock comparison

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Only x and z, and y and z, are concurrent. Everything else is ordered, and w is after all three because it has seen all their events.

Exercise 3: When last-write-wins picks the wrong write

Server A's clock runs 80 ms fast; server B's clock is exact. At true time 1000 ms a client writes "old" through A. At true time 1050 ms another client, who has already read "old", writes "new" through B. Each write is stamped with its server's clock. Which value does last-write-wins keep? Is that right? (See clocks and time.)

Python Solution 3: LWW with skewed clocks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

LWW keeps "old": its stamp is 1080 and the newer write's stamp is only 1050. The user who wrote "new" after reading "old" is silently overruled. The fix is not a better clock but a better rule: use version vectors to see that "new" causally follows "old".

Quorums, retries and idempotency

Exercise 4: Choosing W and R

A store has N = 5 replicas. List every pair (W, R) with R + W > N. For the pairs with R + W = N + 1, how many failures can writes and reads each survive? Which pair would you pick for a read-heavy workload? (Background: quorums.)

Python Solution 4: quorum choices

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

There are 15 valid pairs. With R + W = N + 1 there is a trade-off: (3, 3) survives two failures for both reads and writes. For a read-heavy workload choose (5, 1): reads touch one replica and are fast, but every write needs all five replicas, so a single failure blocks writes. Many systems prefer (3, 3) as the balanced default.

Exercise 5: Exponential backoff with jitter

A client retries with exponential backoff: the ceiling for attempt k (starting at 0) is min(2000, 100 * 2**k) ms, and the actual delay is a random number between 0 and the ceiling ("full jitter"). Print the ceilings for attempts 0 to 6, then estimate the mean delay of attempt 3 over 10,000 clients. Why does jitter matter? (See idempotency and retries.)

Python Solution 5: backoff with full jitter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The ceilings are 100, 200, 400, 800, 1600, 2000, 2000, and the mean delay at attempt 3 is 398 ms, about half the ceiling of 800. Without jitter, thousands of clients that failed together would retry at the same instants, hammering the recovering server in synchronized waves. Random delays spread them out.

Exercise 6: An idempotent payment

Write charge(key, account, amount) that applies a charge once per idempotency key. A repeated call with the same key and the same amount returns the first result without charging again. The same key with a different amount must raise an error.

Python Solution 6: idempotency keys

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The balance drops by 30 only once. In a real database, the key check and the balance update must happen in one transaction, or two parallel retries can both pass the check.

Exercise 7: How many retries do you need?

Each attempt succeeds independently with probability 0.7. What is the probability that at least one of 3 attempts succeeds? Compute it with a formula, then check it with a simulation of 20,000 requests.

Python Solution 7: odds of retrying

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The probability is 1 - 0.3ยณ = 0.973. Three tries turn a 70% success rate into about 97%. This only holds when failures are independent: if the server is overloaded, retries are correlated and make things worse, which is why retries need backoff and budgets.

CRDTs

Exercise 8: G-Counter merge laws

A grow-only counter keeps one count per replica; the value is the sum and merge takes the element-wise maximum. Check on 200 random triples of states that merge is commutative, associative and idempotent. (See CRDTs.)

Python Solution 8: G-Counter laws

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

These three laws are exactly why replicas can exchange states in any order, with duplicates, and still converge. Note that adding the counts instead of taking the maximum would break idempotence.

Exercise 9: An add-wins set

Implement an observed-remove set. Each add creates a unique tag; remove deletes only the tags the remover has seen. Show that when replica A removes "tea" while replica B concurrently adds "tea" again, the element survives after the merge.

Python Solution 9: OR-Set, add wins

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The remove only kills the old tag, and B's new tag was never observed by A, so it survives. Both replicas agree on ["tea"].

Sharding and consensus

Exercise 10: How many keys move?

You have 10,000 keys on 4 nodes and add a fifth. Compare hash mod N with consistent hashing (100 virtual nodes per node): what fraction of keys changes node? (See sharding.)

Python Solution 10: rebalancing cost

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Modulo hashing moves about 80% of the keys, because almost every key's hash % n changes. Consistent hashing moves only the share the new node takes over: 22% here, close to the ideal 1/5 = 20%. That difference is why it is the standard for caches and Dynamo-style stores.

Exercise 11: Majorities and failures

For cluster sizes 3 to 9, print the majority and how many node failures a majority-based system tolerates. Explain why 4 nodes are no better than 3 and why even sizes are avoided.

Python Solution 11: majority table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Four nodes need 3 for a majority, so they still tolerate only 1 failure, exactly like 3 nodes, but there are more machines that can fail and a split into 2 plus 2 leaves no majority at all. Odd sizes give the most fault tolerance per node.

Exercise 12: The Raft commit index

A Raft leader has 5 servers. The highest log index known to be replicated on each is [7, 5, 6, 3, 5] (the first is the leader itself). What is the highest index the leader may consider committed? Write the function.

Python Solution 12: finding the commit index

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sorted from high to low the list is [7, 6, 5, 5, 3]. Three servers (a majority of five) have at least index 5, so index 5 is committed. Index 6 is on only two servers. In real Raft one more rule applies: the leader commits by counting replicas only for entries from its own term; older entries become committed indirectly.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which statement about Lamport timestamps is true?

    Lamport clocks only guarantee one direction. To detect concurrency you need vector clocks.
  2. 2. Why does jitter matter in a retry policy?

    Without randomness, clients that failed at the same moment retry at the same moment and overload the server again.
  3. 3. With N = 5, which pair gives overlapping read and write quorums?

    Overlap needs R + W > N. Only 3 + 3 = 6 exceeds 5 (2 + 3 = 5 and 1 + 4 = 5 do not).
  4. 4. How many keys move with hash mod N when going from 4 to 5 nodes?

    Most keys get a different remainder. Consistent hashing moves only about 20%.

Summary

  • Practice clocks by hand: Lamport rules give an order but cannot detect concurrency; vector clocks can.
  • Skewed clocks make last-write-wins pick the wrong write.
  • Quorums need R + W > N; backoff needs jitter; retries need idempotency keys.
  • CRDT merges must be commutative, associative and idempotent.
  • Consistent hashing moves a small share of keys; majorities tolerate fewer failures than you might hope.
  • A Raft leader commits the highest index stored on a majority.

Next: Interview Questions.