2024年度 学院等開講科目 情報理工学院 情報工学系 情報工学コース
フォールトトレラント分散アルゴリズム
- 開講元
- 情報工学コース
- 担当教員
- BONNET FRANCOIS PIERRE ANDRE / DEFAGO XAVIER
- 授業形態
- 講義 (対面型)
- メディア利用科目
- -
- 曜日・時限
(講義室) - 月7-8 (M-155(H1104)) / 木7-8 (M-155(H1104))
- クラス
- -
- 科目コード
- CSC.T527
- 単位数
- 200
- 開講時期
- 2024年度
- 開講クォーター
- 3Q
- シラバス更新日
- 2025年3月14日
- 使用言語
- 英語
シラバス
授業の目的（ねらい）、概要
The course aims to develop a thorough understanding of fault-tolerance in distributed systems. Due to their nature, distributed systems are inherently vulnerable to failures if not designed properly. At any time, a subset of the processes in a distributed system may fail by crashing or could be compromised and behave in a treacherous way (e.g., Byzantine failures). It is hence essential to design distributed systems and applications in such a way that they can adequately cope with failures. The lecture will present focus on how to deal with these issues.
到達目標
By studying relevant methods and algorithms in details, the student will acquire a deep understanding of the issues at hand and the basic mechanisms to deal with such failures. Although the course will focus on the theory of such systems, it will also systematically draw links with practical applications, making it valuable to both theoreticians and practitioners.
キーワード
Distributed algorithms, message-passing, synchrony models, agreement, replication, fault-tolerance, Byzantine agreement, self-stabilization, blockchain, randomized algorithms
学生が身につける力
- 専門力
- 教養力
- コミュニケーション力
- 展開力 (探究力又は設定力)
- 展開力 (実践力又は解決力)
授業の進め方
Typical classes will alternate between slide-based presentations, interactive discussions, class exercises. Active contribution to class discussions is strongly encouraged.
授業計画・課題
| 授業計画 | 課題 | |
|---|---|---|
| 第1回 | Introduction, models & definitions | Revision of basic concepts of distributed algorithms (models, synchrony, causality) |
| 第2回 | Synchronous consensus | 授業時に指示する． |
| 第3回 | Asynchronous consensus, FLP impossibility proof | 授業時に指示する． |
| 第4回 | Consensus in the presence of partial synchrony | 授業時に指示する． |
| 第5回 | Asynchronous consensus with unreliable failure detectors | 授業時に指示する． |
| 第6回 | Eventual leader election, Paxos | 授業時に指示する． |
| 第7回 | Byzantine consensus (I) | 授業時に指示する． |
| 第8回 | Byzantine consensus (II) | 授業時に指示する． |
| 第9回 | Randomized consensus | 授業時に指示する． |
| 第10回 | State-machine replication | 授業時に指示する． |
| 第11回 | Distributed transactions, distributed ledger, blockchain mechanisms | 授業時に指示する． |
| 第12回 | Self-stabilization (I) | 授業時に指示する． |
| 第13回 | Self-stabilization (II) | 授業時に指示する． |
| 第14回 | Q&A + final test | 授業時に指示する． |
準備学修(事前学修・復習)等についての指示
学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。
教科書
Course materials:
Slide copies, additional article copies, ...made available for download from the course webpage.
参考書、講義資料等
Reference Books:
1. Michel Raynal, "Fault-tolerant message-passing distributed systems," Springer, 2018. https://www.springer.com/gp/book/9783319941400
2. Ajay Kshemkalyani, Mukesh Singhal, "Distributed computing: principles, algorithms, and systems," Cambridge Uni. Press, 2011.
3. Wan Fokkink, "Distributed algorithms: an intuitive approach ," MIT Press, 2013.
4. Vijay K. Garg, "Elements of distributed computing," IEEE, 2002.
5. Gerard Tel, "Introduction to distributed algorithms (2nd ed.)," Cambridge Univ. Press, 2000.
6. Shlomi Dolev, "Self-Stabilization," MIT Press, 2000. https://mitpress.mit.edu/books/self-stabilization
7. Karine Altisen, Stéphane Devismes, Swan Dubois, Franck Petit, "Introduction to Distributed Self-Stabilizing Algorithms", Morgan & Claypool, 2019.
成績評価の方法及び基準
Homework assignments and contribution to class discussion, assignments, reports (60%); and examination (40%).
Examination will assess the understanding of basic concepts of fault-tolerant distributed algorithms (problems, algorithms, and methodology) and reasoning (correctness and complexity).
関連する科目
- CSC.T438 ： 分散アルゴリズム
- CSC.T524 ： ディペンダブルコンピューティング
- MCS.T213 ： アルゴリズムとデータ構造
履修の条件・注意事項
Required knowledge:
Prior to taking this course, the student must have previously acquired,
through lectures or self-study, background knowledge on basic concepts
of fault-free distributed algorithms such as taught in the following
course:
- CSC.T438 Distributed algorithm
その他
Related course:
In the field of fault-tolerant and dependable computing systems, this course is complementary with:
- CSC.T524 Dependable Computing
- CSC.T438 Distributed Algorithms