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

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

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

This is a graduate-level distributed algorithm course. The course provides the knowledge about
distributed algorithms used in distributed systems and networks to achieve effective and fault-tolerant information processing.
Recent results on distributed algorithms are also studied in a seminar.

具体的な到達目標は以下の通りである。
１．分散システム構築の基本を理解できる。
２．分散アルゴリズムの効率を評価できる。
３．耐故障分散アルゴリズムの基本を理解できる。

On completion of this course, the student should be able to:
(1)Have basic knowledge related to fundamental of distributed algorithms.
(2)Evaluate complexity of fundamental distributed algorithms.
(3)Have basic knowledge of techniques for fault-tolerant distributed systems.

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

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

Subjects in the course
1 Introduction.
Backgrounds of the distributed systems.
(Preparation) Read Section 1.1-1.4 of the textbook.

2 Issues in distributed processing systems.
Time in distributed systems.
(Preparation) Read Section 1.5-2.1 of the textbook.

3 Logical clock.
(Preparation) Read Section 2.2-2.3 of the textbook.

4 Distributed snapshot.
(Preparation) Read Section 3 of the textbook.

5 Leader election
(Preparation) Read Section 4 of the textbook.

6 Mutual exclusion
(Preparation) Read Section 5 of the textbook.

7 Broadcast communication.
(Preparation) Read Section 6 of the textbook.

8 Agreement protocol.
(Preparation) Read Section 7.1-7.2 of the textbook.

9 Byzantine agreement.
(Preparation) Read Section 7.3-7.4 of the textbook.

10 Self-stabilizing algorithm.
(Preparation) Read Section 8 of the textbook.

11 Topics: scheduling
Presentation of recent results on distributed algorithms in an international conference.
(Preparation) Read a technical paper in the conference.

12 Topics: agreement
Presentation of recent results on distributed algorithms in an international conference.
(Preparation) Read a technical paper in the conference.

13 Topics: fault-tolerance
Presentation of recent results on distributed algorithms in an international conference.
(Preparation) Read a technical paper in the conference.

14 Reviewing of the course
(Preparation) Reviewing of the course.

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

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

Evaluation
Students must make a presentation on a recent paper in an international conference related to distributed algorithms.
The presentation is evaluated by the student's understanding of the content and descriptive explanation and scored by 100-point scale.
To pass this course, more than 60 points are required.

＜教科書＞

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

Textbook:
Yoshifumi Manabe: "Distributed processing systems," Morikita Publishing (In Japanese)

＜参考書＞

Nancy Lynch:"Distributed Algorithms," Morgan Kaufmann

＜オフィスアワー＞

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

Office hour:
Thursday 2nd period at A-1572
(Or contact jt13455@ns.kogakuin.ac.jp)