理工学部Faculty of Science and Engineering
COT300XE（計算基盤 / Computing technologies 300）分散アルゴリズムDistributed algorithms
和田 幸一Koichi WADA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学部Faculty of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | H6052 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 火4/Tue.4 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数Credit(s) | |
| 備考（履修条件等）Notes | |
| 他学部公開科目Open Program | |
| 他学部公開（履修条件等）Open Program (Notes) | |
| グローバル・オープン科目Global Open Program | |
| 成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | |
| 成績優秀者の他学部科目履修（履修条件等）Interdepartmental class taking system for Academic Achievers (Notes) | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| SDGsCPSDGs CP | |
| アーバンデザインCPUrban Design CP | |
| ダイバーシティCPDiversity CP | |
| 未来教室CPLearning for the Future CP | |
| カーボンニュートラルCPCarbon Neutral CP | |
| 千代田コンソ単位互換提供（他大学向け）Chiyoda Campus Consortium | |
| カテゴリー＜理工学部＞Category |
応用情報工学科 学科専門科目 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
【outline and objectives】
This lecture aims to learn the foundations about distributed computing, such as the principle of distributed computing systems on computer networks, and its mechanism, and algorithmic design paradigm of distributed computation on fault prone networks.
【goal】
Understand the basics of distributed system models, distributed system stability, checkpointing and rollback, fault-tolerant distributed algorithms, no-wait systems, self-stabilizing systems, and distributed computation on dynamic networks, and be able to explain each of these topics using concrete examples.
【learning outside the classroom】
4 hours per week.
【grading criteria】
assignments and reports: 40%, exam: 60%.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
計算機をネットワークで結合した計算機ネットワーク上での分散計算システムの原理とその仕組み，故障が発生するネットワーク上での分散計算のアルゴリズム設計技法などの分散計算に関する基礎的事項の学習を目的とする．
到達目標Goal
分散システムのモデル，分散システムの安定性，チェックポイントとロールバック，耐故障性分散アルゴリズム，無待機システム，自己安定システム，動的ネットワーク上での分散計算の基本的事項を理解し，それぞれ具体的な実例を用いて説明ができる．
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」と「DP2」と「DP4」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
オンラインでの開講となった場合，オンライン授業の方法や各回の授業計画の変更，成績評価方法の変更などについては，学習支援システムでその都度提示する．
課題等の提出，フィードバックは学習支援システムを通じて行う予定です．
分散システムのモデル，分散システムの安定性，チェックポイントとロールバック，耐故障性分散アルゴリズム，無待機システム，自己安定システム，動的ネットワーク上での分散計算に関して，講義形式で行う．
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
なし / No
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
第1回[対面/face to face]：オリエンテーション
分散計算とは．例題による分散アルゴリズム入門
第2回[対面/face to face]：分散計算の基礎的概念1
分散システムのモデル
第3回[対面/face to face]：分散計算の基礎的概念2
同期モデル，故障モデル．
第4回[対面/face to face]：分散システムの安定性1
送信，放送，合意．
第5回[対面/face to face]：分散システムの安定性2
コミット，相互排除，トークン巡回．
第6回[対面/face to face]：チェックポイントとロールバックリカバリ
独立チェックポイント法とドミノ効果
第7回[対面/face to face]：耐故障性合意アルゴリズム1
完全非同期システム上の合意アルゴリズム，故障検知器
第8回[対面/face to face]：耐故障性合意アルゴリズム2
ビザンチン合意問題
第9回[対面/face to face]：無待機システム1
逐次一貫性と線形化可能性
第10回[対面/face to face]：無待機システム2
共有オブジェクトを実現する無待機アルゴリズム
第11回[対面/face to face]：自己安定アルゴリズム1
自己安定アルゴリズムとは，
自己安定アルゴリズムの具体例
第12回[対面/face to face]：自己安定アルゴリズム2
自己安定アルゴリズムの合成，乱択自己安定アルゴリズム．
第13回[対面/face to face]：動的ネットワークにおける分散アルゴリズム1
動的ネットワークのモデル
第14回[対面/face to face]：動的ネットワークにおける分散アルゴリズム2
動的ネットワーク上でのトークン巡回アルゴリズム
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
毎回演習問題を出すので，それらを解き，レポートを提出する．
本授業の準備・学習時間は，各4時間を標準とする．
テキスト（教科書）Textbooks
分散処理システム，真鍋義文著，森北出版
ISBN978-4-627-81071-6 C3304（電子版）
参考書References
講義時に提示する．
成績評価の方法と基準Grading criteria
オンラインでの開講となった場合，成績評価の方法と基準も変更する場合がある．
その場合の具体的な方法と基準は，担当教員が学習支援システムで提示する．
(1) テスト，演習問題のレポート提出，質問への応答により評価する．
(2) 本科目において設定した到達目標の60％以上達成した場合に合格とする．
学生の意見等からの気づきChanges following student comments
特になし．
その他の重要事項Others
担当教員から，学習支援システムを通じた連絡がないか，日ごろから確認をよくするようにしてください．