-title: 連邦型Lindaによる分散アルゴリズムをデバッグするためのメタプロトコル

--author: 赤嶺悠太, 小野雅俊, 河野真治


--分散アルゴリズムを勉強する

	Socketからプログラムするのは敷居が高すぎる

でも実際に動かしてみないと体験出来ない。

	通信のモデルがある方が良い

	Linda って、モデルはわかりやすいよね〜

しかし、Linda の共有されたタプル空間ではScale しようがない

--Scaleする分散プログラム

Scalabilty とは?

	接続するサーバ、ネットワーク規模が増える

	増えても、サービスの性質を一定に保つ

--分散プログラムの三つの要素

	Local Accesss       末端の通信

	Protocol Engine     通信するサーバ

	Configuration       サーバの接続パターン


--プロトコルエンジンとタプル空間

タプル空間を相互に、プロトコルエンジンが接続すると言うのを考える

	タプル空間一つにアクセスが集中しない

	DHTとかとは正反対

Scale する適切なプロトコルを提供して、それを使用して分散アルゴリズムを作る

--Single Thread Implementation

	一つのLinda Server はSingle Threaded

	二つのLinda Serverを接続するPrototocol Engine はSingle Threaded

	in/out では待ち合わせを行なわない

	polling ( callback ) base でプログラムする

--The Reason why Single Thread Implementation

	実装しやすい

	デバッグしやすい

	APIがゲーム向き (主ターゲットがネットワークゲーム)

--API

public PSXLinda open(String _host,int _port)

public PSXReply in(int id)

    タプルスペース番号より引数で指定したidのタプルの受け取りを要求する。

public PSXReply out(int id, ByteBuffer data)

    引数で指定したidでByteBuffer内のデータを送信する。

public int sync(long mtimeout) 

    接続しているLinda Serverとタプルの送受信のポーリングを行う。

\end{itemize}

--プログラミング例

    FederatedLinda fdl;
    PSXLinda getpsx;
    PSXLinda sendpsx;
    PSXReply in;
    ByteBuffer data = ByteBuffer.allocate(10);

    //通信を初期化する
    fdl = FederatedLinda.init();
    //データを取ってくるホストと受け渡すホストとの接続開始
    getpsx  = fdl.open("cs100",10000);
    sendpsx = fdl.open("cs101",10001);
    //取ってくるホストからinを指定してデータを取得
    in = getpsx.in(10)
    data = in.getData();
    //受け渡すホストに対しデータとidを指定して同期
    sendpsx.out(10,data);
    fdl.sync();

--例えば、

これを使って、Compact Routing を実装してみる

    Compact Routing でも Mesh などでは、収束しない

細かい実装をしないとScaleしない。(Split horizen, Hop count)

プログラムミスなのか、アルゴリズムが悪いのか?

Scale するように調整するには?

--デバッグするには?

	サーバの数だけ画面を開く....

だめです。

デバッグを実装する必要がある。

--デバッガに対する要求

	タプル空間に直接アクセス出来る

	デバッグ自体がScale して欲しい

	デバッグ通信自体が、Federated Linda であるべき

	デバッグ通信のデバッグ対象への影響が少ない

	local なサーバの状態だけでなく大域的な通信状態を取り扱える

--メタエンジン

Linda Server に、タプル空間をいじれるメタエンジンを付加する

メタエンジン上に、Fedrated Linda を使ってデバッグプロトコルを実装する

--メタエンジンの実装

Linda Sever/Protocol Engine はSingle Thread なので、変わりばんこに実行してやれば良い。

最初にFederated Linda 上で通常のプログラムとしてデバッグプロトコルを作成する

それを、メタエンジンでの通信に移す

--Linda ServerとMeta Engine

Linda ServerとProtocol Engineは、1対1が自然なようである

Meta Engine とProtocol Engine の違いは、タプル空間に直接さわれるかどうか

なので、今後は、1対1を仮定して良いと思われる

--分散プログラムのデバッグ手法

対象とするバグ

	Protocol Engine の実装ミス

	    入出力が正しくない

	大域的な分散アルゴリズム自体のミス

	    Dead Lock/Live Lock

	Scale しないバグ

	    輻輳、飢餓


--デバッグプロトコル

	大域状態を調べる

	計算を止める

	計算を再開する

	デッドロック/ライブロックを検出する

	条件に従って入出力するタプルの通信パターンを記憶する

--デバッグ用の通信パターン

もっとも干渉が少ない場合として、単一のデバッグコマンドを全サーバに周回させるプロトコルを考える。


--実験

Linda Server間でMeta Engineがデータをやり取りする場合

<center><img src="fig/meta_ring_three.jpg"></center>


3〜100までの台数でデータが1周(図\ref{metaring})する時間、
および1000周(図\ref{metaring1000})した時に掛かった時間を測定する。
前者では接続の手間を含む通信時間、後者では通信のみの時間を
計ることが出来る。

実験は、
琉球大学
情報工学科のクラスタ上(Core Duo 2GHz,メモリ1GB) Torque
AlaxalA Gigabit Ethernet Switch
クラスタ自体は180台あるが、安定して動作する100台までを使用

<center><img src="fig/metaring1.jpg"></center>

データを1周のみした場合は1サイクルあたり約14000ms、一台あたり約140ms

これは、TCPの接続時間がかなり大ききことを示している。

デバッガとしては容認できないと思われる。
従って、毎回、新しく接続するようなHTMLのような
通信を採用することはできないことがわかる。

--千周の平均周回時間

<center><img src="fig/metaring1.jpg"></center>

1サイクルおよそ60ms、一台につき約0.6msとなっている。

パケット1KBから100KBまでの差は2倍程度であり、それ以上はパケットサイズに
リニアに時間がかかる。従って、数十KB程度以下にデータを抑えることは、
応答時間的には意味がない。


--まとめ

Linda  複数接続するFederated Linda Server をJava 上に実装し、

Metaで通信するMeta Protocol Engineを実装し評価した。

今後は、Meta Protocol Engineにデバッグプロトコルを実装していく