Summary
Periodic backpointer repair (Aspnes & Shah, arXiv:cs/0306043 — Algorithm 8, self-stabilizing backpointer repair) restores the invariant that if y is x's right neighbor at a level then x is y's left neighbor there (and symmetrically) — an invariant concurrent joins can transiently break. The repair sweep detects a broken backpointer by probing a peer, which the current RPC surface cannot express:
- CheckNeighbor — asks whether the receiver currently holds a given node as its neighbor at a
(level, direction); returns a boolean.
This issue delivers only the probe transport: the request type, packet class, MiddleLayer dispatch, client sender, and a thin read handler. The periodic repair sweep that consumes it (Algorithm 8) — including the relink action taken when a probe fails — lands in a separate issue and is out of scope here.
In-scope handler behavior (exact): the CheckNeighbor handler calls the existing lookup-table isLeftNeighbor/isRightNeighbor (selected by direction) and returns a BooleanResponse. It is read-only; it performs no table writes and takes no repair action.
Scope
src/main/java/underlay/packets/RequestType.java — add a CheckNeighbor enum entry.
src/main/java/underlay/packets/requests/ — add CheckNeighborRequest (the candidate neighbor plus level and direction).
src/main/java/underlay/packets/responses/ — reuse BooleanResponse. No new response class.
src/main/java/middlelayer/MiddleLayer.java — add a receive() dispatch case and a client sender, following existing conventions (receiverId routing, lock gating).
src/main/java/skipnode/SkipNodeInterface.java, src/main/java/skipnode/SkipNode.java — add the thin read handler described above, backed by isLeftNeighbor/isRightNeighbor. No table writes, no repair orchestration.
Acceptance Criteria
Dependencies
None. The periodic backpointer-repair sweep (Algorithm 8) that issues this probe and relinks on a failed check is a separate issue and out of scope here.
Part of #33. Depends on: none — ready to start
Summary
Periodic backpointer repair (Aspnes & Shah, arXiv:cs/0306043 — Algorithm 8, self-stabilizing backpointer repair) restores the invariant that if
yisx's right neighbor at a level thenxisy's left neighbor there (and symmetrically) — an invariant concurrent joins can transiently break. The repair sweep detects a broken backpointer by probing a peer, which the current RPC surface cannot express:(level, direction); returns a boolean.This issue delivers only the probe transport: the request type, packet class,
MiddleLayerdispatch, client sender, and a thin read handler. The periodic repair sweep that consumes it (Algorithm 8) — including the relink action taken when a probe fails — lands in a separate issue and is out of scope here.In-scope handler behavior (exact): the
CheckNeighborhandler calls the existing lookup-tableisLeftNeighbor/isRightNeighbor(selected bydirection) and returns aBooleanResponse. It is read-only; it performs no table writes and takes no repair action.Scope
src/main/java/underlay/packets/RequestType.java— add aCheckNeighborenum entry.src/main/java/underlay/packets/requests/— addCheckNeighborRequest(the candidate neighbor pluslevelanddirection).src/main/java/underlay/packets/responses/— reuseBooleanResponse. No new response class.src/main/java/middlelayer/MiddleLayer.java— add areceive()dispatch case and a client sender, following existing conventions (receiverIdrouting, lock gating).src/main/java/skipnode/SkipNodeInterface.java,src/main/java/skipnode/SkipNode.java— add the thin read handler described above, backed byisLeftNeighbor/isRightNeighbor. No table writes, no repair orchestration.Acceptance Criteria
RequestTypehasCheckNeighbor; a request class underrequests/carries the candidate neighbor pluslevelanddirection, and it maps toBooleanResponse(no new response class).MiddleLayer.receive()dispatches it, andMiddleLayerexposes a client sender, matching existing sender/dispatch conventions.(level, direction), via the existingisLeftNeighbor/isRightNeighbor; it is read-only.CheckNeighborbetween two linked nodes over the mock underlay and asserts true for a held neighbor and false otherwise.make testandmake lintpass. Total change including the test is well within 200 lines.Dependencies
None. The periodic backpointer-repair sweep (Algorithm 8) that issues this probe and relinks on a failed check is a separate issue and out of scope here.
Part of #33. Depends on: none — ready to start