Summary
Building on the CheckNeighbor repair handler, this issue adds the initiator half of Algorithm 8 (Section 5.2.1, Aspnes & Shah, arXiv:cs/0306043): a periodic per-level sweep that restores the backpointer invariant — if y is x's right neighbor at level l then x is y's left neighbor at level l (and symmetrically). Concurrent lock-free joins (Algorithm 2) can transiently break it, fragmenting a level into disjoint pieces such as A <-> B and C <-> D (four nodes A < B < C < D, no node having failed) that the sweep must heal.
On each scheduler tick, the node walks every level, reads its right and left neighbors, and issues a CheckNeighbor to confirm the counterpart links back to it, re-linking when the outcome shows the backpointer is missing. Repeated rounds heal a fragmented level within a bounded number of sweeps.
Scope
src/main/java/skipnode/SkipNode.java — add a repair-sweep routine that, per level, reads the right neighbor (getRightNode) and left neighbor (getLeftNode) and issues a CheckNeighbor through the existing client-side MiddleLayer sender to verify or restore the backpointer, acting on the returned outcome (consistent → no action; re-linked → done; evicted → adopt the reported neighbor). Register the sweep as a periodic task with the scheduler abstraction once the node is inserted, and cancel it on terminate().- The client-side CheckNeighbor sender is provided by the messages prerequisite (the counterpart of
announceNeighbor / updateLeftNode in src/main/java/middlelayer/MiddleLayer.java); this issue consumes that sender as-is and does not add or modify it. No MiddleLayer change is needed here.
- Tests (same issue): using
src/test/java/unittest/LocalSkipGraph.java, build a graph, manually fragment one level into the A <-> B / C <-> D shape, run the sweep, and assert the backpointer-invariant check (tableConsistencyCheck) holds within a bounded number of rounds. Add a stability test asserting a sweep over an already-consistent graph makes no changes.
Acceptance Criteria
Dependencies
Requires, in order:
- The CheckNeighbor repair handler (the responder half of this repair work) — the sweep issues CheckNeighbor requests and relies on its consistent / re-link / evicted outcomes, and on the handler's
receive() dispatch case to answer them.
- The CheckNeighbor message: the sweep uses the client-side
MiddleLayer sender it provides, which must already be in place.
- The periodic scheduler abstraction that drives recurring per-node tasks and can be cancelled on shutdown; the sweep registers as one such task.
- The lock-free join, whose concurrent splices are what transiently fragment a level; repair heals that fragmentation.
Part of #33. Depends on: #42, #43
Summary
Building on the CheckNeighbor repair handler, this issue adds the initiator half of Algorithm 8 (Section 5.2.1, Aspnes & Shah, arXiv:cs/0306043): a periodic per-level sweep that restores the backpointer invariant — if y is x's right neighbor at level l then x is y's left neighbor at level l (and symmetrically). Concurrent lock-free joins (Algorithm 2) can transiently break it, fragmenting a level into disjoint pieces such as A <-> B and C <-> D (four nodes A < B < C < D, no node having failed) that the sweep must heal.
On each scheduler tick, the node walks every level, reads its right and left neighbors, and issues a CheckNeighbor to confirm the counterpart links back to it, re-linking when the outcome shows the backpointer is missing. Repeated rounds heal a fragmented level within a bounded number of sweeps.
Scope
src/main/java/skipnode/SkipNode.java— add a repair-sweep routine that, per level, reads the right neighbor (getRightNode) and left neighbor (getLeftNode) and issues a CheckNeighbor through the existing client-sideMiddleLayersender to verify or restore the backpointer, acting on the returned outcome (consistent → no action; re-linked → done; evicted → adopt the reported neighbor). Register the sweep as a periodic task with the scheduler abstraction once the node is inserted, and cancel it onterminate().announceNeighbor/updateLeftNodeinsrc/main/java/middlelayer/MiddleLayer.java); this issue consumes that sender as-is and does not add or modify it. NoMiddleLayerchange is needed here.src/test/java/unittest/LocalSkipGraph.java, build a graph, manually fragment one level into the A <-> B / C <-> D shape, run the sweep, and assert the backpointer-invariant check (tableConsistencyCheck) holds within a bounded number of rounds. Add a stability test asserting a sweep over an already-consistent graph makes no changes.Acceptance Criteria
terminate().tableConsistencyCheckpasses within a bounded number of sweep rounds.Dependencies
Requires, in order:
receive()dispatch case to answer them.MiddleLayersender it provides, which must already be in place.Part of #33. Depends on: #42, #43