Skip to content

[Protocol] Add CheckNeighbor repair handler #43

Description

@thep2p

Summary

Concurrent joins (Algorithm 2, Aspnes & Shah, arXiv:cs/0306043) splice a new node into each level's doubly-linked list without global coordination, so two nodes joining between the same pair of neighbors can transiently break the backpointer invariant: if y is x's right neighbor at level l, then x must be y's left neighbor at level l (and symmetrically). For example, with four nodes A < B < C < D where A and D are linked at a level, B and C joining concurrently between them can leave that level fragmented into A <-> B and C <-> D, with no node having failed.

Algorithm 8 (Section 5.2.1) repairs such fragments by having each node periodically check each neighbor per level and re-link to restore the invariant. This issue adds the responder half: the node-side handler that processes a CheckNeighbor request, together with its dispatch case in MiddleLayer.receive(). The periodic sweep that issues these requests is a separate follow-up.

The handler receives a level, a direction, and the counterpart the sender believes it is linked to, verifies it against its own current table through the relink primitive (a single-critical-section write that either sets the slot, reports it already consistent, or reports a different neighbor already occupying it), and returns the outcome so the sender can act on it.

Scope

  • src/main/java/skipnode/SkipNode.java — add a checkNeighbor handler method (alongside announceNeighbor, updateLeftNode, updateRightNode) that, given a level, direction, and expected counterpart, applies the relink primitive to the correct table slot and returns one of: already-consistent (no change), re-linked (slot set to restore the backpointer), or evicted (a different node already occupies the slot).
  • src/main/java/middlelayer/MiddleLayer.java — add the CheckNeighbor case to the receive() dispatch switch, mirroring the existing AnnounceNeighbor and UpdateLeftNode/UpdateRightNode cases: cast the incoming CheckNeighbor request (packet type supplied by the messages prerequisite), invoke the new handler, and return its outcome as the response. This issue owns that dispatch case — the messages prerequisite does not add it, because the handler the case must call is introduced here.
  • Tests (same issue): unit tests over the handler asserting each outcome — an already-consistent link is a no-op, a missing or incorrect backpointer is re-linked to satisfy the invariant, and a slot held by a different neighbor is reported as evicted rather than overwritten. Extend src/test/java/lookup/ConcurrentLookupTableTest.java where the handler's use of the relink primitive needs table-level coverage.

Acceptance Criteria

  • A checkNeighbor handler exists on the node and is reachable through MiddleLayer.receive() via a CheckNeighbor dispatch case added in this issue.
  • Given a level, direction, and counterpart, the handler restores the backpointer invariant when the slot is empty or already holds that counterpart, and reports the already-consistent case without a redundant write.
  • When the target slot holds a different neighbor, the handler reports that neighbor (evicted) and does not overwrite it.
  • The handler mutates the table only through the relink primitive — no separate read-then-write across two steps.
  • New unit tests cover the consistent, re-link, and evicted outcomes and pass under the existing test task; no existing tests regress.

Dependencies

Requires, in order:

  • The relink table primitive: a single-critical-section accept-or-forward write, with a relink variant that additionally reports the already-consistent (no-op) and evicted-neighbor cases. The handler is defined in terms of it.
  • The CheckNeighbor message: its request/response packet types, the RequestType enum entry, and the client-side MiddleLayer send method (the counterpart of announceNeighbor / updateLeftNode). This prerequisite supplies the packet types, enum entry, and sender only; the receive() dispatch case that routes a CheckNeighbor request to the handler is added by this issue.
  • The lock-free join: the join path must already splice via order-verification forwarding rather than distributed locking, so repair operates against a lock-free base rather than the retired locking protocol.

Part of #33. Depends on: #34, #37, #39

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