ホームページ
-http://www.panic-lab.rutgers.edu/Research/planetp/

PlanetP: Using Gossiping to Build Content Addressable Peer-to-Peer
-http://www.cs.rutgers.edu/~tdnguyen/pubs/cuenca-hpdc-2003.pdf


*基本アイディア
DHTがnameからlocationの解決と言った、いわばDNS的な世界なのに対し、PlanetPは、P2P上の全文検索、いわばgoogle的な世界です。
P2Pの全文検索と言うと、GnutellaベースのInfrasearchが最初に思いつきます。Infrasearchは、簡単に言うと、検索queryをP2Pのノード群に伝播させるイメージです。
一 方、PlanetPの基本戦略は、各ノードがローカルの全文検索用インデックス(単語から文書を索くインデックス)を作り、P2Pのノード群に拡散しま す。各ノードは、他ノードの全ての全文検索用インデックスをローカルに持つイメージです。本物の全文検索用インデックスを全体にばらまいたら、ネットワー クトラフィックも各ノードのディスクも大変なことになるので、Bloom Filterを使います。
各ノードは、次に述べるgossipingアルゴリズムで、ローカルのBloom Filterを拡散します。
各ノードは、「ノードのアドレス + Bloom Filter」ペアの集合を保持します。ローカル上のBloom Filter(のコピー)の集合に対して、全文検索を行い、検索結果対象の文書を持つノードにアクセスして文書を取得します。


*gossiping(ゴシッピング)
次のふたつの基本戦略の組み合わせで、P2Pの中に情報を拡散するアルゴリズムです。
+ rumor mongering (意訳: 噂好きのおばさんモデル)
+ anti-entropy (意訳: 悪魔くんモデル)

** rumor mongering
次のように動作します。

情報拡散元のノードをxとします。
1. ノードxはゴシッピングを開始すると、インターバルTg秒ごとに適当なノード(ノードyと呼びます)を選択して、情報を送りつけます(噂の送信)。
2. 情報を受けたノードyも、同じロジックで情報の送信を開始します。
3. ゴシップの送信先ノードが連続してn個、既にその情報を持っていた場合、ゴシップの送信を止めます。

適切なnを選ぶには、全体のノード数に関する知識が必要な気はしますが、そこを無視すると、非常に局所的な状態管理だけで全体に情報を拡散させることができるアルゴリズムです(全体に行き渡ったかどうかは確率的ですが)。
それぞれのノードが勝手にひそひそとおしゃべりをしていき、みんなに噂が行き渡った頃には、自然におしゃべりが止まります。

PlanetPのTgの初期値のデフォルトは30秒です(動的に変動します)。


** anti-entropy(アンチエントロピー)
rumor mongeringがpush的な拡散なのに対し、anti-entropyはpull的に動作します。
PlanetP では、rumor mongeringの10回に1回、anti-entropyにモードが切り替わります。anti-entropyモードの場合、適当に選んだノードyか ら、ノードyが持つ全ての情報のsummaryをpullします。ノードyが持つ全ての情報とは、ノードyが知っている他ノードのBloom Filter群です。summaryが具体的に何かは不明です(ノードIDと対応するBloom Filterの最終更新時刻で良い気がしますが不明です)。
要は、ノードxは、自分が知らない情報をノードyが持っているようなら、ノードyからpullします。

上のrumor mongering(push)とあわせて、P2Pノード間で、Bloom filterが相互に交換されるイメージです。

** partial anti-entropy
anti-entropyは重いやりとりなので、ちょっとした工夫をしています。
rumor mongering(push)の時、ノードyは、持っている最新の情報のid(このidはやや不明。上のsummaryと同じく、ノードIDと対応する Bloom Filterの最終更新時刻で良い気がします)を返します。ノードxは自分が知らない情報をノードyが持っているようなら、rumorのpushのついで に、ノードyから情報をpullします。
ノード間の情報の同期が少しでも可能ならその機会は逃すな、と言う、微妙に貧乏臭い戦略ですが、ぼくはこういうハックは好きです。


* Brokerサービス(Consistent Hashing。ほとんどDHT)
gossipingの情報拡散の速度には限度があります。PlanetPでは、数千ノードで約10分だそうです。
この辺の批判をかわすためか分かりませんが、一応、Brokerサービス(ある意味、サーバ)もオプションとして許しています。
一応、書いてあるだけで、たいして説明はしていません。


* content search
いわゆる全文検索の話です。良く知られた戦略のP2P応用です。要は、不完全な情報しか揃っていない状況でもそこそこうまく全文検索しよう、という話です。
vector空間rankingモデルのTFxIDF(Term Frequency x Inverse Document Frequency)が基本です。
TFxIDF は、文書の中に多く現れる単語(term)はその文書にとって重要だと見なし、一方、多くの文書に共通して多く現れる単語の重要度は相対的に下げる戦略で す。この文書で言えば、「PlanetP」という単語は多く出現して、かつ他の文書には出てこなさそうなので大きな評価値がつくでしょう。一方、「全文検 索」や「ノード」のような単語は多く出現しても、他の文書にも多く出てきそうなので、あまり大きな評価値にはならないでしょう。
検索queryの単語(複数あっても良い)が与えられると、文書のvector空間との類似度から、検索にヒットする文書が決まります。

この辺の話は、全文検索を説明しているサイトでもっと詳しく説明しているので、興味があれば探してください。

TFxIDFはP2Pと全然関係無い話で、PlanetPのポイントは次のふたつです。
+ 検索結果のノードのランキングのためのIPF(Inverse Peer Frequency)
+ どういう風に見つかったノードにアクセスするか

IPF はIDFからの類推で分かるように、多くのノード(ピア)がその単語(term)でひっかかる文書を持っているなら、その検索結果の価値を下げる戦略で す。これを利用することで、あまり他のノードがひっかからない単語で文書を見つけたノードは、検索結果の価値が高いと見なします(最初に説明したように、 各ノード上で全文検索するわけではなく、実際の全文検索はローカルにあるBloom Filterのコピーで行います)。