REPOSITORY CODING · HARD
Require stable tombstone coverage and a valid frontier
A zero stable frontier cannot cover a positive deletion dot. Independently, a claimed frontier ahead of any replica must be rejected before compaction.
Causal replication and compactionCausal register laboratory
Work through a real codebase.
Choose an environment, investigate the existing implementation and use the tests to check your change. Sign in to open a workspace; execution and Ono usage follow your plan’s allowances.
Task requirements and environments
Java · 80 minute session
- Simulate a bounded causal multi-value register map over 1..5 named replicas and at most 120 explicit set/delete/merge/compact events. Each replica is its own actor. Clocks start at zero, local actor counters are bounded by 200, and key/value lengths and identifiers are validated.
- A local write increments only its own actor counter, captures the previous vector context and replaces the observed versions of that key with one immutable dotted version. Delete writes a tombstone version. Concurrent unobserved values survive merge; observed overwritten versions must not reappear.
- Merge version sets using both causal clocks: keep shared dots and unshared dots not covered by the other side clock, then join clocks componentwise by maximum. Source replicas and version contexts retain ownership. Repeated and self merges are idempotent.
- Compaction removes only tombstones whose full context and dot are covered by an explicitly supplied stable frontier. The frontier must name every actor and be dominated by every replica clock in this rehearsal. Preserve causal clocks after removing tombstones so delayed merges do not resurrect overwritten values.
- Return sorted replicas, vector clocks and key entries with distinct sorted live values, sorted dot labels, deleted and conflict flags. Equal concurrent payloads represent one visible value while retaining both dots. This is an offline causal-state model, separate from the replicated-log consensus workbench.
Spring Boot · 80 minute session
- Simulate a bounded causal multi-value register map over 1..5 named replicas and at most 120 explicit set/delete/merge/compact events. Each replica is its own actor. Clocks start at zero, local actor counters are bounded by 200, and key/value lengths and identifiers are validated.
- A local write increments only its own actor counter, captures the previous vector context and replaces the observed versions of that key with one immutable dotted version. Delete writes a tombstone version. Concurrent unobserved values survive merge; observed overwritten versions must not reappear.
- Merge version sets using both causal clocks: keep shared dots and unshared dots not covered by the other side clock, then join clocks componentwise by maximum. Source replicas and version contexts retain ownership. Repeated and self merges are idempotent.
- Compaction removes only tombstones whose full context and dot are covered by an explicitly supplied stable frontier. The frontier must name every actor and be dominated by every replica clock in this rehearsal. Preserve causal clocks after removing tombstones so delayed merges do not resurrect overwritten values.