Capstone Thread: An Ordered Event Pipeline

Build an in-memory event pipeline from the module primitives. Budget 6–8 hours after the labs. This is a transfer artifact with explicit scope: no persistence, concurrency or crash-recovery guarantee is implied.

Core contract

Accept finitely many shard iterators sorted by integer timestamp; records contain an immutable event ID and payload. Emit timestamps in nondecreasing order, breaking ties by shard number and then within-shard input order. Deduplicate IDs using the rule "the first event in this merged order wins." An event's payload is not comparable and must stay associated with its ID. IDs may use the lab's integer map contract; define errors and duplicates before implementing.

Design and evidence

Use one queue head per nonempty shard. Maintain a seen-ID dictionary, and explain why its state is O(U) for U distinct IDs: the complete pipeline is O(K+U) state, not O(K), even though the merge alone uses O(K). The deterministic teaching map has collision-dependent time, so do not claim the pipeline is unconditionally O(N log K). State a separate expected bound only under an appropriate dictionary model. Retaining output adds another O(N) term.

Submit source, input/output contract, merge and deduplication invariants, cost and memory accounting, and tests for empty shards, equal timestamps, repeated IDs in different shards, noncomparable payloads, negative timestamps and highly colliding IDs. Compare finite fixtures to a simple flatten/stable-sort/deduplicate oracle; that oracle is permitted in tests, not in the bounded-head implementation.

Change request

Choose one: require global arrival-order ties; expire deduplication IDs after a window; or allow event cancellation/reinsertion. State what extra metadata or state is needed and which original proof fails. For a window, define event-time versus processing-time behavior and late arrivals before claiming bounded memory. For cancellation, protect against stale versions. Include a minimal counterexample to the unchanged design and a fresh regression for the revised contract.

Acceptance

Correct stream order, record identity, deduplication semantics, and retained-state accounting are mandatory. Document any assumptions your implementation relies on. Review with the competency rubric, then perform a delayed fresh transfer task. Do not substitute a polished demo or benchmark chart for the invariants.