トップページ
ご挨拶
入会案内
支部規程
役員
電気・情報関連学会
リンク
イベント
事務局

講演会 「Low-Congestion Distributed Algorithms」

日 時

 4月10日(木)15:00−16:00(60分)(予定)

場 所 広島大学工学部A1-633(東広島市鏡山1-4-1)
(変更の可能性あり.参加希望者に連絡させていただきます.)
講 師

Boaz Patt-Shamir, Tel Aviv University

概 要 The traditional model for computing over a communication network
(called LOCAL) allows sending a message of arbitrary size in a single
time step. This way, the time complexity is a measure of the locality
of algorithms: saying that an algorithm runs in time T is equivalent,
under the LOCAL model, to saying that the problem can be solved if
each node learns all information the nodes which are reachable within
T hops.  Therefore, in this model any problem can be solved in time
linear in the network diameter.
While work on the LOCAL model has produced many interesting results,
it is widely accepted that this model does not capture the true
complexity of distributed computing: it is mainly useful in
understanding what cannot be done distributively, i.e., lower
bounds. A better approximation of reality is the CONGEST model, where
a link can carry only a bounded number of bits in a time
step. Usually, it is assumed that message size is O(log n) bits, so
that each message can carry a constant number of reasonably-sized
pieces of information, such as node identifiers, or values of
polynomial magnitude.  It turns out that in this model, many problems
cannot be solved in o(sqrt(n)) time, even in networks of diameter,
say, O(log n) hops. On the other hand, letting D denote the network
diameter in hops, there are some problems in which the O(D+sqrt(n))
time upper bound is nearly achievable in the CONGEST model (to within
a polylogarithmic factor).
In this talk we review some known results in the CONGEST model, as
well as some new progress directions. In particular, we will consider
the tasks of constructing routing tables, the task of finding a
Steiner forest, and the extreme case of a completely connected network
(a clique).
※講演会はすべて英語で行われます。
『講演会内容』
分散アルゴリズムというのはこれまで任意のサイズのメッセージが一度に
送れるものと仮定して考えられてきました.
そのような仮定のものとでは,計算時間複雑度はどれだけ遠くにメッセージを
伝播するかということと等価になります.
しかしこれは実際のネットワークの状況をうまくモデル化できているとはいえません.
そこで,各リンクで単位時間で送れるビット数を制限したCONGESTモデルを考えます.
この新しいモデルにおける既知の結果と新しい方向性についてお話します.
参加料

無料

事前の
参加申込

要  人数確認のためご希望の方は下記にメールにてご連絡ください.

主 催 電子情報通信学会中国支部
共 催 電気学会・映像情報メディア学会・情報処理学会・電気設備学会 各中国支部
問合せ先 広島大学大学院工学研究院 亀井 清華
Tel. 082-424-7685  Fax. 082-422-7195
E-mail: s-kamei[at]se.hiroshima-u.ac.jp