حل آموزشی تمرین‌های فصل 10Chapter 10 exercise solutions, explained

• Three processes A, B, C with unique IDs; the tie-break needs uniqueness, nothing else.
• Teaching scenario from chapter diagram 5: A and C post once each, B merges both then replies.
• Messages can be delayed but the receive rule is applied per delivery; no wall clock is used anywhere.

Receive=max(local,received)+1 gives reception a timestamp greater than its send; adding one distinguishes the receive event. Unrelated events may have equal or ordered timestamps, so the converse of happened-before fails. Process IDs provide deterministic tie-breaking, not causality. Three processes make independent sends and a shared receiver easy to inspect.

1. Count first One counter per process, starting at 0. Every local event and every send ticks it +1 — the clock only moves forward, one step per event.
2. Adopt on receive On receive, adopt max(local, seen). Walk the book's scenario: B takes max(0,1)=1 from A, max(1,1)=1 from C, then its reply-send ticks 1+1=2. No receive ever moves a clock backwards.
3. Sort with tie-break Sort stamps as (counter, processID) with the process ID breaking ties: (1,A) < (1,C) < (2,B). A total order that respects every message chain — concurrent posts A and C simply take ID order.
4. Name what it cannot do Name the limit with the trap: x=(5,A) and y=(3,C) with no messages — ordered stamps, zero causality. Concurrency detection needs vector clocks: one entry per process, O(n) state and stamp bytes.

One counter (u64) plus one immutable processID per process. Message envelope carries (counter, processID); the harness logs every send/receive with its stamp. Read path: sort logged stamps by (counter, processID). Write path: apply the two rules at each event; no coordination, no extra RPC.

Teaching walk (chapter diagram 5): A sends (1,A); C sends (1,C); B holds max(0,1)=1, then max(1,1)=1; B's reply-send ticks to (2,B); A adopts max(1,2)=2. Final counters: A=2, B=2, C=1. Sorted stamps: (1,A) < (1,C) < (2,B).

• Vector clocks (one counter per process): detect causality AND concurrency, at O(n) state per node and O(n) bytes per message. Pay for it only when the product must know 'concurrent' — collaborative editing, causal delivery, CRDT metadata — not for plain ordering.

• Lost or duplicated message: adoption is idempotent (max twice is max once), but a lost message simply never advances the receiver — the order stays valid, only coarser. Never 'fill in' a stamp you did not receive.
• Process-ID collision: two processes sharing one ID break the tie-break and can stamp two events identically. Guard: assign IDs from one registry (or reuse the oracle of exercise 3) and crash on duplicate registration.
• Counter overflow: a u64 counter ticking per event lasts effectively forever at teaching rates; a tiny counter wraps and breaks the order. Guard: fix u64 and assert — never silently wrap.

Run: javac LamportDemo.java && java LamportDemo — stdlib Java only, instant.

Expected output: stamps A=(1,A), C=(1,C), B-reply=(2,B); sorted total order exactly (1,A) < (1,C) < (2,B); L(x) < L(y) with no causal path; OK. (actual output of this environment)

• Reading L(a) < L(b) as 'a caused b'. The stamp order is display order; causality needs a message chain from a to b.
• Claiming Lamport detects concurrency ('equal stamps mean concurrent'). Two message-free events may hold any stamps — equality proves nothing either.
• Reaching for wall-clock synchronization. Lamport needs no synchronized clocks at all — that is the point; adding NTP solves nothing here and adds skew failure modes.

• Three replicas n1/n2/n3, fixed membership; no rebalancing during the scenario.
• Single writer, ordered versions v1(old) < v2(new); the write targets w=3 but only n1 has stored v2 — partial, never acknowledged.
• Reads take r=2 and return the max version they meet; reader B's read starts after reader A's read returned.

Read1 may observe an incomplete write, but once it returns that value a later Read2 cannot go backwards. Before-return write-back places the observed version on a majority; every later majority intersects it. With n=3, two replicas suffice; targeting all three writes merely exposes the incomplete-write window. The proof also needs monotonic versions, fixed membership and a defined writer protocol.

1. Partial is not acked Separate targeted from acknowledged: the write aimed at w=3 but only n1 stored v2. Name it partial — no quorum owes it visibility.
2. Replay the violation Run the violating pair: read1 from {n1,n2} returns max(v2,v1)=v2 (concurrent, allowed); read2 from {n2,n3} starts after read1 returned and gets max(v1,v1)=v1. New-then-old with the inequality intact.
3. Write back before return Apply the ABD fix: the reader writes v2 back to {n1,n2} — a quorum — BEFORE returning. The re-read from {n2,n3} now meets v2. Repair before the return is the guarantee; repair after it is cosmetics.
4. Name the assumptions State the remaining assumptions honestly: single writer here (multi-writer needs a pre-write timestamp query), fixed membership (rebalancing needs joint quorums), and versions ordered by construction, never by wall clock.

