% Sample file for the use of compsoft style file.
%
\documentclass[T]{compsoft}

% Preamble
%
% 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
% 巻数，号数，開始ページ，終了ページを指定する．
%\volNoPp{16}{5}{78}{83}

% ワークショップによる推薦論文の場合，ワークショップ名を指定する．
% \suisen{ワークショップ名}

% 特集の場合，特集のタイトルを与える．
% \tokushu{特集のタイトル}

% 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
% 大会の回数は計算される．
\taikai{2011}

% ここに，使用するパッケージを列挙する．
\usepackage[dvips]{graphics}

% ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
% 再定義は原則として避けること．

\begin{document}

% 論文のタイトル
\title{DataSegment API を用いた分散フレームワークの設計}

% 著者
% 和文論文の場合，姓と名の間には半角スペースを入れ，
% 複数の著者の間は全角スペースで区切る
%
\author{赤嶺 一樹, 河野真治
%
% ここにタイトル英訳 (英文の場合は和訳) を書く．
%
\ejtitle{Design of Distributed Application Framework with DataSegment API}
%
% ここに著者英文表記 (英文の場合は和文表記) および
% 所属 (和文および英文) を書く．
% 複数著者の所属はまとめてよい．
%
\shozoku{Kazuki Akamine, Shinji Kono}{琉球大学理工学研究科情報工学専攻}%
{Information Engineering Course, Faculty of Engineering Graduate School of Engineering and Science, University of the Ryukyus}
%
% 出典情報は \shutten とすれば出力される．
%\shutten
%
% 受付年月日，記事カテゴリなどは自動的に生成される．
%\uketsuke{1999}{8}{3}
%
% その他，脚注に入れるものがあれば，\note に記述する．
%\note{脚注に入れる内容}
}

%
% 和文アブストラクト
\Jabstract{%
本研究室では、分散フレームワークとして、 Linda を拡張した FederatedLinda を開発してきた。しかし、分散用の API として、 in/out/read だけでは足りないことが判明した。また、分散 KVS には、 read/write/update といった API があるが、同期する機構は備わっていないため、ゲームなどのリアルタイムプログラム用途にそのまま利用することはできない。
%
そこで、 Linda の待ち合わせ可能な API と一般的な KVS の持つデータベースの API の中間になるような DataSegment API を設計する。本研究室では、その DataSegment API を用いた分散フレームワークを開発する。}
%
% 英文アブストラクト（大会論文には必要なし)
% \Eabstract{}
%
\maketitle

\section{スケーラブルな分散フレームワークの提案}
ブロードバンド環境やスマートフォンなどをはじめとしたモバイル端末の普及により、ネットワークに接続している端末が増えている。それにしたがって、ネットワーク上におけるサービスの巨大化は必至となっている。そこで、サービスのスタートアップ時期には少量のリソースで運用でき、ユーザー数が増える時期には、リソースを追加するのみでサービスの質を維持できるといった、スケーラビリティーを備えたシステムが求められている。そのようなシステムを開発するためには、様々なプロトコルを提案し、実装し、検証していく必要がある。そのため、提案したプロトコルを玩具的に実験できるフレームワークが求められている。
%
本研究室ではこれまでに、 Linda を拡張した FederatedLinda を開発し、スケーラビリティーのあるシステムについて考えてきた。すると、その開発サイクルの中でいくつかの問題点があることが分かった。また、本研究室が開発している、並列フレームワーク Cerium に新しく実装する予定の DataSegment と CodeSegment を用いた並列計算に関するアイディアが、分散アプリケーションにも応用できるのではないかと考えた。上記の理由から、新しい分散フレームワークを提案する。
%
本論文では、 DataSegment と CodeSegment を用いた分散フレームワークに関して提案する。
%

\section{FederatedLinda}
これまでに本研究室では、分散フレームワーク FederatedLinda を提案し、実装してきた。その実装には、以下の通り3段階のレベルがあった。
\subsection{Level. 1}\label{"level1"}



\section{並列更新アルゴリズム}\label{section:update}

本節では，後続の操作をブロックしない${\it update\/}$操作を与える．基本的な
アイデアは，zig-zigとzig-zagの両方について，目標節点をその深さの
半分までしか浮上させない半扁平化(semi-splaying)を用いることである(文献
\cite{ST85}の半扁平化は，zig-zigのみが扁平化と異なっていた)．$x$を更新対
象の節点とすると，アルゴリズムは以下のようになる．
%
% ここでも左右対称な操作の片方のみを述べる．

