Skip Graph の concurrent JOIN を考える - その1 - higepon blog
id:kibayos さんの PDF「構造化オーバレイの一貫性保証」 に書かれている Skip Graph の一貫性保証の例を読み解く。 http://live-e.naist.jp/sensor_overlay/3/doc/yoshida.pdf （PDF） 探索処理は任意のタイミングで実行可能 資料 P14 。 Join は下位レベルから上位へ Remove は上位レベルから下位へ なので上位から下位に検索する処理には影響がないとの事。 直感的に理解できなかったので具体例を考える。 各レベルでの処理は atomic であると仮定する。 以下のような初期状態の Skip Graph に対して [10] をスタートに key = [9] で検索。 level1: [5]<->[15] [7]<->[10] level0: [5]<->[7]<->[10]<->[15] この状態では検索結果
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Skip Graph の concurrent JOIN を考える - その2 - higepon blog