Summary
Begin replacing the pessimistic-lock join with lock-free splicing, starting at the base level (level 0). Today SkipNode.insert() searches for its level-0 left/right neighbors, then grabs insertion locks across every level via acquireNeighborLocks (an all-or-nothing multi-level lock grab wrapped in a random-backoff retry loop) before blindly writing every link. This part reworks only the base level: after the level-0 neighbors are located through search-by-identifier, the joining node splices itself into the level-0 doubly-linked list using the verify-and-forward link primitive/messages — each neighbor verifies ordering against its own current table and either accepts the link or forwards the request to the correct neighbor — with no lock acquisition at the base level. To keep the base-level slot from being written twice, the lock-based table build begins at level 1 and no longer locks or blindly writes level 0.
The upper-level tower is still built through the existing lock path, so all current sequential correctness and search behavior is preserved; converting the level-climb and taking the join off the lock path entirely is the follow-up part. The random-backoff retry that still guards upper-level lock acquisition therefore remains in place after this change — this part does not remove it. Grounded in Aspnes & Shah, arXiv:cs/0306043, Algorithm 2 (lock-free join).
Scope
src/main/java/skipnode/SkipNode.java
insert() (~70–136): keep the search-by-identifier bootstrap that finds the level-0 left/right neighbors; replace the base-level link step so the node splices in at level 0 through the verify-and-forward link primitive/messages — the local side sets its own level-0 slot and each neighbor applies the accept-or-forward primitive — instead of relying on the lock/announce path at that level.acquireNeighborLocks() (~155–233): begin lock acquisition at level 1 so the level-0 neighbors are no longer locked; the level-0 iteration may still be used to climb to the level-1 ladder, but it acquires no locks. Levels 1 and above are unchanged.insertIntoTable() (~326–345) / announceNeighbor() (~316–319): these perform a blind multi-level table write (updateLeftNode/updateRightNode with no order verification, invoked once per neighbor from minLevel up to the common-prefix length). Ensure the level-0 slot is no longer written by this path — level 0 is established solely by the verify-and-forward link — so the base-level slot is never written by two mechanisms.
src/test/java/skipnode/SkipNodeTest.java
- Add a base-level join test asserting that after sequential insertion the level-0 list is correctly ordered and back-pointer-consistent (if y is x's right neighbor at level 0 then x is y's left neighbor at level 0, and symmetrically), reusing the
tableCorrectnessCheck / tableConsistencyCheck helpers.
Acceptance Criteria
Dependencies
- The verify-and-forward table write primitive (verify the current slot, then set-or-forward atomically under the table's own lock, in a single critical section) must already be available on the lookup table.
- The verify-and-forward link request/response messages (accept-or-forward link, dispatched through the middle layer) must already be available.
Part of #33. Depends on: #34, #36
Summary
Begin replacing the pessimistic-lock join with lock-free splicing, starting at the base level (level 0). Today
SkipNode.insert()searches for its level-0 left/right neighbors, then grabs insertion locks across every level viaacquireNeighborLocks(an all-or-nothing multi-level lock grab wrapped in a random-backoff retry loop) before blindly writing every link. This part reworks only the base level: after the level-0 neighbors are located through search-by-identifier, the joining node splices itself into the level-0 doubly-linked list using the verify-and-forward link primitive/messages — each neighbor verifies ordering against its own current table and either accepts the link or forwards the request to the correct neighbor — with no lock acquisition at the base level. To keep the base-level slot from being written twice, the lock-based table build begins at level 1 and no longer locks or blindly writes level 0.The upper-level tower is still built through the existing lock path, so all current sequential correctness and search behavior is preserved; converting the level-climb and taking the join off the lock path entirely is the follow-up part. The random-backoff retry that still guards upper-level lock acquisition therefore remains in place after this change — this part does not remove it. Grounded in Aspnes & Shah, arXiv:cs/0306043, Algorithm 2 (lock-free join).
Scope
src/main/java/skipnode/SkipNode.javainsert()(~70–136): keep the search-by-identifier bootstrap that finds the level-0 left/right neighbors; replace the base-level link step so the node splices in at level 0 through the verify-and-forward link primitive/messages — the local side sets its own level-0 slot and each neighbor applies the accept-or-forward primitive — instead of relying on the lock/announce path at that level.acquireNeighborLocks()(~155–233): begin lock acquisition at level 1 so the level-0 neighbors are no longer locked; the level-0 iteration may still be used to climb to the level-1 ladder, but it acquires no locks. Levels 1 and above are unchanged.insertIntoTable()(~326–345) /announceNeighbor()(~316–319): these perform a blind multi-level table write (updateLeftNode/updateRightNodewith no order verification, invoked once per neighbor fromminLevelup to the common-prefix length). Ensure the level-0 slot is no longer written by this path — level 0 is established solely by the verify-and-forward link — so the base-level slot is never written by two mechanisms.src/test/java/skipnode/SkipNodeTest.javatableCorrectnessCheck/tableConsistencyCheckhelpers.Acceptance Criteria
tryAcquire/unlock) messages — the base-level splice is lock-free — and the level-0 slot is written solely by the verify-and-forward link path, never also by the blind lock/announce build.sequentialInsertion,sequentialSearchByIdentifier, andsequentialSearchByMembershipVectortests remain green.make lint(checkstyle) andmake test(mvn test) pass.Dependencies
Part of #33. Depends on: #34, #36