\chapter{分散プログラム}

分散プログラ厶は比較的ネットワーク的に遠いコンピュータを取り扱うプログラ
厶である。本章では分散プログラ厶の難しい点を挙げ、それを解決するのに必要
な要素を説明する。

\section{分散プログラミングのどこが難しいのか}

単純に離れたホスト間で通信して動作するだけならば、プログラム自体は難しく
ない。ただ、逐次プログラムに通信プリミティブを導入すれば良いだけである。
分散プログラムが難しいのは、それをスケーラブルにすること、つまり、規模を
大きくしたときにもちゃんと動作するようにすることが難しいからである。

実際、Internet 上でも、2点間で通信する、あるいは、比較的少数のアクセスを
想定した集中サーバ構成が通常であり、きちんとスケールする分散アプリケーショ
ンは珍しい。例えば、DNS (Domain Name System) は、そのようなスケールする
分散アプリケーションの一つである。DNS は、数十万人を対象とした強力な少数
の集中サーバなどと異なり、はるかに大きな規模(数億人)を対象のサービスを、
より非力な、より多数のホストによって実現している。一方で、IRC (Internet
Relay Chat)などは、単純な木構造を持つメッセージ放送システムであるが、サー
バ管理などを怠ると全体のパフォーマンスが極端に下がってしまう。Net News 
なども配送効率は非常に高いが、運営コストは大きい。

このような状況では、Internet 規模で動作する分散プログラムは難しく、集中
サーバ構成を取る方が容易だとも言える。しかし、DNS のような成功した例もあ
り、分散アプリケーションをちゃんと作ることができれば、全体的なコストとパ
フォーマンス、そして安全性も増すと考えられる。

分散プログラムが Internet 規模で動作するためには、以下のような機能を実装
する必要がある。

\begin{enumerate}
\item ホスト数が増えてもアクセスの集中がないようにする手法
\item サービスの増加に対応した動的な接続変更
\item 通信の切断への対処
\end{enumerate}


\section{タプル空間による分散プログラム Linda}

本論文でははタプルスペースを用いた手法を使うので、Linda\cite{linda} につ
いての考察を行う。Linda は、タプルというid で番号づけられたデータの塊を
以下のAPI (表\ref{fig:lindaapi}) で、共有されたタプル空間に出し入れする
ことにより分散プログラムを行う。(図\ref{fig:linda})

% 図 Linda

\begin{table}[htb]
\begin{center}
\caption{Linda API}
\label{fig:lindaapi}
\begin{tabular}{|l|l|}
\hline
 & id に対応するtuple\\ \hline
 in(id)   & タプル空間から取り出す。タプル空間にタプルは残らない\\ \hline
 read(id)   & タプル空間から取り出す。タプル空間にタプルが残る\\ \hline
 out(id,data)        & タプル空間にタプルを入れる \\
\hline
\end{tabular}
\end{center}
\end{table}

  \begin{figure}[htb]
   \begin{center}
\includegraphics[width=8cm]{fig/original-linda.eps}
   \end{center}
   \caption{LindaServer}
   \label{fig:linda}
  \end{figure}

Lindaの利点としては、まず、通信モデルが理解しやすいことがあげられる。一
つは基本オペレーションが少ないからである。したがって実装も容易である。ま
た、タプル空間は接続の切断にも強く((3)に対応)、空間に接続するクライアン
トの構成の変更((2)に対応)も容易である。しかし、Linda が実用的なプログラ
ムで用いられないのは、タプル空間を単一のサーバとして実装すると、サーバに
アクセスが集中してしまうからである。タプル空間をスケールするように作るの
は非常に難しい。キャッシュや複製を利用したものがいくつか提案されたが、実
際の通信がLindaのモデルとは別なものになってしまうのは望ましくない。つま
り、Linda は、素直に書くと集中型になってしまう分散プログラミングモデルで
ある。

\section{今までのツール}

通信ライブラリを用意すれば分散プログラムは可能となる。しかし、それは、
チューリングマシンで、すべての計算が可能というような意味でしかない。

