Multi-key Skip Graph のマルチレンジフォワード方式を理解しよう

以下「単一ピアに複数キーを保持可能とする Skip Graph 拡張の提案」という論文で提案されている Multi-key Skip Graph の話。論文は id:kibayos さんなどによって書かれたもの。

論文の [1-6] 検索の詳細を追う。動作の主体と、それが入手可能な情報を意識しつつ。

物理ピア [0, 00] にクエリ [1-6] が行く。
物理ピア 00 は Level 2 のリンクをたどる事で [3, 00] と [6, 00] がクエリ結果に含まれる事を知る
物理ピア 00 は上記と同様に [1-3]、[3-6] の 2 つの区間に、別の物理ピアが保持する仮想ピアが含まれる可能性がある事を知る。
物理ピア 00 の [1, 00] において1つ下のレベルに下がり、仮想ピア [2, 01] を発見する。これは [1-3] に含まれるので 01 が代表ピアである。
物理ピア 00 の [3, 00] において1つ下のレベルに下がり、仮想ピア [4, 01] を発見する。これは [3-6] に含まれるので 01 が代表ピアである。
たまたま代表ピアが 01 と同じなので [1-3], [3-6] のクエリはまとめて 01 に送られる。
物理ピア 01 は Level 1 のリンクをたどる。クエリ [1-3] において [2, 01] がクエリ結果に含まれる事を知る。Level 0 を見る事で [1-2] [2-3] の間には他の物理ピアがない事を知る。
物理ピア 01 は Level 1 のリンクをたどる。クエリ [3-6] において [4, 01] がクエリ結果に含まれる事を知る。Level 0 を見る事で [3-4] の間には他の物理ピアがない事を知る。逆に [4-6] の間には物理ピア 10 があるのでクエリ [3-6] を 10 に送る。
物理ピア 10 は Level 0 をだどり、[5, 10] がクエリ結果に含まれる事を知る。
結果をマージする。