【概 要】 |
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 quivalent, 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モデルを考えます．
この新しいモデルにおける既知の結果と新しい方向性についてお話します． |
