確率的な通信時間を持つネットワーク上でのブロードキャスト時間計算
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,計算機ネットワークでブロードキャストにかかる時間を計算することを考える.ただし,どの通信路を通して通信を行う場合にもランダムな時間 (通信時間) がかかるものと考える.本稿では各通信路の通信時間を互いに独立な確率変数と考え,確率変数であるブロードキャスト時間も確率変数の確率分布を求める.この問題と類似の問題が #P -完全に属するため,この問題も厳密に解決することが困難であることが予想される.このため,本稿ではブロードキャスト時間の確率分布関数 FB(x) を,ある与えられた w > 0 よりも小さい x について ? 以下の誤差で近似する多項式を求める.本稿では最初に環状のネットワークにおけるブロードキャスト時間分布を求めるアルゴリズムを示す.その後,cactus 構造で一つの閉路のサイズが定数 b 以下であるようなネットワークにおけるブロードキャスト時間分布を求めるアルゴリズムを示す.アルゴリズムの計算時間は分布関数の引数 x の上界 w,ネットワークサイズ n,最大許容誤差 ?について多項式である.
- 2010-09-15
著者
-
Ei Ando
Faculty of Computer and Information Science, Sojo University
-
Joseph Peters
School of Computing Science, Simon Fraser University
-
Ei Ando
Faculty Of Computer And Information Science Sojo University
-
Joseph Peters
School Of Computing Science Simon Fraser University