Skip to content

[Testing] Add deterministic concurrent-join repair regression test #45

Description

@thep2p

Summary

Once the lock-free join and periodic backpointer repair land, we need a deterministic regression test that reproduces the concurrent-join partition and proves repair heals it. The partition is a transient break of the backpointer invariant (if y is x's right neighbor at a level, x must be y's left neighbor, and symmetrically): for four nodes A < B < C < D with A and D already linked at a level, B and C joining concurrently between them can fragment the level list into A<->B and C<->D — each side keeping only half of the splice, reachable with no node failures — which the paper's periodic repair (Aspnes & Shah, arXiv:cs/0306043) heals in a bounded number of rounds.

This issue adds a scheduler-driven test that inserts N nodes concurrently, drives repair rounds deterministically, then asserts the correctness and consistency (backpointer) invariants. It also de-flakes the existing concurrentInsertions test (currently marked flakey) and fixes MvpTest, which is pinned to 5 nodes because it fails when the node count grows.

Scope

  • src/test/java/skipnode/SkipNodeTest.java
    • Add a new deterministic test (e.g. concurrentJoinRepairRegression) that builds N nodes via LocalSkipGraph, inserts all of them concurrently, steps message delivery and repair rounds through the deterministic test scheduler until quiescent, then runs tableCorrectnessCheck and tableConsistencyCheck (lines 27-42 and 46-62) across every node.
    • De-flake concurrentInsertions (method spans lines 149-192): delete the // TODO: this test is flakey; fix it! marker at line 148 (immediately above the @Test) and make correctness depend on scheduler-driven delivery and repair rather than a timed await.
  • src/test/java/integration/MvpTest.java
    • Remove the hardcoded NODES = 5 cap and the // TODO: this test fails if number of nodes increased marker (lines 30-31); raise/parameterize NODES and drive insertion plus repair deterministically so full-connectivity searches pass at larger sizes.

Acceptance Criteria

  • A new deterministic test in SkipNodeTest inserts N nodes concurrently (N large enough to exercise concurrent splices, e.g. the existing NODES = 20), drives repair rounds via the test scheduler, and passes tableCorrectnessCheck and tableConsistencyCheck for every node with no wall-clock sleeps.
  • The test reproduces concurrent-join partitions and, after a bounded number of repair rounds, tableConsistencyCheck holds for all nodes.
  • The test is repeatable: it passes deterministically across repeated runs (seeded / scheduler-driven), with no reliance on timed await for correctness.
  • concurrentInsertions no longer carries the flakey TODO and passes deterministically.
  • MvpTest no longer hardcodes NODES = 5 or carries the scaling TODO; MVP_TEST passes full-connectivity searches at a larger node count (e.g. >= 20).
  • Total change is <= 200 lines including test code, and ships in this issue.

Dependencies

Requires these capabilities to land first:

  • An accept-or-forward table write primitive: verify the current slot, then set-or-forward atomically under the table's own lock, with a relink variant that additionally reports already-consistent (no-op) and evicted-neighbor.
  • The join/repair message types: an order-verification link request that a neighbor either accepts or forwards to the correct neighbor, and the relink request used by repair.
  • The lock-free insert/join rewrite (Algorithm 2) that splices a joining node into each level's doubly-linked list via order-verification forwarding.
  • Removal of the pessimistic multi-level neighbor locking and random-backoff retry, so concurrent joins no longer serialize.
  • A deterministic test scheduler that can step message delivery and trigger repair rounds on demand (no wall-clock timing).
  • The periodic backpointer repair / self-stabilization (Algorithm 8, Section 5.2.1) that re-links neighbors to restore the invariant.

Related: #12.


Part of #33. Depends on: #35, #41, #44

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions