\documentclass[submit,techrep,noauthor]{ipsj}

% \documentclass[submit]{ipsj}
%\documentclass{ipsj}

\usepackage[dvipdfmx]{graphicx}
\usepackage{ascmac}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{url}
\usepackage{listings, jlisting}
\usepackage{enumitem}
\usepackage{caption}

\lstset{
    language=C, 
    tabsize=2, 
    frame=single, 
    basicstyle={\ttfamily\footnotesize},% 
    identifierstyle={\footnotesize},% 
    commentstyle={\footnotesize\itshape},% 
    keywordstyle={\footnotesize\bfseries},% 
    ndkeywordstyle={\footnotesize},% 
    stringstyle={\footnotesize\ttfamily}, 
    breaklines=true, 
    captionpos=t, 
    columns=[l]{fullflexible},% 
    xrightmargin=0zw,% 
    xleftmargin=1zw,% 
    aboveskip=1zw, 
    numberstyle={\scriptsize},% 
    stepnumber=1, 
    numbersep=0.5zw,% 
    lineskip=-0.5ex, 
}
\renewcommand{\lstlistingname}{Code}


\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\|{\verb|}

\setcounter{巻数}{59}
\setcounter{号数}{1}
\setcounter{page}{1}


\受付{2019}{5}{9}
%\再受付{2015}{7}{16}   %省略可能
%\再再受付{2015}{7}{20} %省略可能
%\再再受付{2015}{11}{20} %省略可能
\採録{2019}{5}{9}

\makeatletter



\begin{document}


\title{分散フレームワークChristieによるBlock chainの実装}

\etitle{Implementing Block chain using Distributed Computing Framework Christie}


\paffiliate{IPSJ}{琉球大学工学部情報工学科\\
Information Engineering, University of the Ryukyus.}
 

\author{一木 貴裕}{Takahiro Itsuki}{IPSJ}
%\author{赤堀貴一}{Ki-ichi Akahori}{IPSJ}
\author{河野 真治}{Shinji KONO}{IPSJ}


\begin{abstract}
当研究室で開発した分散フレームワークChristieを用いて，
Etherium を参考にBlock chainを実装した．
Paxos のリーダ選出アルゴリズムと，Christieの持つTopology Managerとの相性が問題になる．
Gears OSのファイルシステムなどに使えるかどうかの調査を行う．
\end{abstract}

\maketitle

\begin{jkeyword}
分散計算，ブロックチェーン
\end{jkeyword}

\begin{eabstract}
A Block chain is implemented using our distributed computation framework Christie.
It is based on Etherium. Leader selection algorithm such as Paxos should be
incorporated with Christies' Topology manager. We investigate a possiblities
of using Block chain in Gears OS's distributed file systems.
\end{eabstract}

\begin{ekeyword}
Distributed Computation, Block chain
\end{ekeyword}

\maketitle

%1
\section{Block Chain と Gears OS}

コンピュータのデータに不整合は起こり得る．不整合は誤操作や，複数人によるデータの同時書き込みによって起こる.
特に分散環境下で問題になる．
ブロックチェーンはデータを分散でき， 不整合の検知が可能な仕組みを提供していう．
当研究室で開発中のGearsOSの分散ファイルシステムの技術として，ブロックチェーンが使用できるかどうかを調査中である．
そのために当研究室ではJava上で開発された分散フレームワーク
Christieにブロックチェーンを実装することにした．


\section{Chrsitie}
%\subsection{Christieとは}
Christieは当研究室で開発している分散フレームワークである．
Christieは当研究室で開発しているGearsOSに組み込まれる予定がある．
GearsOSとは同様に当研究室で開発しており，言語Continuation based CによってOSそのものとアプリケーションを記述する．%GearsOSとは
そのためGearsOSを構成する言語CbCと似た概念がある．
Christieに存在する概念として次のようなものがある．
\begin{itemize}
\item CodeGear(以下 CG)
\item DataGear(以下 DG)
\item CodeGearManager(以下 CGM)
\item DataGearManager(以下 DGM)
\end{itemize}
CGはクラス，スレッドに相当し，Javaの継承を用いて記述する．
DGは変数データに相当し，CG内でアノテーションを用いて変数データを取り出せる．
CGMはノードであり，DGM，CG，DGMを管理する．

DS Manager(以下DSM)にはLocal DSMとRemote DSMが存在する．Local DSMは各ノード固有のデータベースである．

Remote DSMは他ノードのLocal DSMに対応するproxyであり，接続しているノードの数だけ存在する(図 \ref{fig:RemoteDSM} )．
他ノードのLocal DSMに書き込みたい場合はRemote DSMに対して書き込めば良い．

\newpage

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=8cm]{images/remote_datasegment.pdf}
    \end{center}
    \caption{Remote DSMは他のノードのLocal DSMのproxy }
\label{fig:RemoteDSM}
\end{figure}


Remote DSMを立ち上げるには，DataSegmentクラスが提供するconnectメソッドを用いる．
接続したいノードのipアドレスとport番号，そして任意のManager名を指定することで立ちあげられる．
その後はManager名を指定してData Segment APIを用いてDSのやり取りを行うため，プログラマはManager名さえ
意識すればLocalへの操作もRemoteへの操作も同じ様に扱える．



 
DGMはDGを管理するものであり，putという操作により変数データ，すなわちDGを格納できる．
DGMのput操作を行う際にはLocalとRemoteと2つのどちらかを選び，変数のkeyとデータを引数に書く．
Localであれば，LocalのCGMが管理しているDGMに対し，DGを格納していく．
Remoteであれば接続したRemote先のCGMのDGMにDGを格納できる．
put操作を行った後は，対象のDGMの中にqueとして補完される．
DGを取り出す際には，CG内で宣言した変数データにアノテーションをつける．
DGのアノテーションにはTake，Peek，TakeFrom，PeekFromの4つがある．


\begin{description}
\item[Take] 先頭のDGを読み込み，そのDGを削除する．DGが複数ある場合，この動作を用いる．
\item[Peek] 先頭のDGを読み込むが，DGが削除されない．そのため，特に操作をしない場合は同じデータを参照し続ける．
\item[TakeFrom(Remote DGM name)] Takeと似ているが，Remote DGM nameを指定することで，その接続先(Remote)のDGMからTake操作を行える．
\item[PeekFrom(Remote DGM name)] Peekと似ているが，Remote DGM nameを指定することで，その接続先(Remote)のDGMからPeek操作を行える．
\end{description}
  

%\subsection{プログラミングの例}
ここでは，Christieで実際にプログラムを記述する例を述べる．
CGMを作り，setup(new CodeGear)を動かすことにより，DGを持ち合わせ，DGが揃った場合にCodeGearが実装される．
CGMを作る方法はStartCodeGear(以下SCG)を継承したものからcreate-CGM(port)methodを実行することによりCGMが作られる．
SCGのコードの例をソースコード\ref{code:StartHelloWorld}に示す．%refを使う

\lstinputlisting[label=code:StartHelloWorld ,caption={\footnotesize StartHelloWorld}]{src/HelloWorld/StartHelloWorld.java}

\section{Annotation}

ChristieではInput DG の指定にはアノテーションを使う．
アノテーションとは，クラスやメソッド，パッケージに対して付加情報を記述できるJavaのMeta Computationである．
先頭に@をつけることで記述でき，オリジナルのアノテーションを定義することもできる．
Inputとなる型の変数を直接宣言し，変数名としてkeyを記述する．
そして，その宣言の上にアノテーションでTakeまたはPeekを指定する(ソースコード\ref{src:takeex})．

\lstinputlisting[label=src:takeex, caption=T]{src/christie/InputDG.java} 


アノテーションで指定したInputDGは，CGを生成した際にCodeGear.class内で待ち合わせの処理が行われる．
これにはJavaのreflectionAPIを利用しており， アノテーションと同時に変数名も取得できるため，変数名によるkey指定が実現した．

Christieのこのインプットアノテーションはフィールドに対してしか記述できないため，keyの指定とTake/Peekの指定を必ず一箇所で書くことが明確に決まっている．
これにより，外のCSからのkeyへの干渉をされることがなり，key の指定が複数の CG に分散することがない．
また，keyを変数名にしたことで，動的なkeyの指定や，keyと変数名の不一致による可読性の低下を防ぐことができた．

リモートノードに対してTake/Peekする際は，TakeFrom/PeekFromのアノテーションを用いる(ソースコード\ref{src:remotetake})．

\lstinputlisting[label=src:remotetake, caption=TakeFromの例]{src/christie/RemoteInputDG.java}

Christie は通信の際にDGを圧縮することができる．
圧縮のMeta Computationを
指定する際にDGM名の前にcompressedをつけることができる．(ソースコード\ref{src:compresslocal})．

\lstinputlisting[label=src:compresslocal, caption=Remoteから圧縮して受け取る例]{src/christie/CompressLocal.java}

ChristieではInput DGは直接変数を宣言されているので，
他の場所を辿らなくともCGを見るだけでインプットされるデータの型が分かるようになっている．
ソースコード\ref{src:getdata}はInputDGのデータを扱うである．

\lstinputlisting[label=src:getdata, caption=InputDGを扱う例]{src/christie/GetData.java}

InputDGとして宣言した変数の型は，reflectionAPIにより内部で保存され，リモートノードと通信する際も適切な変換が行われる．
このようにプログラマが指定しなくとも正しい型で取得できるため，プログラマの負担を減らし信頼性を保証することができる．


\section{TopologyManager}

TopologyManagerとは，Topologyを形成するために，参加を表明したノード，TopologyNodeに名前を与え，必要があればノード同士の配線も行うコードである．
TopologyManagerのTopology形成方法として，静的Topologyと動的Topologyがある．
静的Topologyはコード\ref{code:dot-example}のようなdotファイルを与えることで，ノードの関係を図\ref{fig:dot-example}のようにする．
静的Topologyはdotがいるのノード数と同等のTopologyNodeがあって初めて，CodeGearが実行される．
 
 \lstinputlisting[caption=ring.dot, label=code:dot-example]{src/ring.dot}
 

\begin{figure}[ht]
\includegraphics[width=120pt]{images/ring.pdf}
\caption{ring.dotを図式化したもの}
\label{fig:dot-example}
\end{figure}
 動的Topologyは参加を表明したノードに対し，動的にノード同士の関係を作る．例えばTreeを構成する場合，参加したノードから順に，rootに近い位置の役割を与える．また，CodeGearはノードが参加しmparentに接続された後に実行される．
 

%2
\section{ブロックチェーンのトランザクション}
%2.1
%\subsection{P2P (Peer-to-Peer)}			
ブロックチェーンはP2Pにてネットワーク間が動作している，つまり．ブロックチェーンネットワークにはサーバー，クライアントの区別がなく，全てのノードが平等である．そのため，非中央時にデータの管理をおこなう．

ブロックチェーンにおけるブロックは，複数のトランザクションをまとめたものである．
ブロックの構造は使用するコンセンサスアルゴリズムによって変わるが，基本的な構造としては次のとおりである．
\begin{itemize}
\item BlockHeader
\begin{itemize}
\item previous block hash
\item merkle root hash
\item time
\end{itemize}
\item TransactionList
\end{itemize}

BlockHeaderには，前のブロックをハッシュ化したもの，トランザクションをまとめたmerkle treeのrootのhash，そのブロックを生成したtimeとなっている．
previous block hashは，前のブロックのパラメータを選べてhash化したものである．
それが連なっていることで図\ref{hashchain}のようなhash chainとして，ブロックがつながっている．%図はrefで


\begin{figure}[ht]
\begin{center}
\includegraphics[width=240pt]{images/chain.pdf}
\caption{ブロックチェーンの図}
\label{hashchain}
\end{center}
\end{figure}

そのため，一つのブロックが変更されれば，その後につながるブロック全てを更新しなければいけなくなる．
ブロックが生成された場合，知っているノードにそのブロックをブロードキャストする．
実際には通信量を抑えるためにブロックを送った後，ブロックをシリアライズして送信する場合もある．% ブロック高はタイポ?

ノードごとにブロックを検証し，誤りがあればそのブロックを破棄し，誤りがなければ更にそのノードがブロックをブロードキャストする．
そして，Transaction PoolというTransactionを貯めておく場所から，そのブロックに含まれているTransactionを削除し，新しいブロックを生成する．

%\begin{quote}
%\small
%\|http://www.ipsj.or.jp/journal/submit/style.html|
%\end{quote}

%\subsection{トランザクションとその構造}
トランザクションとはデータのやり取りを行った記録の最小単位である．
トランザクションの構造は次のとおりである．
\begin{description}
\item[TransactionHash] トランザクションをハッシュ化したもの．
\item[data] データ．
\item[sendAddress] 送り元のアカウントのアドレス．
\item[recieveAddress] 送り先のアカウントのアドレス．
\item[signature] トランザクションの一部と秘密鍵をSHA256でハッシュ化したもの． ECDSAで署名している．
\end{description}

トランザクションはノード間で伝搬され，ノードごとに検証される．
そして検証を終え，不正なトランザクションであればそのトランザクションを破棄し，検証に通った場合はTransaction Poolに取り組まれ，また検証したノードからトランザクションがブロードキャストされる．

\section{Proof of Workを用いたコンセンサス}

%\subsection{fork}
ブロックの生成をした後にブロードキャストをすると，ブロック高の同じ，もしくは相手のブロック高の高いブロックチェーンにたどり着く場合がある．
当然，相手のブロックチェーンはこれを破棄する．
しかしこの場合，異なるブロックを持った2つのブロックチェーンをこの状態をforkと呼ぶ．
fork状態になると，2つの異なるブロックチェーンができることになるため，一つにまとめなければならない．
１つにまとめるためにコンセンサスアルゴリズムを用いるが，コンセンサスアルゴリズムについては次章で説明する．

%\section{Proof of Workを用いたコンセンサス}
ブロックチェーンでは，パブリックブロックチェーンの場合とコンソーシアムブロックチェーンによってコンセンサスアルゴリズムが変わる．
この章ではパブリックブロックチェーンのBitcoin，Ethereumに使われているProof of Workとコンソーシアムブロックチェーンに使えるPaxosを説明する．

%\subsection{Proof of Workを用いたコンセンサス}
パブリックブロックチェーンとは，不特定多数のノードが参加するブロックチェーンシステムのことをさす．
よって，不特定多数のノード間，全体のノードの参加数が変わる状況でコンセンサスが取れるアルゴリズムを使用しなければならない．
Proof of Workは不特定多数のノードを対象としてコンセンサスが取れる．
ノードの計算量によってコンセンサスを取るからである．
次のような問題が生じてもProof of Workはコンセンサスを取ることができる．

\begin{enumerate}
\item プロセス毎に処理の速度が違う．つまり， メッセージの返信が遅い可能性がある
\item 通信にどれだけの時間がかかるかわからず， その途中でメッセージが失われる可能性がある， 
\item プロセスは停止する可能性がある．また， 復旧する可能性もある．
\item 悪意ある情報を他のノードが送信する可能性がある．
\end{enumerate}
Proof of Workに必要なパラメータは次のとおりである．

\begin{itemize}
\item nonce
\item difficulty
\end{itemize}
nonceはブロックのパラメータに含まれる．
difficultyはProof of Workの難しさ，正確にいえば１つのブロックを生成する時間を調整している．Proof of Workはこれらのパラメータを使って次のようにブロックを作る．

\begin{enumerate}
\item ブロックとnonceを加えたものをハッシュ化する．この際， nonceによって， ブロックのハッシュは全く違うものになる．
\item ハッシュ化したブロックの先頭から数えた0ビットの数がdifficultyより多ければ， そのブロックにnonceを埋め込み， ブロックを作る．
\item 2の条件に当てはまらなかった場合はnonceに1を足して， 1からやり直す．
\end{enumerate}
difficulty = 2でProof of Workの手順を図にしたものを図\ref{pic:proof}に示す．%refで

\begin{figure}[ht]
\includegraphics[width=240pt]{images/proof-of-work.pdf}
\caption{Proof of Workの手順}
\label{pic:proof}
\end{figure}

2の条件については，単純に(桁数 - difficulty + 1) * 10 $>$ hash とも置き換えることができる．
nonceを変えていくことで，hashはほぼ乱数のような状態になる．
つまり，difficultyを増やすほど，条件に当てはまるhashが少なくなっていくことがわかり，
そのhashを探すための計算量も増えることがわかる．
これがProof of Workでブロックを生成する手順となる．
これを用いることによって，ブロックが長くなるほど， すでに作られたブロックを変更することは計算量が膨大になるため，
不可能になっていく．Proof of Workでノード間のコンセンサスを取る方法は単純で， ブロックの長さの差が一定以上になった場合に
長かったブロックを正しいものとする．これを図で示すと\ref{コンセンサス}のようになる．

\begin{figure}[ht]
\begin{center}
\includegraphics[width=240pt]{images/proof-of-work-fork.pdf}
\caption{Proof of Workのコンセンサス}
\label{コンセンサス}
\end{center}
\end{figure}

計算量の差が51\%以上になると，forkしたブロック同士で差が生まれる．
それによってIPアドレスでのコンセンサではなく， CPUの性能によるコンセンサスを取ることができる．

コンセンサスでは， ブロックとの差が大きければ大きいほど， コンセンサスが正確に取れる．
しかし，正しいチェーンが決まるのに時間がかかる．
そのため， コンセンサスに必要なブロックの差はコンセンサスの正確性と時間のトレードオフになっている．

この方法でコンセンサスを取る場合の欠点を挙げる．
\begin{itemize}
\item CPUのリソースを使用する．
\item Transactionが確定するのに時間がかかる．
\end{itemize}

\section{Paxos}

コンソーシアムブロックチェーンは許可したのノードのみが参加できるブロックチェーンである．
そのため， ノードの数も把握できるため，Paxosを使うことができる．
Paxosはノードの多数決によってコンセンサスを取るアルゴリズムである．ただし， Paxosは次のような問題があっても値を一意に決めることができる．
\begin{enumerate}
\item プロセス毎に処理の速度が違う．つまり， メッセージの返信が遅い可能性がある
\item 通信にどれだけの時間がかかるかわからず， その途中でメッセージが失われる可能性がある
\item プロセスは停止する可能性がある．また， 復旧する可能性もある
\end{enumerate}
Proof of Workにある特性の4がないが， コンソーシアムブロックチェーンは3つの問題を解決するだけで十分である．
何故ならば，コンソーシアムブロックチェーンは許可したノードのみが参加可能だからである．つまり， 悪意あるノードが参加する可能性が少ないためである．
Paxosは3つの役割ノードがある．

\begin{description}
\item[proposer] 値を提案するノード．
\item[acceptor] 値を決めるノード．
\item[learner] acceptorから値を集計し，過半数以上のacceptorが持っている値を決める．
\end{description}
Paxosのアルゴリズムの説明の前に，定義された用語の解説をする．いかにその用語の定義を示す．

\begin{description}
\item[提案] 提案は，異なる提案ごとにユニークな提案番号と値からなる．提案番号とは， 異なる提案を見分けるための識別子であり単調増加する．
値は一意に決まってほしいデータである．
\item[値(提案)がacceptされる] acceptorによって値(提案)が決まること
\item[値(提案)が選択(chosen)される] 過半数以上のacceptorによって， 値(提案)がacceptされた場合， それを値(提案)が選択されたと言う
\end{description}

paxosのアルゴリズムは2フェーズある．
1つ目のフェーズ， prepare-promiseは次のような手順で動作する．

1フェーズ目を図にしたものを図\ref{PoW}に示す．

\begin{figure}[ht]
\begin{center}
\includegraphics[width=240pt]{images/prepare-promise.pdf}
\caption{prepare-promise}
\label{PoW}
\end{center}
\end{figure}


2つ目のフェーズ，accept-acceptedは次のような手順で動作する．
\begin{enumerate}
\item proposerは過半数のacceptorから返信が来たならば，次の提案をacceptorに送る．これをacceptリクエストという．
\begin{enumerate}
\item もし，約束のみが返ってきているならば，任意の値vをprepareリクエストで送った提案に設定する．
\item もし，acceptされた提案が返ってきたら，その中で最大の提案番号を持つ提案の値v'をprepareリクエストで送った提案の値として設定する．
\end{enumerate}

\item acceptorはacceptリクエストが来た場合，Promiseした提案よりもacceptリクエストで提案された提案番号が低ければ，その提案を拒否する．それ以外の場合はacceptする．
\end{enumerate}
２フェーズ目を図にしたものを図\ref{aa}に示す．

\begin{figure}[ht]
\begin{center}
\includegraphics[width=240pt]{images/accept-accepted.pdf}
\caption{accept-accepted}
\label{aa}
\end{center}
\end{figure}

このアルゴリズムによって，各acccepterごとに値が一意の決まる．値を集計，選択するのはLearnerの役割である．Learnerが値を集計する方法には2つの方法である．

\begin{enumerate}
\item Acceptorによって値がacceptされた時に，各Learnerに送信される．ただし，Message通信量が，Acceptorの数 times Learnerの数になる．
\item 1つのLearnerが各Learnerに選択された値を送信する．1の方法に比べてMessage通信量が少なくなる(Acceptorの数 + Learnerの数になる)代わりに，そのLearnerが故障した場合は各LearnerがMessageを受け取れない．
\end{enumerate}

2つの方法はメッセージ通信量と耐障害性のトレードオフになっていることがわかる．
Paxosでコンセンサスを取ることは，Proof of Workと比較して次のようなメリットがある．

\begin{itemize}
\item CPUのリソースを消費しない
\item Transactionの確定に時間がかからない．
\end{itemize}

%\subsection{Paxosによるブロックチェーン}
PaxosはProof of Workと比べ，CPUのリソースを消費せず，Transactionの確定に時間がかからない．
そのため，Paxosでブロックのコンセンサスを取るブロックチェーンを実装することにはメリットがある．
また，Paxos自体がリーダー選出に向いているアルゴリズムである．
そのため，リーダーを決め，そのノードのブロックチェーンの一貫性のみを考えることもできる．

\section{Chrisiteにおけるブロックチェーンの実装の利点と欠点}


Christieにおいてブロック，トランザクション，Paxos，Proof of Workを実装した．
その際，Christieで実装した場合には以下のような利点がある．

\begin{itemize}
\item データの取り出しが簡単．ChristieはDataGearという単位でデータを保持する．そのため，ブロックやトランザクションはDataGearに包めばいいため，どう送るかという問題を考えなくてすむ．
\item TopologyManagerでのテストが便利．dotファイルが有れば，TopologyManagerが任意の形でTopologyを作れる．そのため，ノードの配置については理想の環境を作れるため，理想のテスト環境を作ることができる．
\item 機能ごとにファイルが実装できるため，見通しが良い．ChristieはCbCのgotoと同じように関数が終わるとsetupによって別の関数に移動する．そのため自然に機能ごとにファイルを作るため，見通しが良くなる．
\end{itemize}

一方で，Christie には以下の問題点があることがわかった．

\begin{itemize}
\item デバッグが難しい．cgm.setupでCodeGearが実行されるが，keyの待ち合わせで止まり，どこのCGで止まっているかわからないことが多かった．
例えば， putするkeyのスペルミスでコードの待ち合わせが起こり，CGが実行されず，エラーなども表示されずにwaitすることがある．その時に，どこで止まっているか特定するのが難しい．
\item TakeFrom，PeekFromの使い方が難しい．TakeFrom，PeekFromは引数でDGM nameを指定する．しかし，DGMの名前を静的に与えるよりも，動的に与えたい場合が多かった．
\item Takeの待ち合わせでCGが実行されない．2つのCGで同じ変数をTakeしようとすると，setupされた時点で変数がロックされる．このとき， 片方のCGはDGがすべて揃っているのに，すべての変数が揃っていないもう片方のCGに同名の変数がロックされ， 実行されない場合がある．
\end{itemize}

\section{実験}
本研究室では， 実際にコンセンサスアルゴリズムPaxosをPC上に分散環境を実装して検証した．
分散環境場で動かすため，JobSchedulerの一種であるTorque Resource Manager(Torque)を使用した．

