Skip to content

[Protocol] Add SetLink and Buddy splice RPCs #36

Description

@thep2p

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

  • RequestType has SetLink and Buddy; each has a request class under requests/ carrying its payload; both map to IdentityResponse (no new response class).
  • MiddleLayer.receive() dispatches both, and MiddleLayer exposes a client sender for each, matching existing sender/dispatch conventions.
  • SetLink handler performs a plain updateLeft/updateRight with replacement and returns the replaced neighbor; expected is carried in the packet for the deferred atomic verify-and-set primitive and is not consulted by this handler.
  • Buddy handler performs a single local set of the requested link and returns the holding identity; the accept-or-forward routing decision is not implemented here.
  • No new lookup-table write primitive is added, and insertion/join/repair orchestration is unchanged.
  • New public types and methods carry Javadoc (checkstyle clean).
  • A test exercises both messages end-to-end between two nodes over the mock underlay (dispatch reached; correct IdentityResponse payload returned). make test and make lint pass. 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 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

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