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

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

分散システムおよびネットワークシステムにおいて効率的な処理・耐故障処理を実現するためのアルゴリズム理論を学ぶ。
分散システムの基礎アルゴリズムについて学ぶとともに、ゲーム理論を用いた応用的アルゴリズムについて

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

　１　分散システムとは
　　　分散システムが使われるようになってきた歴史的経緯について解説する。
　　　準備学習：教科書第１章を読んでおく。
　２　時刻と全域状態
　　　分散システムにおける仮想的な時刻の概念について解説する。
　　　準備学習：教科書第２章を読んでおく。
　３　分散スナップショット
　　　分散システムにおける全域状態を得るアルゴリズムについて解説する。
　　　準備学習：教科書第３章を読んでおく。
　４　リーダ選挙問題
　　　システム内で唯一のリーダを選ぶアルゴリズムについて解説する。
　　　準備学習：教科書第４章を読んでおく。
　５　分散相互排除問題
　　　複数のプロセスからの要求のうち１つだけをかなえる相互排除問題を解くアルゴリズムについて解説する。
　　　準備学習：教科書第５章を読んでおく。
　６　放送型通信アルゴリズム
　　　複数のプロセスに同一の順序でメッセージを受信させるためのアルゴリズムについて解説する。　
　　　準備学習：教科書第６章を読んでおく。
　７　合意問題
　　　複数のプロセスが同一の値に合意するためのアルゴリズムについて解説する。
　　　準備学習：教科書第７章を読んでおく。
　８　自己安定アルゴリズム
　　　準備学習：教科書第８章を読んでおく。
　９　ケーキ分割問題（１）：問題の定義
　　　複数の参加者間で分割可能な財を公平に分割する問題の定義と古典的結果について解説する。
　　　準備学習：参考書（２）の２．１−２．２章を読んでおく。
１０　ケーキ分割問題（２）：最近の成果
　　　複数の参加者間で分割可能な財を公平に分割する問題に関する最近の研究について解説する。
　　　準備学習：参考書（２）の２．３章を読んでおく。
１１−１５　　
　　　トピックス　　　
　　　分散アルゴリズムに関する最新の研究成果に関して輪講を行い、レポートを作成する

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

課題レポートの内容に対する評価で行う。

１００点満点で評価し、６０点以上を合格とする。

＜教科書＞

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

＜参考書＞

（１）増澤利光、山下雅史著　「適応的分散アルゴリズム」　共立出版
（２）伊藤大雄著　「パズル・ゲームで楽しむ数学」　森北出版

＜オフィスアワー＞

A-1572研究室で行う。
メールで事前に連絡してアポイントメントを取ること。
メールアドレス：jt13455@ns.kogakuin.ac.jp

＜学生へのメッセージ＞

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

このページの著作権は学校法人工学院大学が有しています。 Copyright(c)2014 Kogakuin University. All Rights Reserved.