Project: audit a live depot index and recovery path

Live graph and historical index

Start with D-19 linked to D-26 and D-47 isolated. Ask whether D-19 reaches D-47, add D-26 to D-47, ask again, delete that link, and ask again. Require false, true, false. Add a second route before deletion and check that an alternate path keeps the depots connected. Reject a duplicate add and an absent removal. For the ordered index, retain the root containing asset 47, add asset 61 under a fresh root, then remove 47 under a third. Query all three roots. Check that a subtree untouched by an edit is reused by identity and that old owners remain unchanged.

Restart and queue schedule

Append a complete transaction frame for P-19 and P-26, sync it, then inject a short final frame for P-52. Replay must return only the complete transaction and trim the torn tail. Replace a byte in a full frame and require a checksum error rather than quiet truncation. Run the queue schedule with a stale tail observation: the stale link must fail after another offer has linked its node. Check FIFO order, then explain why the same Python assignments cannot establish lock-free progress or safe memory reclamation under concurrent execution.

Acceptance trace

Live route: false, true, false
Old ordered root: asset 47; third root: asset 61
Recovered pages: P-19, P-26; torn P-52 absent
Stale link: false; drained jobs: J-47, J-61

Cost and failure review

Adjacency updates do expected O(1) hash-set work, while a route question may visit O(V + E) graph entries. The treap expects O(log N) copied nodes per edit but has O(N) worst-case height. A framed journal append writes O(B) bytes and waits on fsync; replay reads O(L) journal bytes. The queue schedule is only sequential. Record those bounds beside their assumptions. Add a single-writer rule, version-retention policy, and restart-before-append rule to the implementation contract. A production storage engine needs checkpointing, a durable filename protocol, process coordination, and fault testing beyond this exercise.

Common Mistakes

• Do not keep a union-only component cache after deleting an edge.
• Do not edit a node reachable from an older index root.
• Do not silently replay past a full checksum failure.
• Do not append behind an incomplete tail without recovery.
• Do not describe a sequential CAS schedule as a concurrent lock-free implementation.

Connected lessons

• Online connectivity: answer after each edge change
• Persistent ordered indexes: copy search paths, share subtrees
• Framed journals: detect a torn tail before replay
• CAS queue protocol: link, help, and reclaim safely
• Project: plan a reversible depot release
• Projects
• Quizzes
• Data Structures