Each replica stores (version, value) with totally ordered versions. Write path (single writer): stamp v+1, send to all three, wait for w ACKs — here only one lands, so the write stays in flight. Read path: query r=2, pick max version, write it back to r=2, then return. Multi-writer adds a query phase: read the highest timestamp from a quorum before stamping the write.

Teaching numbers: replicas hold (v2=new) on n1, (v1=old) on n2/n3. Read1 {n1,n2} = max(2,1) = v2. Read2 {n2,n3} = max(1,1) = v1 — violation. Write-back puts v2 on n2; re-read {n2,n3} = max(2,1) = v2 — fixed. Cost of the fix (teaching): one extra quorum round-trip on every read.

• Leader-based linearizable reads (read from the leader, or leader-confirmed reads): simpler to reason about, but every read pays leader latency and the leader is a bottleneck. Choose it when contention is low and simplicity beats read throughput; choose quorum register reads when reads must scale out.

• Reader crashes after observing v2 but before write-back: if the caller never got a response, the read never completed — no precedence edge, and the next reader's write-back still propagates v2. If it returned v2 then died mid-write-back, the completed read DID set precedence, and the duty passes to the next reader, which writes back whatever max it meets. Completed means the response reached the caller, not that the reader saw the value internally.
• Concurrent writers without a query phase: two writers stamping v2 independently fork the value — same version, different data. Guard: query the highest timestamp from a quorum first (ABD multi-writer), so versions stay unique per writer.
• Membership change mid-scenario: w + r > n computed over two different member sets overlaps nothing. Guard: joint quorums — old and new member sets must overlap each other until the change completes.

Run: javac QuorumDemo.java && java QuorumDemo — stdlib Java only, instant.

Expected output: read1 returns v2=new, read2 returns v1=old (violation true), after write-back read2 returns v2=new; OK. (actual output of this environment)

• Calling the targeted w=3 an acknowledged w=3. Sent-to-three is not stored-on-three; only ACKs count, and here there is one.
• Claiming background read-repair makes reads linearizable. Repair after the return is history cosmetics — the caller already saw the violation. Say 'eventual repair', never 'linearizable'.
• Comparing versions by wall-clock timestamps (LWW). Wall clocks skew; skewed stamps order values wrongly and silently. Versions here are logical and ordered by construction.

• One oracle allocator serves batches of 5 (teaching size); the high-water mark is durable, the handout pointer is volatile.
• Crash loses all volatile state and nothing durable; the standby (if any) starts from the same durable mark.
• Uniqueness, gap-free, allocation order and real-time observation order are four separate guarantees — define which the product needs before choosing.

Persisted high-water marks reserve every ID below them, including unissued ones; restarting above the mark exchanges duplication for gaps. A batch of b amortizes a durable write across b IDs but can lose up to b−1 unissued IDs on crash. Five makes the trade-off inspectable. Disjoint ranges support sharded uniqueness; global response order needs issuance-path control beyond fencing mark storage.

1. Mark first, serve second Persist the reservation before serving: reserve batch 1..5 durably, then hand out 1,2,3 from RAM. The mark-first order is the whole trick.
2. Crash the batch Crash mid-batch and recover from the mark: 4,5 were never issued, so next issues are 6,7. Gaps appear, duplicates never do — issued=[1,2,3,6,7].
3. Split the guarantees Separate uniqueness, gap-free allocation, allocation order and real-time response order. This batched design deliberately allows gaps; disjoint ranges provide uniqueness. Global ordering requires every issuance path to follow one ordering protocol.
4. Fence the failover The standby skips all durably reserved ranges and reserves new ones under an epoch fence. Never reassign an old range. An old leader may still issue unique but smaller RAM IDs; if global order is required, validate ownership on the response path too.

Components: one allocator (volatile handout pointer + batch cache), one durable store for the high-water mark, one standby replaying the mark log. API: reserve(batch) persists the mark and returns nothing servable yet; nextID() serves from RAM. Read path: serve from memory, no I/O. Write path: mark-first, then serve — a crash between them only skips IDs. Partition key: none — the oracle is one logical decider; scale it by batching, not by splitting the mark.

Teaching run: batch 1..5 reserved (hwm=5); issues 1,2,3; crash; recover from hwm=5; issues 6,7. Issued=[1,2,3,6,7]: gaps {4,5}, duplicates none. Shard demo: A issues A-1,A-2 while B issues B-1,B-2 — all four unique, yet A-2 may predate B-1 in real time.

• UUIDs (random, no coordination): uniqueness without any allocator or failover story, at the cost of no order at all and wider keys. Choose when order is never read — request IDs, tracing spans — never when something sorts by ID.
• Shard-prefixed IDs (A-*, B-* from disjoint ranges): unique and coordination-free with per-shard order, but no global real-time order. Choose when shards own their rows and cross-shard sorting is display-only.

