大域ディペンダブル特論 5/28 田浦分レポート課題

大変お待たせいたしました.すっかり忘れていた,5/28田浦分講義の課題 をお知らせします.また,講義に使用したスライドは こちら(PDF)または こちら(PPT) です.

課題: 以下のいずれのうちからひとつ選んでレポートにして提出せよ.

どの課題の場合も以下を付録としてつけること(以下が評価に悪影響を 及ぼすことはない).

課題1

耐故障性のある計算を構築するための有用なbuilding blockとして,2相コミッ ト(two phase commit)がある.

課題2

授業では,非同期ネットワークで1-crash-robustな合意アルゴリズムが存 在しないことの証明の概略を述べた.適当な分散アルゴリズムの教科書(例: Tel 借りたい人は田浦まで)などを参照し,厳密な定義のもとで,証明の詳細を構 築せよ.参考文献をそのまま写したようなものは不可.本質的な理由が直感的 に納得できるよう,証明の言いかえなどを試みること.そして,この証明をよ く眺めて,合意問題と一見異なる問題で,しかし同様に1-crash-robustなアル ゴリズムが存在しない問題の例をあげよ.

課題3

実践的な耐故障ソフトウェアの構築方法として,大部分の計算ノードや protocolをstateless化することがあげられる.つまり,そのような計算ノー ドがcrashしても,計算にcriticalなstateが失われないようにし,かつ protocol (一連の状態遷移処理)の途中で計算ノードがcrashしても,その他の ノードは,いつか自動的にprotocolの開始時点の状態にrevertするように protocolを設計する(soft state).ここではそのような考え方に基づいた耐故 障ソフトウェアのプロトタイプを作成する.

問題: 耐故障タスクサーバ

以下のプログラムを作成し,ソースコードや実験結果ともにまとめる.