--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/presentation/federated-linda.ind	Fri Apr 24 07:49:19 2009 +0900
@@ -0,0 +1,272 @@
+-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 しないバグ
+
+	    輻輳、飢餓
+
+
+--デバッグプロトコル
+
+	大域状態を調べる
+
+	計算を止める
+
+	計算を再開する
+
+	デッドロック/ライブロックを検出する
+
+	条件に従って入出力するタプルの通信パターンを記憶する
+
+--デバッグ用の通信パターン
+
+もっとも干渉が少ない場合として、単一のデバッグコマンドを全サーバに周回させるプロトコルを考える。
+
+
+--Simulation
+
+分散通信に影響を最低限にするために、Ringで性能を評価する。
+3台のLinda Server間でMeta Engineがデータをやり取りする場合
+のUMLシーケンス図は
+図\ref{ringthree}のようになる。
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[scale=0.2]{fig/meta_ring_three.eps}
+\caption{3台間の通信}
+\label{ringthree}
+\end{center}
+\end{figure}
+
+Ring では通信パケットは一つのみであり、デバッグ対象への
+影響が小さい。
+しかし、スナップショットや一時停止などの
+デバッグ操作をするためには、全ノードを周回する必要がある。
+%これはo(n)であり、十分にスケーラビリティがあるとは言えない。
+%しかし、もっとも影響が少ない方法なので、どの程度まで使える
+%かを測定することには意味がある。
+
+ここでは、通信パケットの大きさを変えて、
+3〜100までの台数でデータが1周(図\ref{metaring})する時間、
+および1000周(図\ref{metaring1000})した時に掛かった時間を測定する。
+前者では接続の手間を含む通信時間、後者では通信のみの時間を
+計ることが出来る。
+
+実験は、
+琉球大学
+情報工学科のクラスタ上(Core Duo 2GHz,メモリ1GB)で、
+クラスタジョブ管理システム
+Torqueを用いて行なった。
+ネットワークはAlaxalA Gigabit Ethernet Switchで構成されている。
+クラスタ自体は180台あるが、
+安定して動作する100台までを使用して測定を行なった。
+
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[scale=0.3]{fig/metaring1.eps}
+\caption{接続を含む一周の時間}
+\label{metaring}
+\end{center}
+\end{figure}
+
+X軸が台数、Y軸がミリ秒、ラインの色が通信するデータサイズを表す。
+両図から見てわかる通り、データの量にはあまり依存する事はなくほぼ同じラインを形作っている。
+データを1周のみした場合は1サイクルあたり約14000ms、一台あたり約140ms掛かっている計算になる。
+これは、TCPの接続時間がかなり大ききことを示している。1MB程度の通信を
+隠すほど接続時間のオーバヘッドは大きい。
+14秒はインタラクティブな
+デバッガとしては容認できないと思われる。
+従って、毎回、新しく接続するようなHTMLのような
+通信を採用することはできないことがわかる。
+
+
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[scale=0.3]{fig/metaring1000.eps}
+\caption{千周の平均周回時間}
+\label{metaring1000}
+\end{center}
+\end{figure}
+
+それに対し1000周した際に掛かった時間は、1サイクルおよそ60ms、一台につき約0.6msとなっている。
+これより、一度、接続してしまえば、
+Meta Engine での通信は実際に100台程度のデバッグに使用するのに十分な性能を
+持っていることが確認出来た。
+
+パケット1KBから100KBまでの差は2倍程度であり、それ以上はパケットサイズに
+リニアに時間がかかる。従って、数十KB程度以下にデータを抑えることは、
+応答時間的には意味がない。
+
+
+--比較
+
+
+本稿ではデバッグを行う為に通常通信とは他に、Metaで通信するMeta Protocol Engineを実装し評価した。
+今回は、スナップショットなどの実際のデバッグ機能を実装することは出来なかった。
+通信の実験においても、
+同クラスタ上で別のRing通信や他のMetaLinda通信等があった場合の干渉の程度
+などを測定する必要があると考えられる。
+
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/presentation/fig	Fri Apr 24 07:49:19 2009 +0900
@@ -0,0 +1,1 @@
+../fig
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/presentation/why.ind	Fri Apr 24 07:49:19 2009 +0900
@@ -0,0 +1,71 @@
+-title: うーん
+
+先生が発表するってどうなの?
+
+しかも二つ続けて。
+
+自分が書いたものだからな〜
+
+自分で書かない論文を発表できるはずもなく
+
+--うーんうーん
+
+先生がプログラミングするってどうよ?
+
+しかも二つ続けて。
+
+自分が書いたものだからな〜
+
+自分で書かないプログラムに関する論文を書けるはずない
+
+テストぐらいは、やって。
+
+--どのあたりが難しい?
+
+	言われたことを行なう(既に書かれたプログラムで実験する)
+
+だいたいこの辺から始める
+
+	それで1年が終ってしまう
+
+先輩の動かしたものを再現できない 
+
+(引き継ぎすることはない...)
+
+	理解できないから書き直そうとする
+
+良くある間違いです
+
+	ゼミの時間に手取り足取りしてプログラムを書く
+
+時間が足りません
+
+	自分一人で書いた方が早い
+
+	それほど仕事しくれるわけでもないので育てても仕方がない
+
+--どのあたりが難しい?
+
+State Pattern は難しいらしい。
+
+	そこで諦める
+
+先生が書いたプログラムには手を出せない(手が出ない)
+
+	Test Driven
+
+Test を通して終り
+
+
+--優秀な学生は優秀です
+
+	使いこなせてないんじゃない?
+
+	提案することはほとんどない
+
+	就活に時間をかける
+
+出来ない学生が就活を卒業より優先するとはまる
+
+	ものには順序と言うものが...
+