%\subsection{Torqueとは}
PCクラスタ上でプログラムの実験を行う際には，他のプログラムとリソースを取り合う懸念がある．
それを防ぐためにTorqueを使用する．
Torqueはjobという単位でプログラムを管理しリソースを確保できたら実行する．
jobはqsubというコマンドを使って，複数登録することができる．

また， 実行中の様子もqstatというコマンドを使うことで監視ができる．
Torqueには主に3つのNodeの種類がある．

\begin{description}
\item[Master Node] pbs\_serverを実行しているノード．他のノードの役割とも併用できる．
\item[Submit/Interactive Nodes] クライアントがjobを投入したり監視したりするノード．qsubやqstatのようなクライアントコマンドが実行できる．
\item[Computer Nodes] 投入されたjobを実際に実行するノード． pbs\_momが実行されており，それによってjobをstart，kill，管理する．
\end{description}

今回は図\ref{fig:kvm}のように，KVM上にMaster Node， Submit/Interactive Nodeの役割を持つVM1台と，Computer Nodesとして15台のVMを用意し，jobの投入を行なった．

\begin{figure}[ht]
\includegraphics[width=240pt]{images/kvm.pdf}
\caption{実験環境}
\label{fig:kvm}
\end{figure}

jobはシェルスクリプトの形で与えることができる．ソースコード\ref{code:torque-example}を例として挙げる．

\lstinputlisting[caption=torque-example.sh,label=code:torque-example]{./src/torque-example.sh}

このスクリプトでは，ノード数10(vm0からvm9まで)，jobの名前を「ExampleJob」という形で実行する設定をしている．もし， このコードを投入した場合，Submit/Interactive Nodesが各vmにsshし，hostnameコマンドを実行する．
実行後はstdout，stderrorの出力を「job名.o数字」， job名.e数字」というファイルに書き出す．

%\subsection{PCクラスタ上でのPaxosの実際の動作}
PCクラスタ上で実際にPaxosを動かした際の解説をする．
今回は単純化し，proposerの数を2，accepterの数を3，learnerの数を1としてPaxosを動かし，値が一意に決まる過程を見る．
実験の単純化の為に，提案の数値を整数とし，各processerごとに異なった値とした．
正確には，「proposer + 数字」の部分を値とし，コンセンサスを取るようにした．実際にPaxosを動かし，シーケンス図で結果を示したものが図\ref{fig:paxos}である． 

\begin{figure}[ht]
\includegraphics[width=20cm]{images/paxos1.pdf}
\caption{Paxos動作を表したシーケンス図}
\label{fig:paxos}
\end{figure}

一意の値を決めることができており，また，Learnerが値を選択した後でも，Paxosは常に決めた値を持ち続けるアルゴリズムである．ログの出力では提案番号がより大きいものの提案まで続いていたが，値がこれ以上覆らなかった．
今回はわかりやすいよう値を数字で行なった実験であるが，これをタランザクション，ブロックに応用することで，ブロックチェーンにおけるコンセンサス部分を完成させることができる．

% \section{計測実験}
\section{まとめ}


Paxos の動作は確認したが，計測実験を行うには至っていない．トランザクションの速度がノード数にどのように
影響されるのかを調べる必要がある．

Christie のToplogy Manager は実験するノードの設定を行う集中制御ノードであり，本来集中制御部分を持たない
ブロックチェーンとの相性は良くない．　しかし，分散ファイルシステム等の用途の場合は Topology Manager の
ような方法の方がノードの管理が可能な利点がある．

今後は実装を進め，Gears OSでのファイルシステムへの応用などを考えていきたい．

\begin{thebibliography}{9}
\bibitem{aka}赤堀 貴一，河野真治 : \textbf{Christieによるブロックチェーンの実装}．琉球大学工学部情報工学科卒業論文 2019.
\bibitem{latex}照屋 のぞみ，河野真治 : \textbf{分散フレームワークChristieの設計}．琉球大学理工学研究科修士論文 2018.
\label{teru}
\end{thebibliography}
 
\end{document}