\begin{itemize}
% \medskip\noindent (a)
\item[(a)]
空の木に対する挿入は図\ref{figure:update}
(a1)の操作，(空でない)木の根に対する更新は
図\ref{figure:update}(a2)の操作を行なう．

% \begin{adjustvboxheight}
\begin{figure*}[t]
\begin{center}
\scalebox{1.00}{\includegraphics{fig3.eps}}
\end{center}
\caption{後続操作をブロックしない更新アルゴリズムの1ステップ}
\label{figure:update}
\end{figure*}
% \end{adjustvboxheight}

% \medskip\noindent (b)
\item[(b)]
zig: 
$x$が左部分木の根である場合は図\ref{figure:update}(b1)
の操作，$x$が存在すべき左部分木が空の
場合は図\ref{figure:update}(b2)の操作を行なう．

% \medskip\noindent (c)
\item[(c)]
zig-zig: 図\ref{figure:update}(c)左の木における$x (<b)$の探索では，
枝$ba$の右回転を行なってアクセスしたパスの長さを1短縮する．次は1レベル
(短縮前の長さでは2レベル)下降して，部分木$A$に対して再帰的に探索を行なう．

% \medskip\noindent (d)
\item[(d)]
zig-zag: 図\ref{figure:update}(d)左の木における節点$x$ ($b<x<a$) の
探索では，
枝$cb$の左回転と，できた枝$ca$の右回転を行ない，
アクセスしたパスを1短縮する．
%
% 二つの中側の部分木の適当な方に対して再帰的に探索を行なう．
%
% \noindent
$x=c$ならばこれで探索終了である．$x<c$ならば2レベル(短縮前の長さでは3レ
ベル)下降して$B$の中から$x$を再帰的に
探索する．$x>c$ならば同様に$C$の中から再帰的に探索する．$x\ge c$の場合には
枝$ca$の回転操作を省略することも考えられる．
%
$b$の右部分木が空の場合は，そこに節点$x$を挿入
したあと，上に述べた回転操作を行なう．

\end{itemize}
% \medskip
以上の操作で，アクセスしたパスの長さは最悪でも約$2/3$になる．
%
半分でなくて$2/3$なのは，上記zig-zag操作の性質によるものである．


\section{並列削除アルゴリズム}\label{section:delete}

並列削除のための基本的な着想は，扁平化操作を，削除すべき節点を下降さ
せるために利用することである．これまでは，扁平化操作はもっぱら，再度アク
セスしそう
な節点を浮上させるために用いられてきた．ここで重要なことは，削除対象の
節点以外は高々${\rm O}(1)$レベルしか下降させないようにすることである．
以下では，$z$を削除対象の節点とする．

まず，根節点が削除対象節点$z$である場合を考える．この場合，zippingと呼ぶ
操作によって
それを``容易に''削除できる場所まで下降させる．節点が``容易に''削除でき
るとは，その左部分木，右部分木，左部分木の右部分木，右部分木の左部分木の
いずれかが空であることである．根節点の下降によって，その左部分木と
右部分木の縫い合せが起きる．
% 
% これが言葉の由来である．

\begin{enumerate}
% \medskip\noindent (a)
\item[(a)]
``容易に''削除できる場合：図\ref{figure:delete}(a1)または(a2)
のように変形する．


% \begin{adjustvboxheight}
\begin{figure*}[t]
\begin{center}
\scalebox{1.00}{\includegraphics{fig4.eps}}
\end{center}
\caption{後続操作をブロックしない削除アルゴリズムの1ステップ}
\label{figure:delete}
\end{figure*}
% \end{adjustvboxheight}

% \medskip\noindent (b)
\item[(b)]
``容易に''削除できない場合：図\ref{figure:delete}(b)のように
zig-zagを施し，そ
の結果できる$b$の右部分木に，(一つめとは左右対称な) zig-zagを施す．

\noindent
4回の回転で$z$は2レベル下降する．$z$の新たな部分木$C$と$F$
は，同じレベルにとどまる．それ以外の節点も高々1レベルしか下降
しない．$z$を根とする新たな部分木に対して再帰的に削除操作を行なうが，$z$の子孫
でない節点がそれによってさらに下降することはない．
\end{enumerate}

