O(n^2)のメッセージ数がかかるアルゴリズムを紹介した。以下では、O(n log n) のアルゴリズムを紹介する。基本的なアイデアを示す。双方向リング上で考える。 ばつ印は、除外プロセスとする。それ以外は、始動プロセス。隣接したプロセス同士でプロセッサ番…

分散アルゴリズムでは、情報を１つの特別なプロセスに集めることで問題を解くことができる。しかし、そのような特別なプロセスを事前に決定してしまうと問題があることを説明した。したがって、そのような特別なプロセスを１つ作り出す問題、リーダー選挙問…

分散アルゴリズムでは、 各プロセスは、一意のプロセッサ番号を持つ。 各プロセスは、待機プロセスと始動プロセスに分けられる。最初、全てのプロセスは待機状態にあり任意の時刻に始動状態になることができる。 受け取ったメッセージは、受信レジスタに保存…

今度の発表のために、資料の内容を簡潔にまとめておく。 参考アルゴリズム・サイエンス:出口からの超入門 (アルゴリズム・サイエンスシリーズ―超入門編) 近年、ネットワーク網の発達や計算機が安価になるなど、複数の計算機を用い、ネットワークを通じて協調…