分散システム、分散アルゴリズム

分散システム

                                       電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/coins/dsys-1998/1999-02-02 /dist-system.html
あるいは、次のページから手繰っていくこともできます。
http://www.hlla.is.tsukuba.ac.jp/~yas/coins/
http://www.hlla.is.tsukuba.ac.jp/~yas/index-j.html

■分散システムの性質と目標

◆分散システム

• 複数の構成要素（コンピュータ）から構成される
• ネットワークで接続されている
• 使っている人には、あるレベル１台の集中システムのように見える。

◆集中システム

• 一組みのハードウェア
• ＣＰＵ、メモリ、ハードディスク
• １つのオペレーティング・システム
• 自律システムを作り出す技術がある
  一貫性がある、矛盾がない
  方針（policy）が完全に反映できる
• セキュリティの確保に物理的な位置が使える

◆分散システムの利点

• 安い−−マイクロプロセッサ
• 速い−−並列処理
• 本質的に分散−−ＷＷＷ、電子メール
• 段階的成長が可能。毎年買い足し。
• がんばれば、信頼性を高くできる
  システムの一部が故障しても、全体は動き続ける

◆分散システムの弱点

• ソフトウェア技術が遅れている
• ネットワークが飽和することがある
• セキュリティの確保が難しい

◆分散システムの設計目標

• 透明性
• フォールト・トレランス
• 拡張性
• 性能（並列処理）

◆透明性

• 分散透明性
  　システムが複数のコンピュータから構成されていることを、使っている人が 気が付かない
  地理的な位置、移動、複製、平行、並列、時間

◆フォールト・トレランス

• システムの一部が故障した時、サービスを続ける。
• 分散システムは、潜在的には、フォールト・トレランスを実現できる。
• 下手に作ると、１台でも止まると全部止る。

４台同時に故障する確率：0.05^4==0.00006

◆スケーラビリティ

構成要素の数が増えた時にどうなるか。 10台で動くものが100台、1000台で動くか。

◆（集中）アルゴリズム

（集中）システムで問題を解くための指令の集まり。

• ｉｆ文
• ｗｈｉｌｅ文
• 手続き呼び出し

◆分散アルゴリズム

• 要素間のメッセージの伝達の方法の集まり
• 分散アルゴリズム
• どのコンピュータもシステム状態に関して完全な情報を持たない、 コンピュータは、ローカルな情報だけで決定する。
• １台のコンピュータが故障しても、全体が破滅しない。
• グローバルな時計が存在しない。

◆分散アルゴリズムの例

• 電話で放送
• 電話で多数決
• 時計を合わせる

◆トレードオフ

実用になり、かつ、利益に見合うコストで実現できる範囲を探すことが大事に なる。