%これはちょっとマジで書きかけたものです．
%気にしないで，使ってください．
%minru

\documentclass[twocolumn, a4j, twoside]{jarticle}
\usepackage{master_proc}
\usepackage[dvips]{graphicx}

% dvipdfm を使って PDF ファイルに日本語の栞をつける
% \usepackage[dvipdfm]{color}
% \usepackage[dvipdfm,bookmarks=true,bookmarksnumbered=true,%
% bookmarkstype=toc]{hyperref}

\jtitle{分散プログラミングモデル : Federated Linda}		%和文タイトル
\etitle{Distributed Programming Model : Federated Linda}	%英文タイトル
\author{安村 恭一}	%著者名
\studentid{048545E}	%学籍番号
\teacher{河野 真治}	%指導教官

\begin{document}
  \maketitle
  \section{はじめに}
比較的ネットワーク的に遠いコンピュータを取り扱う分散プログラムはスケーラ
ブルに書くことが難しいとされている。一方、遂次プログラムなどは構造型やオ
ブジェクト指向などにより、難しさが緩和されており、自然に逐次プログラムを
書くことができる。これまでの分散フレームワークやツール群は、逐次プログラ
ミングモデルの延長だったりスケーラブルに書くには複雑で理解しづらいもので
あり、真の分散プログラミングモデルとはいえない。分散プログラムには自然に
スケーラブルな分散プログラムを書くことができる真の分散プログラミングモデ
ルが必要である。

本研究の目的は、スケーラブルな分散プログラムを自然に記述できる、真の分散
プログラミングモデルを提供することである。本論文では、本研究室で開発した
非同期型 Linda の拡張を用いて、分散プログラミングモデル Federated Linda 
を提案する。

\section{分散プログラム}

分散プログラムが難しいのは、それをスケーラブルにすることが難しいからであ
る。実際、Internet 上でも、集中サーバ構成が通常であり、きちんとスケール
する分散アプリケーションは珍しい。しかし、DNSのように大規模の対象のサー
ビスもあることから、きちんと分散アプリケーションを作ることができればイン
ターネットのような大規模な対象のサービスも実現可能といえる。

自然な分散プログラミングを目指すためには、以下のようなことが要請される。
{\small
\begin{verbatim}
・ 実際の通信のモデルが理解しやすい
・ Basic のように会話的に開発できる
・ 基本オペレーションが少なく、明解である
・ 分散環境での運用が容易
・ インターネット環境で自動的に相互接続する
\end{verbatim}
}
自然に書いて、スケールする分散プログラムになることが目標である。そのため
には分散アルゴリズム自体を内蔵するようなプログラミングモデルが望ましい。

\subsection{Linda}

本論文で提供するFederated Lindaのベースとなった分散システムLinda につい
て説明する。Linda はタプルというIDで番号づけられたデータの塊を
\tt{in,read,out}などのオペレーションを用いて、共有されたタプル空間に出し
入れすることで分散プログラムを行う(図\ref{originallinda}参照)。Linda の
利点として通信モデルが理解しやすいことが挙げられる。また、接続切断に強い
モデルである。しかし、集中型になりやすいモデルである。

\begin{figure}[hbp]
\begin{center}
\includegraphics[width=3cm]{fig/original-linda.eps}
 \caption{Linda Server}
\label{originallinda}
\end{center}
\end{figure}

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

分散プログラムには三つの要素で構成される。Protocol Engine,Local access
to protocol, Link configuration である。
Protocol Engine はプロトコルを定義している要素である。Local Access to
protocolは直接通信にアクセスするAPIである。Link Configurationは論理的な
接続を規定・接続を行う。これらの要素を分離してサポートすることで、プログ
ラムの開発・テストで、それぞれに集中することができる。また、各要素毎に切
り換えを行うことができるので、ポータビリティ性の向上が期待できる。

\section{Federated Linda の提案}
Federated Linda は、複数のタプルスペースを相互に接続することにより分散プ
ログラムを実現する。一つのタプルスペースには少数の接続があることが期待さ
れており、多数のタプルスペースが接続により分散アプリケーションを実現する
(図\ref{connection-of-tspace}参照)。インターネットのパケット転送のように、
タプルと呼ばれるIDとデータが組になったものが、タプルスペース間を転送され
ていく。

Federated Lindaは分散プログラムの要素毎に以下のモデルを提供する。Local
Accessは、in,read,outを用いたタプルを出し入れする通信モデルであり、通信
は非同期に行われる。Protocol Engineは分散アルゴリズムを内蔵するエージェン
トを記述するモデル。エージェントはタプルをリレー転送する
Link ConfigurationはXMLでトポロジを定義して、それを基に接続を行うモジュー
ルを提供する。
\begin{figure}[htp]
\begin{center}
\includegraphics[width=3.5cm]{fig/FederatedLinda.eps}
 \caption{タプルスペースの相互接続}
\label{connection-of-tspace}
\end{center}
\end{figure}

\section{プログラミング例}
Linda Server は C 言語で記述している。タプルスペースはメモリ上のキューと
して実装されている。タプルIDは16bit整数値、データは任意の文字列である。
Protocol Engine, クライアントプログラムはC, Perl, Python, Ruby で記述可能
である。以下にPython で記述したマルチキャストを行うプログラム例を載せる。
\begin{verbatim}
while (1) : # メインループ
  rep=ConnectRep.reply()
  if (rep):    # 新規の接続処理
    ConnectRep = self.linda.In(TUPLE_ID_CONNECT)
    # 新規接続者を登録
    self.tuplespaces.append(getTuplespace(rep))
  rep=MultiCastRep.reply()
  if (rep):    # マルチキャスト
    MultiCastRep=self.linda.In(TUPLE_ID_MULTICAST)
    # 全タプルスペースへデータを送信
    for t in self.tuplespaces :
      t.Out(TUPLE_ID_RECV, rep)
  self.flinda.sync()