% \medskip
図\ref{figure:zipping}に，根節点$z$の削除による木の形状の変化を示す．
\begin{figure*}[t]
\begin{center}
\scalebox{1.00}{\includegraphics{fig5.eps}}
\end{center}
\caption{Zippingによる節点$z$の削除}
\label{figure:zipping}
\end{figure*}

削除対象節点$z$が根であるとは限らない場合は，まず第\ref{section:update}節の
方法で$z$を探索する．これは根から$z$に至るパスを短縮する効果をもつ．つぎ
に，$z$をzippingによって下降させて削除する．

Zipping操作はパスの短縮を行なわないが，アクセスした節点は浮上させ
るという原則にしたがうならば，zippingに先だって，左部分木の最大要素に至
るパスと右部分木の最小要素に至るパスをそれぞれトップダウンの半扁平化
(zig-zig (図\ref{figure:update}(c)) の繰返し)によっ
て短縮すればよい．この短縮化はzippingと並行して行なうことができる．

Zippingは更新操作と異なり，各節点のキー値を読むことなく木を下降する．
またzippingは，木$T_1$と木$T_2$ ($T_1$のど
のキーも，$T_2$のどのキーよりも小さいものとする)とのトップダウン併合操作
にも応用できる．すなわち，新たな節点(キーは任意)を調達し，その左部分木
を$T_1$，右部分木を$T_2$として一つの木を構成した
のち，調達した根節点を消去すればよい．

\section{計算量に関する結果と考察}

効率の二つの尺度のうち，スループットにつ
いては容易に議論ができる．すなわち，二つの操作は，レベル$l$ (根をレ
ベル$0$として)の節点を${\rm O}(l)$回 --- ${\it update\/}$は高々$(l+2)$回，
zippingは高々$(2l+2)$回 ---
の回転操作ののちに確定させる．
さらにどちらの操作も，連続する高々$3$
レベルの節点を同時に施錠するだけでよい．これらのことから，木の大きさや深
さによらないスループットで，操作系列をパイプライン的に並列処理するこ
とができる．

レスポンスは，${\it update\/}$については，通常のスプレー
木と同等の償却計算量をもつことが証明できる．具体的には，
節点$x$の{\bf 大きさ}$s(x)$を$x$を根とする部分木の節点数と定義し，
{\bf ランク}$r(x)$を$\log_2(s(x))$とする．
そして
%
木の{\bf ポテンシャル}を，すべての節点のランクの和と定義する．
すると，${\it update\/}$の償却時間，つまり回転操作の回数で測った所
要時間に操作前後のポテンシャルの変化を加えたものは，$n$を木の節点数とし
て，${\rm O}(\log n)$であることを示すことができる．
このことから，十分長い操作系列の平均レスポンスは，最悪でも対数的であるこ
とがわかる．
文献\Cite{ST85}のよう
に，節点に異なる重みをつけて$s$や$r$を定義することにより，より強い性質
を示すこともできるが，本論文では省く．

一方，${\it delete\/}$については，文献\Cite{ST85}の解析方法では，対
数的償却計
算量を導くことはできない．そのことを示すために，図\ref{figure:delete}
(b)の4回の回転によるポテンシャル変化を考える．

図\ref{figure:delete}(b)の一番右側
の木のランク関数を$r'$とする．一番左側の木からのポテンシャルの変化を，
$k$をある正定数として$k(r'(b)-r'(z))$以内に押さえることができることを示すのが，
文献\Cite{ST85}における償却計算量の証明技法の基本であった．しかし，
これらの木に
ついて$s(A)= s(B) = s(C) = h\gg t = s(D) = s(E) = s(F)$
を仮定すると，ポテンシャル変化が$h/t$に関して${\rm O}(\log
(h/t))$となる．一方$r'(b)-r'(z)$は$h/t$に関して${\rm O}(1)$であるので，
上記の要請を満たす
$k$は存在しないことがわかる．Zippingに先立ってパス短縮化を行なっ
た場合についても，同様のことが示せる．