• Failover without fencing: the old allocator revives and re-issues 1,2,3 beside the standby's 1,2,3 — duplicates, the one forbidden outcome. Guard: the standby takes a fresh epoch token and storage durably rejects the smaller epoch — the fencing rule from chapter 9, applied to allocator epochs, not per-write tokens.
• Mark persisted after serving: a crash between serving and persisting loses track of issued IDs — recovery re-issues them. Guard: mark-first ordering in code, asserted by a test that kills mid-batch (the demo).
• Two allocators on overlapping ranges (mis-sharding): disjointness assumed but never enforced gives duplicates across shards. Guard: ranges assigned from one config version, and each issuer stamps its shard prefix so overlap is detectable, not silent.

Run: javac OracleDemo.java && java OracleDemo — stdlib Java only, instant.

Expected output: issues 1,2,3 then crash, recovery from hwm=5, next issues 6,7; issued=[1,2,3,6,7], no duplicates; OK. (actual output of this environment)

• 'This oracle can never be sharded.' Wrong per guarantee: uniqueness shards freely with disjoint ranges; only gap-free and global real-time order resist sharding. Say which guarantee, or say nothing.
• Persisting the mark after serving ('batch the writes for speed'). A crash in between re-issues IDs — the one forbidden outcome bought for one fewer fsync. Mark first, always.
• Fencing per ID instead of per allocator epoch. Tokens must identify the allocator's lease epoch (one fencing check per failover), not each issued ID — per-ID tokens add a check to every issue for no extra safety.

• Single register, small histories (2-3 ops); bounded search enumerates permutations — teaching sizes only.
• Invoke/return stamps come from the harness clock; precedence uses done-before-starts only, never stamp comparison.
• Pending operations (no return stamp, e.g. timeouts) are indeterminate until branched both ways.

Enumerating orders makes a compatible sequential execution understandable for small histories. Worst-case n! permutations explain why it does not scale. Add a real-time edge only when A returns before B starts. A pending operation may have committed, so do not automatically discard it as failed. Harness time orders invocation/return; stored timestamps do not establish linearization points.

1. Stamp, then constrain Stamp every op with invoke/return from the harness. Precedence rule: if op X returned before op Y started, X must precede Y in every candidate order — the only hard constraint.
2. Enumerate keepers Enumerate candidate orders that keep precedence; overlapping operations permute freely. h1 admits one order (write, read); h3 admits both — freedom, not failure.
3. Judge each order Apply the register rule per order: walk it, track the latest write, each read must match. h2's only order demands 1 but holds 0 — reject. One surviving order accepts the history.
4. Fork the unknown Fork pending operations both ways: a timed-out write is indeterminate — accept if either the took-effect or the never-did branch validates. Then state the limit: the verdict binds this window only.

Harness: a wrapper around the key-value client stamping invoke/return per op (monotonic clock for durations, wall clock for the log). Checker: precedence graph from done-before-starts edges, then bounded permutation search with the register rule per order, pending ops forked both ways. Read path: collect a history window. Write path: none — the checker never writes, it judges.

Teaching histories: h1 = write(1) t0-t2, read-to-1 t3-t4 — one precedence-keeping order (write, read), read matches: LINEARIZABLE. h2 = same bars, read-to-0 — the only order demands 1: NOT LINEARIZABLE. h3 = write t0-t5 overlapping read t2-t4 to 0 — order (read, write) validates: LINEARIZABLE.

• Model checking the implementation (TLA+-style exhaustive search of the protocol): proves the design for bounded sizes instead of sampling executions. Stronger than a history checker, heavier to write — use it for the replication protocol itself, and keep the history checker for the running system.

• Lying harness clock (invoke stamped after return): precedence inverts and verdicts are garbage. Guard: monotonic clock for durations, sanity-assert invoke <= return on every op, drop windows that fail it loudly.
• Pending write treated as failed: a timed-out write may still take effect later — calling it failed lets a later read of its value look like a phantom. Guard: indeterminate modeling, both branches, always.
• History window too small to catch the race (sampling only quiet hours): the checker passes and confidence is false. Guard: sample across peaks and deploys, and say the verdict covers the window — never the system.

Run: javac CheckerDemo.java && java CheckerDemo — stdlib Java only, instant.

Expected output: h1 LINEARIZABLE, h2 NOT LINEARIZABLE, h3 LINEARIZABLE; OK. (actual output of this environment)

• Treating stamp comparison as precedence ('write stamped earlier must order first'). Precedence is done-before-starts on invoke/return intervals — stamp values, Lamport or wall, never decide it.
• Accepting on the first plausible order instead of searching all precedence-keeping orders for rejection. One valid order accepts; but you only know none exists after trying all.
• Running the checker on replica reads and 'fixing' failures by weakening the histories (dropping the stale reads). The checker found a real violation — fix the store (write-back, leader reads), never the evidence.