☆分散アルゴリズム特論（Distributed Algorithms）[4103]

＜授業のねらい及び具体的な到達目標＞

分散システムおよびネットワークシステムにおいて効率的な処理・耐故障処理を実現するためのアルゴリズム理論を学ぶ。
分散システムの基礎アルゴリズムについて学ぶとともに、最新の研究成果についても輪講形式で学ぶ。

＜授業計画及び準備学習＞

１　分散システムとは
　　　分散システムが使われるようになってきた歴史的経緯について解説する。
　　　準備学習：教科書１．１−１．４を読んでおく。
　２　分散システム構築上の課題、時刻
　　　分散システム構築上の問題点について解説する。
　　　準備学習：教科書１．５ー２．１を読んでおく。
　３　論理時計
　　　分散システムにおける論理時計の概念について解説する。
　　　準備学習：教科書２．２ー２．３を読んでおく。
　４　分散スナップショット
　　　分散システムにおける全域状態を得るアルゴリズムについて解説する。
　　　準備学習：教科書第３章を読んでおく。
　５　リーダ選挙問題
　　　システム内で唯一のリーダを選ぶアルゴリズムについて解説する。
　　　準備学習：教科書第４章を読んでおく。
　６　分散相互排除問題
　　　複数のプロセスからの要求のうち１つだけをかなえる相互排除問題を解くアルゴリズムについて解説する。
　　　準備学習：教科書第５章を読んでおく。
　７　放送型通信アルゴリズム
　　　複数のプロセスに同一の順序でメッセージを受信させるためのアルゴリズムについて解説する。　
　　　準備学習：教科書第６章を読んでおく。
　８　合意問題
　　　複数のプロセスが同一の値に合意するためのアルゴリズムについて解説する。
　　　準備学習：教科書７．１−７．２を読んでおく。
　９　ビザンチン合意問題
　　　ビザンチン故障の概念とビザンチン故障が存在する場合の合意アルゴリズムについて解説する。
　　　準備学習：教科書７．３−７．４を読んでおく。
１０　自己安定アルゴリズム
　　　準備学習：教科書第８章を読んでおく。
１１　トピックス：スケジューリング問題
　　　分散システムのスケジューリング問題に関する最新の研究成果に関して輪講発表を行う。
　　　準備学習：国際会議ICDCS予稿集の該当部分を読んでおく。
１２　トピックス：合意問題
　　　分散システムの合意問題に関する最新の研究成果に関して輪講発表を行う。
　　　準備学習：国際会議ICDCS予稿集の該当部分を読んでおく。
１３　トピックス：耐故障アルゴリズム
　　　分散システムの耐故障アルゴリズムに関する最新の研究成果に関して輪講発表を行う。
　　　準備学習：国際会議ICDCS予稿集の該当部分を読んでおく。
１４　トピックス：データ一貫性問題　　　
　　　分散システムのデータ一貫性問題に関する最新の研究成果に関して輪講発表を行う。
　　　準備学習：国際会議ICDCS予稿集の該当部分を読んでおく。

＜成績評価方法及び水準＞

輪講発表の内容に対する評価で行う。
１００点満点で評価し、６０点以上を合格とする。

＜教科書＞

真鍋義文著　「分散処理システム」　森北出版

＜参考書＞

増澤利光、山下雅史著　「適応的分散アルゴリズム」　共立出版

＜オフィスアワー＞

木曜２限、A-1572研究室で行う。
これ以外の時間を希望する者はメールでjt13455@ns.kogakuin.ac.jpでアポイントメントを取ること。

＜学生へのメッセージ＞

インターネットやクラウドコンピューティングを支えるアルゴリズムが分散アルゴリズムです。今までにないすぐれた分散アルゴリズムが考案されれば、それは世界中で使われる可能性があります。皆さんのチャレンジを期待します。