分散アルゴリズム特論 [ハイ]

開講年度

2025年度

開講学期

後期

科目名

分散アルゴリズム特論

授業種別

講義

科目名（英語）

Distributed Algorithms

授業情報(授業コード・クラス名・授業形態)

Z0200001 分散アルゴリズム特論 [ハイ]

担当教員

真鍋義文

単位数

2.0単位

曜日時限

木曜2限

キャンパス

新宿　遠隔

教室

.、A-0511教室

学位授与の方針

A 専攻する研究領域における高度な専門知識を身につけたもの 80%
B 科学技術を運用する能力を身につけたもの　20%
C 主体的に研究に取り組み、社会や職業についての知識や技術者や研究者として必要な倫理観を身につけたもの　0%
D 特定の専門領域における創成能力を身につけたもの　0%

具体的な到達目標

分散システムおよびネットワークシステムにおいて効率的な処理・耐故障処理を実現するためのアルゴリズム理論を学ぶ。
分散システムの基礎アルゴリズムについて学ぶとともに、最新の研究成果についても学ぶ。
具体的な到達目標は以下の通りである。
１．分散システム構築の基本を理解できる。
２．分散アルゴリズムの効率を評価できる。
３．耐故障分散アルゴリズムの基本を理解できる。

本講義の第１回ー第１４回はハイブリッドで実施する。
希望者は遠隔（同時双方向）で受講可（事前申請不要）。
第１５回は遠隔（オンデマンド）で実施する。

受講にあたっての前提条件

基本的なアルゴリズムに関する知識を持っていること。

AL・ICT活用

クリッカー・タブレット等ICTを活用した双方向授業／e-ラーニング等ICTを活用した自主学習支援

授業計画

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

成績評価の方法

毎回の講義中に出題する課題（１０％）および分散アルゴリズムに関連した国際会議論文についての最終レポート提出（９０％）の成績をもとに理解度をA+,A,B,C,D,FのGradeで評価する。
Grade D以上を合格とする。

受講生へのフィードバック方法

毎回のレポートおよび最終レポートについて次の回の講義でフィードバックを行う

教科書

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

参考書

Nancy Lynch: "Distributed Algorithms," Morgan Kaufmann

オフィスアワー

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

受講生へのメッセージ

実務家担当科目

実務経験の内容

通信会社の研究所での勤務の経験がある教員が、分散処理研究の経験を活かし、先進的な分散アルゴリズムについて講義する。

教職課程認定該当学科

情報学専攻

シラバス情報