Summary
Lock-free join (Aspnes & Shah, arXiv:cs/0306043 — Algorithm 2) splices a joining node into each level's doubly-linked list by order-verified message forwarding rather than distributed locking: a neighbor receiving a link request verifies ordering against its own table and either accepts the link or forwards it to the correct neighbor. Two of the messages that splice step needs are missing from the current RPC surface:
- SetLink — asks the receiver to set its neighbor at a given
(level, direction) to a replacement, and carries {level, direction, expected, replacement} so a later conditional (verify-and-set) write can consult expected.
- Buddy — an order-verified link request: the identity to link plus the target
(level, direction).
This issue delivers only the message transport for these two: request types, packet classes, MiddleLayer dispatch, client senders, and thin receiver-side handlers. The order-verification accept-or-forward routing decision (Buddy) and the atomic conditional verify-and-set/relink guarantee (SetLink) are provided by separate issues — the lookup-table verify-and-set primitive and the Algorithm 2 join driver — and are NOT implemented or duplicated here.
In-scope handler behavior (exact, so no contributor hand-rolls a deferred path):
- SetLink handler: a plain
updateLeft/updateRight (selected by direction) on the local lookup table using replacement, returning the replaced neighbor as an IdentityResponse. expected is carried in the packet so its shape is final when the verify-and-set primitive lands, but this handler does NOT consult it — a compare-to-expected-then-write here would be a non-atomic read-then-write race, which is exactly why the atomic conditional is deferred to the table primitive.
- Buddy handler: a single local set of the requested link, returning the holding identity as an
IdentityResponse. The accept-or-forward routing decision is DEFERRED to the Algorithm 2 join driver; this issue does NOT implement a forwarding path.
Scope
src/main/java/underlay/packets/RequestType.java — add SetLink and Buddy enum entries.
src/main/java/underlay/packets/requests/ — add SetLinkRequest (level, direction, expected, replacement) and BuddyRequest (the identity to link plus level and direction).
src/main/java/underlay/packets/responses/ — reuse IdentityResponse for both (SetLink returns the replaced neighbor; Buddy returns the identity that holds the link). No new response class.
src/main/java/middlelayer/MiddleLayer.java — add a receive() dispatch case and a client sender for each new type, following existing conventions (receiverId routing, lock gating).
src/main/java/skipnode/SkipNodeInterface.java, src/main/java/skipnode/SkipNode.java — add the two thin handlers described above. No new lookup-table write primitive; no changes to insert() or the join/repair orchestration.
Acceptance Criteria
Dependencies
None required to land this transport. The atomic verify-and-set/relink lookup-table primitive that gives SetLink its conditional-write guarantee, and the Algorithm 2 join driver that sequences Buddy/SetLink to splice a joining node, are separate issues and out of scope here; this issue must not implement or duplicate that table primitive.
Part of #33. Depends on: none — ready to start
Summary
Lock-free join (Aspnes & Shah, arXiv:cs/0306043 — Algorithm 2) splices a joining node into each level's doubly-linked list by order-verified message forwarding rather than distributed locking: a neighbor receiving a link request verifies ordering against its own table and either accepts the link or forwards it to the correct neighbor. Two of the messages that splice step needs are missing from the current RPC surface:
(level, direction)to a replacement, and carries{level, direction, expected, replacement}so a later conditional (verify-and-set) write can consultexpected.(level, direction).This issue delivers only the message transport for these two: request types, packet classes,
MiddleLayerdispatch, client senders, and thin receiver-side handlers. The order-verification accept-or-forward routing decision (Buddy) and the atomic conditional verify-and-set/relink guarantee (SetLink) are provided by separate issues — the lookup-table verify-and-set primitive and the Algorithm 2 join driver — and are NOT implemented or duplicated here.In-scope handler behavior (exact, so no contributor hand-rolls a deferred path):
updateLeft/updateRight(selected bydirection) on the local lookup table usingreplacement, returning the replaced neighbor as anIdentityResponse.expectedis carried in the packet so its shape is final when the verify-and-set primitive lands, but this handler does NOT consult it — a compare-to-expected-then-write here would be a non-atomic read-then-write race, which is exactly why the atomic conditional is deferred to the table primitive.IdentityResponse. The accept-or-forward routing decision is DEFERRED to the Algorithm 2 join driver; this issue does NOT implement a forwarding path.Scope
src/main/java/underlay/packets/RequestType.java— addSetLinkandBuddyenum entries.src/main/java/underlay/packets/requests/— addSetLinkRequest(level,direction,expected,replacement) andBuddyRequest(the identity to link pluslevelanddirection).src/main/java/underlay/packets/responses/— reuseIdentityResponsefor both (SetLinkreturns the replaced neighbor;Buddyreturns the identity that holds the link). No new response class.src/main/java/middlelayer/MiddleLayer.java— add areceive()dispatch case and a client sender for each new type, following existing conventions (receiverIdrouting, lock gating).src/main/java/skipnode/SkipNodeInterface.java,src/main/java/skipnode/SkipNode.java— add the two thin handlers described above. No new lookup-table write primitive; no changes toinsert()or the join/repair orchestration.Acceptance Criteria
RequestTypehasSetLinkandBuddy; each has a request class underrequests/carrying its payload; both map toIdentityResponse(no new response class).MiddleLayer.receive()dispatches both, andMiddleLayerexposes a client sender for each, matching existing sender/dispatch conventions.SetLinkhandler performs a plainupdateLeft/updateRightwithreplacementand returns the replaced neighbor;expectedis carried in the packet for the deferred atomic verify-and-set primitive and is not consulted by this handler.Buddyhandler performs a single local set of the requested link and returns the holding identity; the accept-or-forward routing decision is not implemented here.IdentityResponsepayload returned).make testandmake lintpass. Total change including the test stays within 200 lines.Dependencies
None required to land this transport. The atomic verify-and-set/relink lookup-table primitive that gives
SetLinkits conditional-write guarantee, and the Algorithm 2 join driver that sequencesBuddy/SetLinkto splice a joining node, are separate issues and out of scope here; this issue must not implement or duplicate that table primitive.Part of #33. Depends on: none — ready to start