☆分散アルゴリズム特論（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.

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

　１　分散システムとは
　　　分散システムが使われるようになってきた歴史的経緯について解説する。
　　　準備学習：教科書１．１−１．４を読んでおく。
　２　分散システム構築上の課題
　　　分散システム構築上の問題点について解説する。
　　　準備学習：教科書１．５ー１．６を読んでおく。
　３　論理時計
　　　分散システムにおける論理時計の概念について解説する。
　　　準備学習：教科書２章を読んでおく。
　４　分散スナップショット
　　　分散システムの全域状態を得るアルゴリズムについて解説する。
　　　準備学習：教科書第３章を読んでおく。
　５　リーダ選挙問題
　　　システム内で唯一のリーダを選ぶアルゴリズムについて解説する。
　　　準備学習：教科書第４章を読んでおく。
　６　分散相互排除問題
　　　複数のプロセスからの要求のうち１つだけをかなえる相互排除問題を解くアルゴリズムについて解説する。
　　　準備学習：教科書第５章を読んでおく。
　７　２相コミット
　　　分散データベースの書き換えのアルゴリズムについて解説する。
　　　準備学習：データベースについて復習しておく。
　８　デッドロック検出アルゴリズム
　　　デッドロック状態を検出あるアルゴリズムについて解説する。　　　
　　　事前学習：閉路などの基本的なグラフ理論の概念について復習しておく。
　９　放送型通信アルゴリズム
　　　複数のプロセスに同一の順序でメッセージを受信させるためのアルゴリズムについて解説する。　
　　　準備学習：教科書第６章を読んでおく。　
１０　合意問題
　　　複数のプロセスが同一の値に合意するためのアルゴリズムについて解説する。
　　　準備学習：教科書７．１−７．２を読んでおく。
１１　ビザンチン合意問題
　　　ビザンチン故障の概念とビザンチン故障が存在する場合の合意アルゴリズムについて解説する。
　　　準備学習：教科書７．３−７．４を読んでおく。
１２　自己安定アルゴリズム
　　　一時的故障があっても正常な状態に戻るアルゴリズムについて解説する。
　　　準備学習：教科書第８章を読んでおく。
１３　動的ネットワークにおけるトークン巡回アルゴリズム
　　　ネットワークが動的に変更する場合に巡回して状況を把握するアルゴリズムについて解説する。
　　　全域木などの木に関するアルゴリズムを復習しておく。　　　
１４　学習の振り返り
　　　準備学習：前回までの総復習を行う。

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
(Preparation) Read Section 1.5-1.6 of the textbook.

3 Logical clock
(Preparation) Read Section 2 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 Two phase commit
(Preparation) Review about fundamentals of database.

8 Deadlock detection
(Preparation) Review about basic definitions in graph theory.

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

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

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

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

13 Token circulation in dynamic networks
(Preparation) Review algorithms for spanning trees.

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

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

毎回の講義中に出題する課題（１０％）および最終レポート提出（９０％）の成績をもとに理解度をA+,A,B,C,D,FのGradeで評価する。
Grade D以上を合格とする。

Evaluation
Students must answer to questions given in each class.(10%)
They must write a report about one topic in distributed algorithms.(90%)
Students are given the grades A+, A, B, C, D and F.
Glades other than F are pass.

＜教科書＞

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

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)