しかし，第\ref{section:delete}節の削除操作は，
%
アクセスしたパス上の節点の深さが約半分になり(事前にパス
短縮化を施した場合)，それ以外の節点も高々定数レベルしか沈まない
%
という，節点の浮き沈みについてのスプレー木一般の性質は満たしている．
%
では一般に，この二つの性質を満たす自己調整的な木アルゴリズムで，平均レス
ポンスが対数時間で押さえられないような，十分長い操作系列は存在す
るのだろうか？ これは未解決であるが，本論文で提案した二操作に
ついては，平均レスポンスは少なくとも${\rm O}(\sqrt n)$ (更新のみならば
${\rm O}(\log n)$)と予想される．

その根拠
として，各節点の削除しやすさの変化を考える．
節点$x$の{\bf 削除困難度}$d(x)$を，$x$からその直前のキー$x_-$をもつ節
点へ至るパス長($x_-$が存在しない場合や，$x_-$が$x$の子孫で
ない場合は$0$と定める)と直後のキー$x_+$をもつ節に至るパス長の最小値
と定めると，第\ref{section:delete}節の
${\it delete\/}$は，$d$の大きな節点の消去には時間がかかるも
のの，残った各節点の$d$を高々${\rm O}(1)$
しか大きくしない．また第\ref{section:update}節の
${\it update\/}$で新たに挿入した節点の$d$
は$0$であり，${\it update\/}$はすでに存在していた各節点の$d$も高々${\rm
O}(1)$しか大きくしない．(ボトムアップ扁平化における節点の$d$の増加は，定数で
押えることができない．)これらのことから
%
\begin{enumerate}
\item[1.]
新たな節点の$d$の値が$k$まで成長するには，他の節点の$\Omega(k)$
回の挿入削除が必要
\end{enumerate}
%
であることがわかる．さらに
%
\begin{enumerate}
\item[2.]
二分木における各節点の$d$の総和は，
木をトラバースしたときに通る枝の延べ本数を上回ることはないから
${\rm O}(n)$
\end{enumerate}
%
である．1.と2.から，
新たな節点の挿入と，$d$の大きな節点の消去が繰り返されるという最悪の操作
系列を考えても，操作の平均の手間は${\rm O}(\sqrt n)$であり，実用上の効率
は更新操作のみの場合とほとんど変わらないと予想される．

\section{まとめと今後の課題}

節点の浮き沈みに関する望ましい性質を保ち，かつ計算量の意味で最適なスルー
プットをもつ自
己調整二分木の並列操作(更新，挿入，削除，併合)アルゴリズムを提案した．節点の
更新や挿入に関して
は対数的償却計算量を持つことが証明できており，さらにアクセスパターンの偏
りや変化に対する追従性など，スプレー木の持つ強力かつ頑健な性質
の多くを引き継いでいる．削除の償却計算量のより良い理論的限界を導く(また
はその不存在を示す)ことは今
後の課題である．また，アルゴリズムの実際的効率，並列分散環境での実装，応
用の検討も今後の課題である．


{\bf 謝辞}\
本論文の初期の版について議論していただいたRobert Tarjan氏(Princeton大)，
毛受哲氏(NEC)，中谷祐介氏(早稲田大)に感謝する．
%
\begin{adjustvboxheight} % needed only when Appendix follows
\begin{thebibliography}{99}
\bibitem{LS86} Lanin, V. and Shasha, D.：A Symmetric Concurrent B-Tree
Algorithm,
Proc.\ 1986 Fall Joint Computer Conference, IEEE, 1986, pp.~380--389．

\bibitem{ST85} Sleator, D. D. and Tarjan, R. E.：Self-Adjusting Binary Search
Trees, {\it J. ACM}, Vol.~32, No.~3 (1985), pp.~652--686．

\bibitem{S89} Shapiro E.：The Family of Concurrent Logic Programming Languages.
{\it ACM Computing Surveys}, Vol.~21, No.~3 (1989), pp.~413--510．

\bibitem{T85} Tarjan, R. E.：Amortized Computational Complexity, {\it
SIAM J.\ Alg.\ Disc.\ Math.}, Vol.~6, No.~2 (1985), pp.~306--318.

\bibitem{W90} 和田久美子：スプレイ木の並列データ探索, Proc.\ KL1
Programming Workshop '90, Tokyo, ICOT, 1990, pp.~42--49．
\end{thebibliography}
\end{adjustvboxheight} % needed only when Appendix follows

\appendix
\section{付録: \LaTeX による論文作成のガイド} 

ここに，以前の \verb|sample.tex| では，論文作成のガイドがあったが，
その内容は \verb|guide.tex| に移動した．

\end{document}