Skip to content

[Node] Implement: level-0 join linking (Phase 1) #90

Description

@thep2p

Summary

Implement Phase 1 of join: locate the predecessor via the existing search machinery, query its right neighbor, and send the two independent GetLinkOp requests that establish u's level-0 neighbors.

Algorithm detail, including the asymmetry note in step 7 (the s-chain and z-chain resolve u's two sides independently — never each other's), is specified in docs/protocol/concurrent-insert.md, Section 3.2.

Files

Acceptance Criteria

  • Reuses SearchByIdRequest/SearchByIdResponse unmodified for the predecessor search.
  • Handles the z = None case (no right neighbor known) without blocking.
  • Replies are applied to u's own table via try_link ([Core] Add try_link: atomic accept-or-forward slot decision #85) — no second write path.
  • Tests cover:
    • Normal two-sided link.
    • One-node-graph edge case (search returns the introducer itself).
    • z = None at query time.

Dependencies

Depends on: #84, #85, #88.

Dependency graph (unblocked first):
EPIC #81 -- local search & join protocol
  #67 [DONE] search_by_id            #71 [OPEN] search_by_mem_vec (independent)
  #74 [OPEN] search_by_id timeout fix   #76 [OPEN] delete/leave
  Concurrent join + repair (Algorithm 2 + Algorithm 8; supersedes closed #66, #77):
    L0 (no deps):         #84  #85  #93  #86  #87
    L1:                   #94  #88  #89
    L2:                   #90 <-- YOU ARE HERE  #91  #95  #96
    L3:                   #92
    L4 (acceptance gate): #97

Metadata

Metadata

Labels

No labels
No labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions