Grid/P2Pプログラミング
モデルと関連技術
東京大学 情報理工学系研究科
田浦健次朗
P2P


よく知られている起源: Napsterファイル共有
 ユーザ間の勝手な音楽ファイル転送を手助け
 手助け(持ち主の検索のためのディレクトリ作成)はサーバ,
転送はユーザ間で
その後
 多数のファイル共有(Gnutella, Kazaa, WinMX, Winny, …)
 同時配信のためのP2Pネットワーク(BitTorrent)
 構造的P2Pネットワーク(Chord, Pastry, Tapestry, CAN, …)
2005年9月12日
PPLサマースクール
P2Pのインパクト


社会的インパクト(省略)
もう少し技術的なインパクト
 初めて多くの人が,非常に多数の計算機の協調によって,
実質的にサービスの質・容量が向上しているのを見た
 強力なサーバ << 多数のPC
 サービス = 大きなコンテンツの多数への配信


ファイル共有 : キャッシュ
BitTorrent : 同時配信
2005年9月12日
PPLサマースクール
Grid


起源となるアイデア: メタコンピューティング
 遠隔にある複数の資源を統合した計算
期待をこめた見方
 世界中の計算資源の効率的な流通(融通)



必要な時に,必要な人の下へ計算資源を即座に提供する基盤
Where is 計算資源?
 専門の会社, ユーザの遊休PC, etc.
 cf. Sun utility computing, [email protected], [email protected], …
電力網(Power Grid)と同じくらい普遍的に,誰でも利用可能
な「計算網」(Computational Grid)
2005年9月12日
PPLサマースクール
[email protected]

ユーザの遊休PCを計算資源とした並列計算
 Volunteer計算, インターネット計算
2005年9月12日
http://www.boincsynergy.com/
PPLサマースクール
[email protected]


印象的なクライアント数
 [email protected] 39万 (2005年8月)
ここでも:
 初めて,多くの人が,非常に多数の計算機の協調によっ
て,実質的にサービスの質・容量が向上しているのを見た
 スーパーコンピュータ << 多数のPC
 サービス = 科学を助ける計算
2005年9月12日
PPLサマースクール
P2P/Grid vs. 伝統的並列処理



非常に多数の計算機(インターネット上のPC)の協調によって,
実質的にサービスの質・容量が向上している …
 それって大昔からある「並列処理」では?
 それもきわめて限定された,単純な応用(ブロードキャスト,
CPU-only計算)の…
半分は真実
 Broadcastのテクニックはよく知られている(MPIライブラリ)
 科学技術計算の高度な並列処理は多数行われてきた
But, これまでの多くの並列処理とプラットフォームの仮定が
根本的に異なる
2005年9月12日
PPLサマースクール
伝統的並列処理 vs P2P/Grid:
プラットフォームに関する仮定の違い
伝統的並列処理
P2P/Grid
計算資源
開始から終了まで固定 動的に変化(参加,脱退)
故障
なし
ネットワーク 一様に高速
2005年9月12日
備えが必須
多様,場所により低速,動的に変化
PPLサマースクール
課題と共通ゴール
並列
環境固定, 性能一様, 故障なし, などの
前提からの脱却
共通ゴール「分散環境での
一般的な並列処理」
動的な変化, 故障, ネット
ワーク性能の多様性, スケー
ル
P2P
beyond ブロードキャスト
(e.g., 検索)
Volunteer Computing
beyond CPU-only型の応用
(e.g., データ集約的応用)
2005年9月12日
PPLサマースクール
共通鍵技術:
オーバーレイネットワーク



参加計算機間で,一部の(TCP)接続を作り,維持する
この接続でできたグラフ上をメッセージが流れる
通信アブストラクションの提供.e.g.
 マルチキャスト
 1-1通信
2005年9月12日
PPLサマースクール
なぜオーバーレイネットワークが重
要か?

なぜ下位の通信レイヤで直接接続・通信しないのか?
 直接接続が可能とは限らない(Firewall/NAT)
 N-Nの直接接続は資源を圧迫し,無駄に使う


N-Nの接続は変更の際に維持するコストが大きい


ファイルディスクリプタ,ポート,TCPの再送Window
cf. クライアントサーバ
トラフィック量(ホップ数)  許容台数,資源消費
??
2005年9月12日
PPLサマースクール
本チュートリアルの中心課題



並列プログラミングのための「オーバーレイネットワークの構
築とそれを利用した通信の実現方法」
 資源消費(接続数)
 ノードや接続の増減に伴う更新コスト
 ルーティング性能(ホップ数)
既存提案,興味深い理論,理論的な限界などの紹介
これらは,分散環境(資源の動的増減,ネットワーク性能の
多様性,故障,etc.)での並列処理の基盤となる(はず)
2005年9月12日
PPLサマースクール
Roadmap



Part I: 並列・分散プログラミングモデルの実例
 メッセージパッシング,共有メモリ,RPC/RMI, タプルス
ペース
 大規模,分散,故障のある,動的な環境での課題
Part II: 構造的P2PとDHTの枠組み
Part III: Advanced Topics
 任意の重みつきグラフに対するCompactルーティング
 構造がないグラフ上の効率的ルーティング
2005年9月12日
PPLサマースクール
Part I:
並列・分散プログラミングモデルの実例



メッセージパッシング
共有メモリ
タプルスペース
2005年9月12日
PPLサマースクール
Grid (分散)環境での並列処理の
現状




「並列プログラミングなし」という実用的解
 逐次プログラム+バッチスケジューラ(SGE, Condor, etc.)
 並列シェル(GXP, pdsh, dsh, etc.)
伝統的並列プログラミングモデルの利用
 メッセージパッシング(MPI, PVM, etc.)
 分散共有メモリはほとんど使われない
伝統的分散プログラミングモデルの利用
 RMI, RPC, ソケット
 タプルスペース (JavaSpace, TSpace, etc.)
分散環境に適した並列プログラミングモデル
 Phoenix
 マスターワーカモデル
2005年9月12日
PPLサマースクール
課題


伝統的並列プログラミングの課題
 分散環境で当然の故障,動的な資源増減下でのプログラミ
ングを支援していない
 ネットワークの制限(Firewall/NAT)下でしばしば動作しない
伝統的分散プログラミングの課題
 多くは1-1のみの通信をサポートしているのみで,「多数のプ
ロセスの協調」を直接支援していない
2005年9月12日
PPLサマースクール
メッセージパッシング



実例 MPI, PVM
基本アイデア:
 各参加プロセスに固定された名前(e.g., 0, 1, 2, …)をつける
 プロセス名を指定した通信(メッセージ送信)
基本API
p
 send(p, msg) /* プロセスpにメッセージを送る */
 msg = recv() /* メッセージを受け取る */
 集団通信(broadcast, reduction, etc.)
2005年9月12日
PPLサマースクール
メッセージパッシング:単純な実装
のモデル


各プロセスが「APIレベルのプロセス名  下位通信レイヤに
おける名前」の対応を保持
 プロセスの増減がなければ起動時に定まり,不変
send(p, msg)  下位通信レイヤの送信プリミティブを起動
下位通信レイヤの接続
2005年9月12日
PPLサマースクール
メッセージパッシング:分析
 固定した多数のプロセス集合による計算の素直なモデル
 全プロセス間で接続が許可されていれば, 1,000プロセス程
度まではN-N接続可能(ボトルネックのない実装が容易)
 効率的な集合通信(特にbroadcast)の支援が容易
 プロセスが動的に増減する場合,プログラミングの複雑度が
非常に増す
 参加中のプロセス名の管理
 プロセス  データのマッピングの管理
2005年9月12日
PPLサマースクール
共有メモリ



実例: 共有メモリ計算機,分散共有メモリ(仮想共有メモリ)
基本アイデア:
 通信にはプロセス名を用いず,別の名前空間(アドレス空
間: 通常プロセス数よりずっと大きい)を用いる
 プロセス間の通信は複数プロセスが同じアドレスにアクセ
スすることで(間接的に)行われる
基本API:
 WRITE(a, v)
 READ(a)
a
2005年9月12日
PPLサマースクール
共有メモリ: 単純な実装のモデル



キャッシュ(複製)なし
アドレス空間を分割担当.各プロセスが,「アドレス  担当す
るプロセス名」の対応を保持
read(a)/write(a, v)  aを担当するプロセスへのメッセージ送信
read(a)
a
2005年9月12日
PPLサマースクール
共有メモリ: 分析
 通信にプロセス名を用いないため,プロセスの増減下でのプ
ログラミングモデルとして好ましい
 通信の効率が悪い(ほぼ常に2ホップ)
 ブロードキャストプリミティブの不在
 1-1をN回繰り返すことになる
2005年9月12日
PPLサマースクール
タプルスペース



実例: Linda, JavaSpace
基本アイデア:
 共有メモリに類似した空間「タプル空間」にタプルを出し入
れすることで通信
基本API
 out(value)
in(int, int)
 value = in(template), value = rd(template)
out(3, 5)
2005年9月12日
PPLサマースクール
(3, 5)
タプルスペース: 実装のモデル


タプルサーバを配置
 全ての成立していない通信を格納する.i.e.
 outされたが,マッチするinが発行されていないタプル
 inされたが,マッチするoutが発行されていないタプル
in/out  タプルサーバとの通信
in/out
2005年9月12日
PPLサマースクール
タプルサーバ
(1,”hello”)
(string,int)
(2,”bye”)
(string, string”)
(5,”hello”)
(3, *)
(”bye”, 10, 12)
(”bye”, string, int)
タプルスペース: 分析
 共有メモリの利点/欠点を多くの大部分継承する
 タプルサーバがボトルネックにならない実装は難しい
 通信の粒度の通信が可能(メッセージのサイズが任意)
 メッセージパッシングの利点を踏襲
2005年9月12日
PPLサマースクール
Part I: まとめ(1)

多かれ少なかれ,モデルを実装するとは
プログラミングモデルレベルの通信
 下位通信レイヤにおける通信(主にTCP接続を用いた通信)
のマッピングを行うことである
 1-1メッセージのルーティング,マルチキャスト
通信のアブス
トラクション
下位レイヤの通信
2005年9月12日
PPLサマースクール
Part I: まとめ(2)

下位通信レイヤへのマッピングの方法は様々であり,トレー
ドオフが存在する
 OSの資源制約内でサポートできる台数
 通信の性能(ホップ数など)
 ボトルネックの有無
 動的な更新のコスト
2005年9月12日
PPLサマースクール
Part II: 構造的P2PとDHT

基本アイデア: 参加ノードで協調的に,規則的に,オーバー
レイネットワークを構築
 不規則なネットワークでは困難な,1-1通信を効率的に実
現
 以下の3点の“good balancing point”




トラフィック量(ホップ数)
消費資源(維持すべき接続数)
参加・脱退時の更新コスト
提供する通信のアブストラクション
 分散ハッシュ表(DHT)
2005年9月12日
PPLサマースクール
DHT


Chord [SIGCOMM 2001]を例として説明する
同時期に発表された類似システム
 Pastry [Middleware 2001]
 Tapestry [Berkeley Technical Report 2000]
 CAN [SIGCOMM 2001]
2005年9月12日
PPLサマースクール
構造的P2P: 動機

初期のP2Pシステム
 同一コンテンツの大量配信(ブロードキャスト)に威力
 検索には洗練されていない方法を用いていた


単一サーバ,flooding
技術的言い換え
 ブロードキャストは無秩序なオーバーレイネットワークで十
分効率よく実行可能
 1-1メッセージのルーティングは非効率的
2005年9月12日
PPLサマースクール
DHT (Distributed Hash Table)


構造的P2Pが提供しているアブストラクション(問題設定)
 put(key, value)
 value = get(key)
 keyは大きな整数の区間(e.g., [0, 2160))の要素
本質的には共有メモリと同じ
 注: 厳密な共有メモリの意味論(consistency)を実装するの
はもっと複雑
a
2005年9月12日
PPLサマースクール
鍵空間
Chord (1)



鍵空間[0, 2m) modulo 2m (m : たとえば160)
 Chord ring, Chord circleなどと呼ばれる
参加中のプロセスがこの空間を分割して
担当する
 1プロセスは一つの区間(a, b] modulo
2mを担当
 bをそのプロセスのidと呼ぶ
実装の鍵となる要素: ルーティング
 与えられたkeyを担当するプロセスへ
メッセージを配達する
2005年9月12日
PPLサマースクール
a
あるプロセ
スの担当範
囲
key
b
Chord ring
Chord (2)

各プロセスは以下のプロセスへの接続を持つ
 Chord ring上の両隣(predecessor, successor)
 Finger table : 自分のid = bとして,






b + 2m – 1
b + 2m – 2
…
b + 21
を担当するプロセス(最大でm個.プロセスidが均等分布していれ
ば約log N個)
2m ノードのHypercubeネットワークを(ノードの集合を1ノードに
縮約することにより)Nプロセスで模倣したものに近い
2005年9月12日
PPLサマースクール
Chord ルーティング


問題 key kを担当するプロセスにメッセージを届ける
if (k が自分の担当) {
自分へ配達;
} else {
Finger tableからkを越えない最大のentry iを取り出す; /* k < b + 2i */
メッセージを対応するプロセス(pi)へ転送
}
m–1
b + 2m – 1
pm – 1
m–2
b + 2m – 2
pm – 2
…
…
…
1
b + 21
p1
k
2005年9月12日
PPLサマースクール
Chordルーティング



ホップ数 < m, プロセスidほぼ均等ならばO(log N)
ノードの参加・脱退時のコスト
 O(log2 N)個のメッセージ(接続の追加,変更)
いずれもHypercubeの性質(ノード当たりlog Nリンク, diameter
log N)と比べると理解しやすい
2005年9月12日
PPLサマースクール
注


Chordおよび多くのDHTの提案は, 世の中で使われている
“ファイル共有アプリケーション” と異なり,各ノードが望む
ノードと接続を作ることができると仮定している
 実用的には, “No firewall/NAT”を仮定
 抽象的には,「完全グラフのspanner」を設計している
 伝統的ネットワークトポロジーの模倣が常に可能
より現実に即した,発展形の問題
 任意のグラフのspannerをオーバーレイネットワークとする
 重みつきグラフの元でのホップ数拡大係数
2005年9月12日
PPLサマースクール
Part III: Advanced Topics


任意の重みつきグラフに対するCompactルーティング
構造がないグラフ上の効率的なルーティング
2005年9月12日
PPLサマースクール
ルーティング: 問題設定



G = V, E  : 重み付きグラフが与えられる
 V : プロセスの集合, E : 通信路の集合
 辺の重み: その辺を通るコスト(遅延)
タスク: パケットのソース s とあて先 t を与
えられ,それを低いコストで届ける
 コスト: 通った辺の重みの和
任意の重み付きグラフを考えることで,現
実の分散環境を反映したモデルとなる
3
2
6
2
5
3
4
s
PPLサマースクール
3
1
2
2005年9月12日
t
1
1
ルーティングの基本方式(最短路)


基本アイデア: 全対全の最短路を計算する
各ノードは,他の各ノードへの最短路に沿った次ホップを蓄
えた表(経路表/ルーティング表)を保持
 記憶領域: N log N
プロセス
次ホップ
0
3
 ルーティングの品質: 最適
22
1
2
3
22
9
35
N–2
N–1
22
3
3
10
9
35
2005年9月12日
PPLサマースクール
Topic 1: コンパクトルーティング



Nプロセスに対し,各プロセスがsubblinear (o(N))の記憶領域
を用いるルーティング方式をコンパクトルーティングという
 当然コンパクトルーティングは最適でないルーティング(回
り道)をする可能性がある
あるルーティング方式のstretch (伸び率)
= [ そのルーティングによるコスト / 最短路のコスト ]
の,全プロセス対にわたる最悪値
目標 : stretchを抑えたコンパクトルーティング
2005年9月12日
PPLサマースクール
Taxonomy : Name Independence


トポロジ非依存名((topology) independent names)
 ルーティング関数に与えられるあて先(アドレス)は,あらか
じめ決められたノード名(e.g., 0, 1, …, n – 1)
トポロジ依存名 ((topology) dependent names)
 ルーティング関数に与えられるあて先(アドレス)は,ルー
ティング方式が決めてよい



2005年9月12日
ルーティングに関する情報を,アドレスに「埋め込む」ことを許す
極端な方法: グラフ全体の情報がアドレスに埋め込まれている
 サイズ0のルーティング表
制約: アドレス長さ = log nの多項式
PPLサマースクール
例

重み一様な完全グラフに関するルーティングを考える
常にマスタ(ルーティングセンター)を経由
stretch = 2
トポロジ非依存名  コンパクトにできない
トポロジ依存名  コンパクトにできる
(e.g., マスタ以外各ノードのアドレス=マスタ側ポート番号とする)
2005年9月12日
PPLサマースクール
知られている結果




(トポロジ依存名) Stretch 3 コンパクトルーティング
 Cowen SODA 1999, “Compact routing with Minimum
Stretch”
トポロジ非依存名 Stretch 3 コンパクトルーティング
 Abraham et al. SPAA 2004, “Compact name-independent
routing with minimum stretch”
Stretch 3は「最適」なコンパクトルーティング
 全ノードo(n)の記憶域でstretch < 3は達成不可能
 Gavoille et al. SIROCCO 1997, “Space Efficiency of
routing schemes of stretch factor three”
以降はCowenの方法の基本アイデアを紹介する
2005年9月12日
PPLサマースクール
CowenのStretch 3 Compact
Routing


仮定
 G = V, E. 重みつき無向グラフ. nノード.
 トポロジ依存名: i.e. ノードのアドレス(あて先)は事前に付
け替えてよい(制約: アドレスはO(log n) bits)
結果
 任意のグラフに対し,Stretch 3 (最短路の3倍以下)でルー
ティング
 ルーティング表サイズ O(n2/3 log4/3 n)
2005年9月12日
PPLサマースクール
基本アイデア

準備:
 少数の「目印(Landmark)」ノードを決める

ただし,どのノードも最低一つの目印を近くに持つように
各ノードuに対し「uの近くのノード」と,全目印への最短路
を計算.uに,それら(のみ)への次ホップを保持
ルーティング (s to t):
 case 1: tがsの近く  最短路
 case 2: そうでない  tに最寄の目印を目指す
: 目印


: あて先(t)
: 送信元(s)
case 1
2005年9月12日
case 2
PPLサマースクール
ポイント

なぜ経路表を小さくできるか?
 近くのノードと,目印へのエントリしか持たない



必要な目印の数を抑えられればよい
なぜstretch 3か?
 後述
微妙なところ:
 あて先ノードに最寄の目印をどう知るか?
 目印ノードの経路表の大きさは?
 答: アドレスに情報を含めておく

2005年9月12日
トポロジ依存名の活用
PPLサマースクール
実際の道
最短路
アルゴリズム: 全体構造



前処理 : 以下を計算
 目印の集合 L
 各ノード u に対するトポロジ依存名(3つ組)
= u, u に最寄の目印 lu, lu から u への最短路上の次ホップ
経路表構築 : 各ノード u は,以下のノードらにする最短路を計算し,それ
に沿った次ホップを経路表に登録
 u に近いノード
 全目印 L
ルーティング (s  t):
 自分に近いノードへは最短路
 それ以外は,tに最寄の目印を経由
2005年9月12日
PPLサマースクール
目印の選択


要件1: どのノード u も自分の近く (B(u)) に一つ目印を持つ
 ある程度遠いノード間では目印を経由しても,ひどい回り
道にならない
要件2: 目印の数が少ない
 全目印へ最短経路を記憶しても表サイズがnにならない
2005年9月12日
PPLサマースクール
前処理

for u  V {
B(u) = uから近いn個のノード
/*  < 1 : 定数.同距離はノード名で順序付け */
R(u) = { y | u  B(y) } /* uを近くに持つノード */
}
C = { u | |R(u)| > n(1+ )/2 }
D = GREEDY_COVER(V, { B(u) }u  V )
L = C  D /* 目印 */
for u  V {
lu = uに最も近い目印
n = luからuへ最短路上の次hop
address(u) = u, lu, n
}
2005年9月12日
PPLサマースクール
GREEDY_COVER


GREEDY_COVER(P, S)
input: S : 集合, P : Sの,「大きさkの部分集合」の集合
output: Pを覆うSの部分集合T.
i.e. T  S s.t. XP tX
T = {} /*
for each step
t = 新たに覆われる集合が最も増える要素
T=T+{t}
return T
事実: Pの各要素の大きさがkのとき
Tの要素数は O(|S|/k log n)
2005年9月12日
PPLサマースクール
経路表構築

for v  V: /* 自分の近傍へのエントリ */
for u  B(v) s.t. v  uの最短路上に目印が存在しない
uの表にvへのエントリ(最短路上の次hop)を追加
for l  L: /* 目印へのエントリ */
for u  V:
uの表にlへのエントリ(最短路上の次hop)を追加
B(v)
vへの最短路を保持するノード
v
2005年9月12日
PPLサマースクール
ルーティング

あて先 address(t) = t, lt, n by s :
 s = lt  nへ転送
 tが経路表にある  経路表を見て次hopへ転送
 otherwise  経路表を見てltへの次hopへ転送
2005年9月12日
PPLサマースクール
なぜコンパクトか?


目印Lの作り方再掲:
C = { u | | R(u) | > n(1+ )/2 }
D = GREEDY_COVER(V, { B(u) }u  V )
L = C  D /* 目印 */
よって,
 | C |  n(1+ )/2 (  | R(u) | =  | B(v) | = n(1+ ))
 | D |  n / n log n = n1–  log n
  | L |  n(1+ )/2 + n1–  log n
2005年9月12日
PPLサマースクール
なぜstretch 3か?
s  lt  t の場合だけが問題
1. b  a (sはtへの最短路を持っていない)
2. c  a + b (cは s  lt の最短路)
 b + c  2a + b  3a

lt
b
c
a
s
最短路
2005年9月12日
PPLサマースクール
t
Topic 2: 構造のないグラフ上の効
率的ルーティング


我々の文脈における動機
 維持にほとんどコストのかからないオーバーレイネット
ワークが構築可能か?
Kleinberg [STOC 2000] “The Small-World Phenomenon: An
Algorithmic Perspective”
2005年9月12日
PPLサマースクール
Milgramの実験


目標: あて先(住所と名前)のついた手紙を渡され,あて先の人
へ手紙を届ける
 渡された人は自分の知人の誰かに手紙を渡すことができる
実験結果: アメリカ人は6 hopでつながっている
 ランダムなグラフの直径が小さいことを示していると解釈で
きる
2005年9月12日
PPLサマースクール
Kleinbergの問題意識

「グラフの直径が小さい」からと言って,
「グラフ全体に関する知識なしに目的地までの短いパスが見
つかる」とは限らない
 i.e. 効率的な(ホップ数の少ない)ルーティングが可能とは
限らない

効率的  log N の多項式ホップ数でルーティング可能
アメリカ人全体で「ルーティング表」があるわけではない…
これを可能にするようなグラフの性質とはどんなものか?


2005年9月12日
PPLサマースクール
モデル




長距離辺
n  n 格子点上にノード
辺(知人)
 隣への「短距離辺」
 ある確率で選ばれた1つの「長距
離辺」
ノード間の「距離」
 d(P, Q) = | xP – xQ | + | yP – yQ |
ルーティングアルゴリズム
 あて先へ最も距離が近い知人へ
転送
2005年9月12日
PPLサマースクール
長距離辺の選び方



rをある定数(0  r < )として,
辺(u, v)が選ばれる確率  d(u, v)–r
とする
r   : 短い辺に偏って選ぶことになる
r = 0 : 一様な確率で選ぶことになる
2005年9月12日
PPLサマースクール
結果
1. r = 2 のとき: 先のルーティングは平均O(log2 n)ホップ
2. それ以外のとき: どんなdecentralizedルーティングアルゴリズ
ムも(n2/3)かかる


注: k次元格子点の場合,上記の結果は“r = kのとき”となる
以降では,一つ目の結果の証明と直感的説明を行う
 易しくするためにk = 1として証明する
2005年9月12日
PPLサマースクール
直感

r 大 : 長距離辺が少なくなるので時間がかかりそう
 より詳しくは,「目的地の遠くでさまよう」
…

r 小 : 目的地の近傍を端点とする長距離辺が「十分な密度
で」存在しない
 目的地へだいぶ近づいてから長距離辺が使えなくなる
…
2005年9月12日
PPLサマースクール
もう少し定量的な直感



あて先から距離 d (L  d < 2L)の点から,次ホップで距離L以
内に突入する辺の存在確率は?
大雑把に言って
 L–r  (の面積) = Lk–r
解釈
 k < r : 大きなLに対して小さい
 k > r : 小さなLに対して小さい
L
L
2005年9月12日
PPLサマースクール
k = 1の場合の証明(1)


目的地から距離 [2j, 2j+1)にいる間をphase jと呼ぶ
(0  j  log n)
パケットの現在地をuとして,ここでphase jが終了する確率を
評価する
2j
u
2005年9月12日
PPLサマースクール
2j
k = 1の場合の証明(2)

uからある特定のv (あて先までの距離 2j)へ長距離辺が伸びている
確率p1
1
j 1
d (u, v) 1
1
2
p1 
 n1  j  2
1
2 2 lg n
d (u, p)


p u
i 1 i

uからどれかの,あて先までの距離 2jのノードへ長距離辺が伸びて
いる確率p2
1
p2  p1  2 
4 lg n
j
2005年9月12日
PPLサマースクール
k = 1の場合の証明(3)


phase jの長さの期待値  1 / p2 = 4 lg n
目的地到達までの長さの期待値 4 log n lg n  O(log2 n)
2005年9月12日
PPLサマースクール
参考 k = 0 の場合は?


p1 = 1 / n (一様)
j
p2 = 2 / n
2005年9月12日
PPLサマースクール
まとめに変えて


目標 : 以下の条件での効率的な通信(1-1のルーティング, 集
合通信)
 多数(> 数千)のノード
 実行時に変化する
 場所によって性能が多様
恩恵を受ける(はずの)システム
 並列ミドルウェア(メッセージパッシング,etc.)
 スケーラブルサービス(モニタリングシステム,ファイルシ
ステム,資源管理システム,etc.)
 新P2Pアプリケーション
2005年9月12日
PPLサマースクール
2005年9月12日
PPLサマースクール
ダウンロード

N - 東京大学