Skip to content

[Protocol] Splice the upper-level tower lock-free via ladder #39

Description

@thep2p

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

  • 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.
  • After sequential insertion, every node's tables are correct and back-pointer-consistent at all levels.
  • sequentialInsertion, sequentialSearchByIdentifier, and sequentialSearchByMembershipVector pass, along with the new multi-level join test.
  • make lint (checkstyle) and make test (mvn test) pass.

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

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