\end{verbatim}
\section{Federated Lindaを用いたプログラミング}
Federated Linda を用いたプログラム例としてディスタンスベクタ型ルーティン
グプロトコルをPythonで実装した。宛先情報は``ホスト名:ポート番号''の文字
列として表す。Linda Serverとルーティングエージェントをセットで１ノードと
してルーティングを行う。今回接続を行ってからルーティングテーブルが安定す
るまでの時間を計測した(図\ref{exetime})。トポロジは二分木とメッシュを使
用した。また、トポロジを構築するXMLを用いて、ノード間の接続を行った。こ
の結果より、ディスタンスベクタ型ルーティングプロトコルでは二分木よりメッ
シュの方が遥かに時間がかかることが容易に確認できた。

\begin{figure}[htp]
\begin{center}
\includegraphics[width=7cm]{fig/exetime.eps}
 \caption{テーブルが安定するまでの時間}
\label{exetime}
\end{center}
\end{figure}

\section{比較}
JXTAはノードの発見とグループの自己組織化は提供するが、分散アプリケーションをど
う書くかは示してくれない。Federated Linda はタプルの出し入れという通信モ
デルと分散プログラム毎にプログラミングモデルを提供している。

CORBAはネットワークを意識しないオブジェクト呼び出しができるが、それゆえ
通信が起こるタイミングが把握しづらくなりやすい。Federated Lindaはsyncと
いう関数でしか通信は起きないので通信発生は明確である。

OverlayWeaverは分散アルゴリズムをJavaでしか記述できない。Federated Linda
は好きなスクリプト言語で記述可能である。また、通信モデルも理解しやすい。

\section{考察}
タプルの出し入れという通信モデルは直感的に分かりやすく、簡潔に書ける。ま
た、分散プログラムを要素毎に分離して提供するので、開発しやすくなっている。
Federated Linda の記述の容易さはそれらの理由によるものであると考えられる。
タプルの出し入れという通信モデルにより、タプル転送を行う。この通信モデル
はインターネットのパケット転送と酷似しており、Federated Linda を用いてイ
ンターネットの分散プログラムが記述できる。また、分散プログラムの要素を分
離して提供しているので、それらの切り替えが容易に行うことができる。

\section{まとめと課題}
スケーラブルな分散プログラミングモデルとしてFederated Lindaを提案し、実
装した。またそれらを用いたルーティングプログラムを作成した。他の分散プロ
グラムツールとの比較を行い、考察を行った。今後の課題として、Federated
Lindaを用いてより多くの分散プログラムを実装することが重要だと思われる。
{\small
  \begin{thebibliography}{9}
\bibitem{globalid}河野 真治,仲宗根 雅臣,
同期型タプル通信を用いたマルチユーザ Playstation ゲームシステム,
卒業論文, 1998

\bibitem{globalid}安村 恭一，河野 真治,
大域IDを持たない連邦型タプルスペース Federated Linda,
第99回 情報処理学会 システムソフトウェアとオペレーティング・システム研究発表会, 2005.

\bibitem{dinamicrouting}安村 恭一，河野 真治,
,動的ルーティングによりタプル配信を行なう分散タプルスペース Federated  Linda,
日本ソフトウェア科学会第22回大会, 2005.
  \end{thebibliography}
}
%   \bibitem{argentina} 中西 学，永田 裕志，猪木 寛至
%	   ``アルゼンチンバックブリーカーの効果的担ぎ方,''
%	   新日技報 Vol.99 No.38 pp.7--11，新日本技術向上学会，1999．
%   \bibitem{friendly-power} 中西 学，キン肉 卓，正義超人，
%	   ``友情パワーにおける潜在能力の引出し方,''
%	   第12回 火事場のクソ力と友情パワーシンポジウム資料，
%	   悪行超人討伐学会主催, 2000．
%\begin{table}[b]
% \begin{tabular}{cc} 
%  \parbox[c]{.14\textwidth}{\center%
%    \epsfile{file=author.eps,scale=0.65}\\
%    \begin{center}\vspace*{-4mm}{著者近影}\end{center}}&
%  \parbox[c]{.28\textwidth}{\scriptsize
%著者略歴：
%高校時代よりアマレスで活躍し、全日本選手権３連覇を達成。専修大学を卒業
%後、'91年4月に「闘魂クラブ」に入団。'92年のバルセロナ五輪に出場後、同年
%8月に新日本プロレス入門。ＳＧタッグIIで藤波のパートナーに抜擢を受け、
%同年10月13日、東大阪市立中央体育館におけるＳ・ノートン、Ｓ・Ｓ・マシン
%組戦でデビュー。'95年3月の第6回ＹＬ杯に優勝し、同年6月に米国武者修行
%へ出発。同年7月よりＷＣＷマットに参戦し、クロサワの名で活躍。'96年9月に
%凱旋し、'97年５月、小島と組み第31代IWGPタッグ王座に君臨。'98年12月、
%IWGPヘビー級王座に初挑戦。'99年8月、Ｇ1クライマックス初優勝に輝き、８・
%28神宮で永田と組み第39代IWGPタッグ王座に就く。今年3月格闘集団「G-EGGS」
%の一員となる。
%}
% \end{tabular}
%\end{table}

\end{document}