[DHT]DHTとホップ数の関係[その2]～Chordの平均ホップ数を考えよう - Tomo’s HotLine
IT技術を中心に、暮らしに役立つ情報からクラシック音楽の解説まで気軽に情報発信しています。 WEBサイトはhttp://toremoro21.world.coocan.jp/ Twitterは@toremoro21です。 前回は直感的な方法でDHTのホップ数について推定した。今度はChordに絞ってホップ数を調べる事でより理解を深める事にしよう。 □Chordのリンク数からホップ数を推定 まず、Chordのノード参加数をN=2^xとしよう。2^ｘとは２のｘ乗を表す事とする。ここで1ノード当たりのリンク数はlog(N)＝ｘである事に注意。 平均ホップ数を計算するときに発想を転換しよう。今1ノードｘあたりのリンクがある。すると、P回ホップ数すると、ホップ可能な総ノード数LはだいたいL=x^Pとなる。x^P=Nであれば、P回ですべてのノードにアクセスできると大体考えられる事ができる。つまり、平均
![[DHT]DHTとホップ数の関係[その2]～Chordの平均ホップ数を考えよう - Tomo’s HotLine](https://cdn-ak-scissors.b.st-hatena.com/image/square/b4e38426fa9529bdb687a0c8ea1406a0f5bee683/height=288;version=1;width=512/http%3A%2F%2Ftoremoro.tea-nifty.com%2F.shared-cocolog%2Fnifty_managed%2Fimages%2Fweb%2Fogp%2Fdefault.png)
[DHT]DHTとホップ数の関係[その１]～直感的な方法 - Tomo’s HotLine
IT技術を中心に、暮らしに役立つ情報からクラシック音楽の解説まで気軽に情報発信しています。 WEBサイトはhttp://toremoro21.world.coocan.jp/ Twitterは@toremoro21です。 DHTの論文を見るとホップ数についての記述があるが、その計算根拠について書いてない場合が多い。 ここでは簡単な方法を使ってホップ数のオーダーを考えてみよう。 なお、次回以降には微分方程式・数列等を使うことにより、より詳細な考察を行う予定である。 今回はCANとChordについて書いてみることにする。 □CAN CANについての概要は以下のサイトをご覧になってほしい。 P2Pと分散ハッシュテーブル～その１ 今、２次元空間のCANを考える。縦、横ともnの大きさがあるとすると、ノード数はN=n^2である。ただし、^2は二乗を表すこととする。 ホップ数については、（0,0)という
P2P概論 — ありえるえりあ
** P2Pの技術的位置付け 技術者の多くは、世の中に次から次に現れる新しい技術用語を冷めた目で見ていると思います。些細な差に新しい用語を当てることが多いからです。本誌の読者の中にも、P2Pなんて用語には技術的に何の意味も無いと否定している人もいると思います。今から、P2Pという用語の技術的な位置付けを行います。読んで賛同してくれる人もいると思います。こんな分類に意味が無いと感じる人もいるかもしれません。賛同できない場合でも、本記事の範囲では、P2Pをこう位置づけて書いている、と理解して読んでください。 P2Pという用語で最も誤解を招きやすい表現は、P2Pは個人のPCが直接通信するネットワークです、という言い方です。個人のPCが直接やりとりするので、yahooのWebサーバにアクセスすることとは訳が違う、と言われても、普通の技術者であれば反発を覚えるのが普通でしょう。そもそもPCの定義とは
[P2P]ブラウザだけで分散ハッシュテーブル(DHT)を体感しよう！ - Tomo’s HotLine
IT技術を中心に、暮らしに役立つ情報からクラシック音楽の解説まで気軽に情報発信しています。 WEBサイトはhttp://toremoro21.world.coocan.jp/ Twitterは@toremoro21です。 □はじめに P2Pで注目されている技術として分散ハッシュテーブル（ＤＨＴ）が挙げられますが、仕組みが複雑なこともあって、理解するのはなかなか大変です。またOverlay WeaverのようなDHTシュミレーターをインストールするのも、ちょっと面倒。。という人も多いと思われます。 そこで、ブラウザだけでＤＨＴを体感できる２つのサイトをご紹介したいと思います。 なお、ＤＨＴって何？と思った方は拙著のＤＨＴ入門を見て頂くことをお勧めします。 分散ハッシュテーブル入門～その１（初心者向け） Ｐ２Ｐと分散ハッシュテーブル～その１（ネットワークについてある程度ご存知の方向け） □Ｆｌ
[P2P]DHTにおける部分一致検索の間接参照による解決法の提案 - Tomo’s HotLine
IT技術を中心に、暮らしに役立つ情報からクラシック音楽の解説まで気軽に情報発信しています。 WEBサイトはhttp://toremoro21.world.coocan.jp/ Twitterは@toremoro21です。 ２００７年ももう少しで終わりですね。今年は娘の誕生、P2P教科書の出版、総務省支援のP2P実証実験への技術検討メンバ参加など、プライベート・仕事ともに節目の年でした。 来年もP2Pに関する講演等が決まりつつあるので後ほど紹介致します。 さて、２月末にとある団体が主催によるP2P研究会にて講演を行う予定です。その中でDynamoなどのP2Pデータベースの話も触れたいので、少しずつネタをBlogに書いておこうと思います。仕事でP2Pに関する業務が正式に認められましたが、アイデアベースで出せるものは今後もBlogで公開したいと思いますので皆様のコメントを是非お寄せ下さい。 □部
Tomo’s HotLine: [P2P][DHT]Pastry入門〜その１
IT技術を中心に、暮らしに役立つ情報からクラシック音楽の解説まで気軽に情報発信しています。 WEBサイトはhttp://toremoro21.world.coocan.jp/ Twitterは@toremoro21です。 今回から数回に渡りＤＨＴでとても有名な方法である「Pastry」について紹介します。 なるべく分かりやすく書くために、部分的には不適切な記述があるかもしれません。そのため、詳細については原論文を見ると良いでしょう。 原論文 Pastry:Scalable,decentralized lbject location and routing for large-scale peer-to-peer systems http://research.microsoft.com/~antr/PAST/pastry.pdf Pastryと何か？ PastryはChordやKademl
Overlay Weaver: An Overlay Construction Toolkit
Overlay Weaver はオーバレイ構築ツールキットです。 アプリケーション開発に加えて、 オーバレイのアルゴリズム設計もサポートします。 アプリケーション開発者に対しては、 分散ハッシュ表 (DHT) やマルチキャストといった高レベルサービスに対する 共通 API を提供します。 この API を用いることで、 特定のトランスポートプロトコル、データベース、ルーティングアルゴリズム に依存しないアプリケーションを開発できます。 Overlay Weaver は、 ルーティングアルゴリズムとして Chord、Kademlia、Koorde、Pastry、Tapestry、FRT-Chord の実装を提供しています。 ルーティング層の分割によって、 これらのアルゴリズムをたかだか数百ステップで実装することが可能となりました。 ルーティング層は高レベルサービスの下位に位置し、 ルーティン
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://planetlab0.otemachi.wide.ad.jp:3998/