A Distributed Algorithm for Generation of MST

IPSJ

Bibliographic Information

Other Title
  • 分散アルゴリズムを用いたMSTの構成法について

Search this article

Description

ローカルネットワークや広域ネットワークが整備されるに従い、分散環境下で実行される並列計算が重要になりつつある。これにともない分散環境下でプロセスを効果的に協調動作させる分散アルゴリズムの研究が盛んに行なわれている。分散システムにおいては、各計算機の局所的なデータだけで処理できる作業は、他の計算機と独立に実行できるので、処理効率が向上する。しかしメッセージの送受信が頻繁に行なわれるような分散アルゴリズムでは、メッセージ遅延や同期などのために逆に処理効率が落ちる場合も少なくない。これまで、様々な問題に対して多くの分散アルゴリズムが提案されているが、本稿ではそれらの中で、最小生成木(MST)の構成問題を非同期システム上で解く分散アルゴリズムを取り上げ、これを超並列計算機SR-2001上に実装する方法について述べる。

Journal

Details 詳細情報について

Report a problem

Back to top