理工学研究科Graduate School of Science and Engineering
COT500X3（計算基盤 / Computing technologies 500）計算機システム工学特論２Computer System Engineering (Ⅱ)
和田 幸一Koichi WADA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学研究科Graduate School of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | YB005 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期集中/Intensive(Fall) |
| 曜日・時限Day/Period | 集中・その他/intensive・other courses |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数Credit(s) | 2 |
| 備考（履修条件等）Notes | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| カテゴリーCategory | 応用情報工学専攻 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
【outline and objectives】
This lecture aims to learn the principle and mechanism of distributed computations on computer networks,in particular, basic items about self-stabilizing algorithms, which are algorithmic design methods for distributed computing in faulty computer networks.
【goal】
Explain models of distributed systems, the concept of self-stability, and its motivations. The concepts of self-stabilizing algorithms and self-stabilizers on various distributed computation models and their concrete examples can be explained. Furthermore, the convergence time to self-stability and local self-stability when a failure occurs in the system can be explained using real examples.
【learning outside the classroom】
4 hours per week.
【grading criteria】
assignments and reports: 80% presentation: 20%.
授業で使用する言語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」「DP3」に関連
授業で使用する言語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]：自己安定性の動機付け
システムの初期化，故障によるシステムの任意状態からのアルゴリズム．
第5回[対面/face to face]：いろいろな分散システムにおける自己安定アルゴリズム１
トークンパッシングモデル上の自己安定アルゴリズム．
第6回[対面/face to face]：いろいろな分散システムにおける自己安定アルゴリズム２
データリンクアルゴリズム
第7回[対面/face to face]：いろいろな分散システムにおける自己安定アルゴリズム３
自己安定ランク付けアルゴリズム
第8回[対面/face to face]：いろいろな分散システムにおける自己安定アルゴリズム４
IDに基づく動的なシステム
第9回[対面/face to face]：いろいろな分散システムにおける自己安定アルゴリズム５
自己安定同期器
第10回[対面/face to face]：いろいろな分散システムにおける自己安定アルゴリズム６
匿名システムにおける自己安定名前付けアルゴリズム
第11回[対面/face to face]：自己安定器
再同期安定器，モニタリングとリセット法
第12回[対面/face to face]：システムの故障から安定までの収束１
デジタル時計の同期化，
第13回[対面/face to face]：システムの故障から安定までの収束２
ビザンチン故障に対する自己安定化，非同期システムの自己安定化．
第14回[対面/face to face]：局所自己安定性
超自己安定性，自己安定故障封じ込めアルゴリズム，エラー検出コードとエラーの修正．
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習時間は、各４時間を標準とします。】(1)毎回演習問題を出すので，それらを解き，レポートを提出する．
(2) 演習問題の発表担当者は，他の学生に理解させることを
念頭に置いてパワーポイント資料を作成すること．
本授業の準備・学習時間は，各4時間を標準とする．
テキスト（教科書）Textbooks
Shlomi Dolev, Self-Stabilization,The MIT Press,2000.
ISBN 0-262-04178-2.
参考書References
講義時に紹介する．
成績評価の方法と基準Grading criteria
オンラインでの開講となった場合，成績評価の方法と基準も変更する場合がある．
その場合の具体的な方法と基準は，担当教員が学習支援システムで提示する．
(1) テスト，演習問題のレポート提出・発表，出席状況，質問への応答により評価する．
(2) 本科目において設定した到達目標の60％以上達成した場合に合格とする．
学生の意見等からの気づきChanges following student comments
特になし．
その他の重要事項Others
担当教員から，学習支援システムを通じた連絡がないか，日ごろから確認をよくするようにしてください．