Skip to content

[Node] Implement: Stage-2 join and join entry point #92

Open

Description

@thep2p

Summary

Implement Phase 2 of join: the per-level BuddyOp climb on both sides, stopping at the first level where neither side has a match.

Algorithm detail: docs/protocol/concurrent-insert.md, Section 3.3.

This issue also owns the top-level join entry point that runs Phase 0, then Phase 1, then Phase 2 in sequence. No other issue owns it. #88 covered Phase 0 only, and #90 covers Phase 1 only. The entry point is listed in docs/protocol/concurrent-insert.md, Section 9. Scope extended per the PR #139 review (#139 (comment)).

Scope

  • src/node/base_node.rs — Phase 2 orchestration, starting from u's Stage-1 level-0 neighbors.
  • src/node/base_node.rs, join entry point: an async join orchestration method on BaseNode (Sections 3.0 to 3.3 and 9). It calls BaseNode::get_max_level against the introducer (Phase 0), passes the result as the max_level argument of BaseNode::join_stage1_link_level0 (Phase 1), then runs the Phase 2 climb above. Its visibility matches the phase methods it calls (pub(crate) today), unless the design doc names a different one.

Acceptance Criteria

  • Both sides queried concurrently per level, not sequentially.
  • A side that resolves None at some level stays None for all higher levels (no re-querying a dry side).
  • Height = last level where either side still matched.
  • Tests cover: multi-level climb, one side going dry before the other, both sides dry at level 1 (height 0), single-node-graph edge case.
  • The join entry point runs Phase 0, Phase 1, and Phase 2 in that order, and is the production caller of get_max_level and join_stage1_link_level0.
  • max_level from Phase 0 reaches Phase 1 as a parameter. It only seeds the starting level of the Stage-1 search, a latency optimization (Section 3.1).
  • Every wait inside the entry point is timeout-bounded.
  • A test drives the whole sequence (Phase 0, Phase 1, Phase 2) through the entry point, with every async wait timeout-bounded.

Dependencies

Depends on #84, #85, #88, #90 — Stage-2 starts from Stage-1's output.

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  #91  #95  #96
    L2.5 (link round-trip follow-ups; #146 blocks #92): #145  #146
    L2.5 (stage-1 concurrent-join fix; blocked by #90, blocks #97): #148
    L3:                   #92 <-- YOU ARE HERE
    L4 (acceptance gate): #97
    L5 (post-gate cleanup; also blocked by #76): #100
  Test-suite cleanup, blocked by #90:
    #147
  Test infrastructure, mock network hub (#62's latency simulation builds on #149's queue):
    #149 (blocked by #90, blocks nothing)
    #62 (no blocker)

Metadata

Metadata

Assignees

Labels

No labels
No labels

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions