Summary
Complete the lock-free join by converting the level-climb to membership-vector ladder splicing and taking the join off the pessimistic-lock path entirely. After the base-level splice, the joining node climbs level by level: at each level above the base it locates the correct left/right neighbor through the membership-vector ladder (findLadder) and splices itself in with the same verify-and-forward link primitive/messages used at the base level. insert() stops calling the lock machinery (acquireNeighborLocks, and the tryAcquire/unlock messages) and the random-backoff retry loop is removed, so the join sends no neighbor lock acquire/release messages and performs no backoff sleep at any level. The lock infrastructure (the acquireNeighborLocks method and the InsertionLock type) is left in place but dormant/uncalled; removing it is a separate downstream change. Grounded in Aspnes & Shah, arXiv:cs/0306043, Algorithm 2 (lock-free join).
Concurrency note: concurrent joins can transiently break the back-pointer invariant across levels — for example, two nodes joining concurrently between the same pair of neighbors can leave a level fragmented, each side keeping only one half of the splice. Restoring the invariant under concurrency is the job of a separate periodic self-stabilizing repair change (Aspnes & Shah, arXiv:cs/0306043, Algorithm 8) and is out of scope here; this part is validated against sequential (deterministic) insertion only.
Scope
src/main/java/skipnode/SkipNode.java
insert() (~70–136): replace the upper-level portion so each level above the base is spliced via findLadder plus the verify-and-forward link primitive/messages; remove the call to acquireNeighborLocks, the surrounding random-backoff retry loop, the owned-locks table build, and the lock-release loop. The join no longer calls tryAcquire/unlock at any level.acquireNeighborLocks() (~155–233): no longer called by the join; leave it dormant for the separate lock-removal change (do not delete it here).findLadder() (~280–308): reused unchanged to locate each level's neighbor during the climb.
src/test/java/skipnode/SkipNodeTest.java
- Add a multi-level sequential join test asserting table correctness and back-pointer consistency across all levels (full towers), reusing the
tableCorrectnessCheck / tableConsistencyCheck helpers.
Acceptance Criteria
Dependencies
- The base-level lock-free bootstrap (the preceding part) must land first.
- The verify-and-forward table write primitive and the verify-and-forward link request/response messages must be available (as in the preceding part).
Part of #33. Depends on: #38
Summary
Complete the lock-free join by converting the level-climb to membership-vector ladder splicing and taking the join off the pessimistic-lock path entirely. After the base-level splice, the joining node climbs level by level: at each level above the base it locates the correct left/right neighbor through the membership-vector ladder (
findLadder) and splices itself in with the same verify-and-forward link primitive/messages used at the base level.insert()stops calling the lock machinery (acquireNeighborLocks, and thetryAcquire/unlockmessages) and the random-backoff retry loop is removed, so the join sends no neighbor lock acquire/release messages and performs no backoff sleep at any level. The lock infrastructure (theacquireNeighborLocksmethod and theInsertionLocktype) is left in place but dormant/uncalled; removing it is a separate downstream change. Grounded in Aspnes & Shah, arXiv:cs/0306043, Algorithm 2 (lock-free join).Concurrency note: concurrent joins can transiently break the back-pointer invariant across levels — for example, two nodes joining concurrently between the same pair of neighbors can leave a level fragmented, each side keeping only one half of the splice. Restoring the invariant under concurrency is the job of a separate periodic self-stabilizing repair change (Aspnes & Shah, arXiv:cs/0306043, Algorithm 8) and is out of scope here; this part is validated against sequential (deterministic) insertion only.
Scope
src/main/java/skipnode/SkipNode.javainsert()(~70–136): replace the upper-level portion so each level above the base is spliced viafindLadderplus the verify-and-forward link primitive/messages; remove the call toacquireNeighborLocks, the surrounding random-backoff retry loop, the owned-locks table build, and the lock-release loop. The join no longer callstryAcquire/unlockat any level.acquireNeighborLocks()(~155–233): no longer called by the join; leave it dormant for the separate lock-removal change (do not delete it here).findLadder()(~280–308): reused unchanged to locate each level's neighbor during the climb.src/test/java/skipnode/SkipNodeTest.javatableCorrectnessCheck/tableConsistencyCheckhelpers.Acceptance Criteria
insert()sends no AcquireLock/ReleaseLock messages at any level and performs no random-backoff sleep; the join is lock-free from the base level through the top of the tower.sequentialInsertion,sequentialSearchByIdentifier, andsequentialSearchByMembershipVectorpass, along with the new multi-level join test.make lint(checkstyle) andmake test(mvn test) pass.Dependencies
Part of #33. Depends on: #38