skip listと修復処理、両方向Chordまで

@kotabe @kumagi つまり、Chordも実は一方向にみえて、skip graphで言うレベル0では双方向ということで、並行join/leaveの問題はChordと同じ方法で回避しているかも、ということ？

2011-08-23 18:37:03

@kibayos 双方向だと並行join/leaveが鬼門になるのに、双方向の安定化がしやすいんですか。その場合の安定化というのは、並行でないjoin/leaveの事を指すんでしょうか。それが特にやりやすくなるとも思わないんですが、何か僕は見落としていますか。

2011-08-23 18:45:35

@kibayos @kotabe なるほど。確かにpredecessorは一つでいいですし…！

2011-08-23 18:46:35

@kibayos @kumagi Azureが並行join/leave問題をどう解決しているのかはわかりません．Chordと同じようにstabilizeするか，あるいは分散排他制御しているか．P2P環境ではないので並行join/leaveはそれほど発生しない気も．

2011-08-23 18:46:46

.@kotabe @kumagi （答えを急いでしまいました）自分の話の前提には、finger tableは含んでませんで、単純にレベル0のリングが対象。

2011-08-23 18:48:00

@kotabe @kumagi 私もそんな感じじゃないかと思っています。ところで、Chordと同様にstabilizeするとすると、これは面白いかも、と思ったと同時に結構わながありそうとも思いました。

2011-08-23 18:51:56

kumagi @kumagi_bot

ちょっと人間の脳みそが追いついてないだけで、同時に複数のP2Pに参加する事は簡単なので、双方向のChordを作るのは、順方向逆方向それぞれが別のハッシュ空間の別のP2Pだと思えば実はすごく簡単に双方向Chordって実現可能なんじゃないかとか思います。

2011-08-23 18:54:05

@kumagi 「双方向にすると安定化がやりやすい」はまだ感覚的な話なので、その前提で。安定化ですが、join/leaveのない状態で構造を整合化する処理と思ってください。

2011-08-23 18:55:11

@kumagi @kibayos 双方向でやりやすいのはリンクが切れたときの修復です（片方向だと修復するのが困難）．安定化(stabilize)と修復(recovery)は明確に分けた方がよいかと．

2011-08-23 18:58:35

@kumagi_bot 方向の違うChordを2つ重ねるってことでしょ。それはできると思いますが、平均1hopしか性能は稼げないですよ。それに対してオーバーレイのメンテナンスコストは倍。

2011-08-23 19:00:58

@kotabe @kumagi さらに概念の分化の話が出たので確認。修復は安定化に含まれるのはよいですか？修復じゃない安定化は何を差します？

2011-08-23 19:04:47

@kibayos @kumagi 修復が安定化に含まれるのかは定義（流儀）の問題な気が．修復じゃない安定化は，ノード故障が発生していない状態で必要な整合性確保処理じゃないでしょうか（例:Chordのstabilize）．

2011-08-23 19:09:37

@kotabe @kumagi つまり、「安定化」の定義が明確じゃないと。それに対して、「修復」は明確。確かに「双方向の方が安定化しやすい」より「双方向の方が修復しやすい」の方が解りよいです。ところで、skip graphの場合は安定化=修復なのでしょうか？

2011-08-23 19:13:32

skip graph上で実現する区間(interval)検索について考える->区間木について調べる->木構造とskip listの関係について考える->skip listの深淵にはまる->つぶやく->kumagi氏が来て炎上->kotabe先生が来てさらに炎上（今ココ）

2011-08-23 19:20:22

@kibayos @kumagi DDLLを使う場合は，Chord的なstabilizeは不要ですが，ネットワーク分断からの回復とか，ノード故障誤検出からの回復は，修復なのかな・・RT @kibayos: ところで、skip graphの場合は安定化=修復なのでしょうか？

2011-08-23 19:26:19

@kotabe @kumagi うーむ、深いです。

2011-08-23 19:27:05

そしたら双方向のほうが良いと思う派だなぁ

2011-08-23 19:28:06

finger tableで参照し合うことが出来るから。

2011-08-23 19:29:06

@did2memo 参照しあえるとそんなに効率に響くんですか？

2011-08-23 19:30:53

@kumagi 最適化のしやすさが大きく違うと思う。コネクションがどうのこうのとか、生存確認がどうのこうのとか、受け取ったクエリの有効活用とか。もったいない精神を活かしたいなら双方向、みたいな。

2011-08-23 19:42:36

@did2memo うーん、コネクションはたかだか160とかケチっても大差ないし、生存確認はsuccessor以外元々やらないだろうし、hop数が減る以外の恩恵が無いと微妙な気がします。

2011-08-23 20:37:24

@kumagi 双方向のデメリットを何だと思って言ってる？

2011-08-23 20:45:12

@did2memo 筆頭に挙げるのが実装のめんどくささ。めんどくささの割に僅かなメリットしかないなら微妙。

2011-08-23 21:00:27

@kumagi @did2memo お二人の議論には前提のずれがあるように思います。アルゴリズムをChordのまま変えないでやるか、アルゴリズム自体を両方向に向けて改良するか。それによって結果が全然違う。

2011-08-23 21:09:05