多数のエージェントが巨大な共有データに自由にアクセスすると言うブラックボー
ドモデルは、AIで良く使われている。これは、タプル空間のモデルと良く似たも
のであり、同じ欠点を持っている。我々は、Linda のAPIを非同期にすること
\cite{linda}により、ビデオゲームのようなリアルタイムアプリケーションに対
しても、Linda が有効であることを示して来た。分散共有メモリは、タプル空間
よりも均一なメモリアクセスを提供するが、その裏では複雑なメモリのコンシス
テシー制御が動いていて、その通信のスケーラビリティを制御することは難しい。

分散オブジェクトは、通信の主体としてデータの集りを用いる。様々な提案され
たObject Request Broker(ORB)\cite{orb}は通信データの規格化や、通信の設定
には有効である。しかし、任意のオブジェクトが任意のオブジェクトに自由に通
信できるので、実際に、どうやって分散プログラムを作るのかと言うことに関し
ては助けにならない。Sun のJini \cite{jini}なども分散アルゴリズムそのもの
には無関心である。JXTA \cite{jxta}はサーバの配置しか解決してくれない。

このような「プロ向け」のツールではなく、より教育的、あるいは、分散アルゴ
リズム、分散アプリケーションを玩具のように作っていけるツールがないのだろ
うか?

\section{分散プログラミングモデルに必要なもの}

自然な分散プログラミングを目指すためには以下のようなことが要請されると考
えている。

\begin{itemize}
\item 実際の通信のモデルが理解しやすい
\item Basic のように会話的に開発できる
\item Linda のように基本オペレーションが少ない
\item 分散環境での運用が容易
\item インターネット環境で自動的に相互接続する
\end{itemize}

自然に書いて、スケールする分散プログラムになることが目標である。そのため
には、高度な分散アルゴリズムを使う必要がある。それは、アプリケーションの
プログラミングからは、関数呼び出しの呼出先のデータ構造やアルゴリズムが隠
蔽されるという意味で、隠蔽される必要がある。つまり、分散アルゴリズム自体
を内蔵するようなプログラミングモデルが望ましい。

%    P2P (や streaming )は、別なものに任せる

\section{分散プログラムの要素}

分散プログラムには三つの要素がある。

\begin{verbatim}
    Distributed Program =
        Protocol Engine 
        Local access to protocol
        Link configuration 
\end{verbatim}

これらの三つを分離してサポートできれば、プログラム開発時、あるいはテスト
時に、その一部に集中することができる。プロトコルのプログラムと、アプリケー
ションのプログラムの分離が重要であると考えられる。
 
Local access は直接に通信にアクセスするAPIである。これは、本質的に非同期
である。終了を待つ read/writeや、同じく終了を待つ Linda の in/out では機
能的に足りない。例えば、データを待っているプロセスを途中で止めることがで
きなくなってしまう。これを{\tt [マルチスレッド+同期機構]}あるいは、{\tt
[割込みや例外処理]}で対処することもできるが、プログラミングモデルは極め
て複雑になってしまう。一方で、コンピュータのCPU のハードウェアモデルは単
純で{\tt [状態遷移機械]}つまり、入力に対して反応して状態を変えるだけであ
る。Local access API は、より単純なものが望ましい。

分散プログラムは、物理的に離れたホストと、それをつなぐ物理的、論理的なネッ
トワーク接続を含む。これの管理は手動では極めて繁雑である。PCクラスタのよ
うな状況ではMPIシェルのような形で管理するのが簡単だが、Internet 環境では
そうはいかない。同じ分散アルゴリズムでも配置によって異なる振舞をする。ま
た、同じ物理構成、論理構成でも異なるアプリケーションが走ることがある。同
じ物理構成でも、論理的には異なるネットワークを構成することもある。例えば、
スパニングツリーなどはそのようなものである。スパニングツリーは、ブリッジ
間のネットワークで経路のループを防止する制御手法であり、物理的なネットワー
クで経路のループがあると、論理的なネットワークでループが発生している経路
を切断することで、ループを防いでいる。経路のループを防ぐことで、データが
永遠に循環することを防止し、また障害発生時に論理的に切断した経路を接続す
ることで迂回経路を確保することができる。このように、スパニングツリーでは
物理的ネットワークと論理的ネットワークが異なる構成をすることがある。