# HG changeset patch # User ichikitakahiro # Date 1557324295 -32400 # Node ID 3bd2dd2fc9049d6501a1f2ade10a272e8ab2c0d2 # Parent 6819a4bd652897d2937d90ed02b82989bdbf14bd write ~PCcluster diff -r 6819a4bd6528 -r 3bd2dd2fc904 paper/sigos.pdf Binary file paper/sigos.pdf has changed diff -r 6819a4bd6528 -r 3bd2dd2fc904 paper/sigos.tex --- a/paper/sigos.tex Wed May 08 20:31:17 2019 +0900 +++ b/paper/sigos.tex Wed May 08 23:04:55 2019 +0900 @@ -116,10 +116,10 @@ %2 \section{ブロックチェーンについて} %2.1 -\section{P2P (Peer-to-Peer)} +\subsection{P2P (Peer-to-Peer)} ブロックチェーンはP2Pにてネットワーク間が動作している,つまり.ブロックチェーンネットワークにはサーバー,クライアントの区別がなく,全てのノードが平等である.そのため,非中央時にデータの管理をおこなう. -\section{ブロックとその構造} +\subsection{ブロックとその構造} ブロックチェーンにおけるブロックは,複数のトランザクションをまとめたものである.ブロックの構造はしようするコンセンサスアルゴリズムによって変わるが,基本的な構造としては次のとおりである. \begin{itemize} \item BlockHeader @@ -150,7 +150,7 @@ %\|http://www.ipsj.or.jp/journal/submit/style.html| %\end{quote} -\section{トランザクションとその構造} +\subsection{トランザクションとその構造} トランザクションとはデータのやり取りを行った記録の最小単位である. トランザクションの構造は次のとおりである. \begin{description} \item[TransactionHash] トランザクションをハッシュ化したもの. @@ -162,13 +162,13 @@ トランザクションはノード間で伝搬され,ノードごとに検証される.そして検証を終え,不正なトランザクションであればそのトランザクションを破棄し,検証に通った場合はTransaction Poolに取り組まれ,また検証したノードからトランザクションがブロードキャストされる. -\section{fork} +\subsection{fork} ブロックの生成をした後にブロードキャストをすると,ブロック高の同じ,もしくは相手のブロック高の高いブロックチェーンにたどり着く場合がある.当然,相手のブロックチェーンはこれを破棄する.しかしこの場合,異なるブロックを持った2つのブロックチェーンをこの状態をforkと呼ぶ.fork状態になると,2つの異なるブロックチェーンができることになるため,一つにまとめなければならない.１つにまとめるためにコンセンサスアルゴリズムを用いるが,コンセンサスアルゴリズムについては次章で説明する. \section{Proof of Workを用いたコンセンサス} ブロックチェーンでは,パブリックブロックチェーンの場合とコンソーシアムブロックチェーンによってコンセンサスアルゴリズムが変わる.この章ではパブリックブロックチェーンのBitcoin,Ethereumに使われているProof of Workとコンソーシアムブロックチェーンに使えるPaxosを説明する。 -\section{Proof of Workを用いたコンセンサス} +\subsection{Proof of Workを用いたコンセンサス} パブリックブロックチェーンとは,不特定多数のノードが参加するブロックチェーンシステムのことをさす。よって,不特定多数のノード間,全体のノードの参加数が変わる状況でコンセンサスが取れるアルゴリズムを使用しなければならない.Proof of Workは不特定多数のノードを対象としてコンセンサスが取れる.ノードの計算量によってコンセンサスを取るからである.次のような問題が生じてもProof of Workはコンセンサスを取ることができる. \begin{enumerate} @@ -216,7 +216,7 @@ \item Transactionが確定するのに時間がかかる. \end{itemize} -\section{Paxos} +\subsection{Paxos} コンソーシアムブロックチェーンは許可したのノードのみが参加できるブロックチェーンである.そのため,ノードの数も把握できるため,Paxosを使うことができる.Paxosはノードの多数決によってコンセンサスを取るアルゴリズムである.ただし,Paxosは次のような問題があっても値を一意に決めることができる. \begin{enumerate} \item プロセス毎に処理の速度が違う. つまり, メッセージの返信が遅い可能性がある @@ -284,11 +284,11 @@ \item Transactionの確定に時間がかからない. \end{itemize} -\section{Paxosによるブロックチェーン} +\subsection{Paxosによるブロックチェーン} PaxosはProof of Workと比べ,CPUのリソースを消費せず,Transactionの確定に時間がかからない.そのため,Paxosでブロックのコンセンサスを取るブロックチェーンを実装することにはメリットがある.また,Paxos自体がリーダー選出に向いているアルゴリズムである.そのため,リーダーを決め,そのノードのブロックチェーンの一貫性のみを考えることもできる. - -\section{Christie} +\section{Chrsitie} +\subsection{Christieとは} Christieは当研究室で開発している分散フレームワークである.Christieは当研究室で開発しているGearsOSに組み込まれる予定がある.そのためGearsOSを構成する言語Continuation based Cと似た概念がある.Christieに存在する概念として次のようなものがある. \begin{itemize} \item CodeGear(以下 CG) @@ -305,7 +305,7 @@ \item[PeekFrom(Remote DGM name)] Peekと似ているが, Remote DGM nameを指定することで, その接続先(Remote)のDGMからPeek操作を行える. \end{description} -\section{プログラミングの例} +\subsection{プログラミングの例} ここでは,Christieで実際にプログラムを記述する例を述べる.CGMを作り,setup(new CodeGear)を動かすことにより,DGを持ち合わせ,DGが揃った場合にCodeGearが実装される.CGMを作る方法はStartCodeGear(以下SCG)を継承したものからcreate-CGM(port)methodを実行することによりCGMが作られる.SCGのコードの例をソースコード4.1に示す. \begin{flushleft} @@ -314,7 +314,7 @@ \end{description} -\section{TopologyManager} +\subsection{TopologyManager} Christieは当研究室で開発されたAliceを改良した分散フレームワークである.しかし,Aliceの機能を全て移行したわけではない.TopologyManagerは最たる例であり.分散プログラムを簡潔に書くために必要である.そのため,ChristieにTopoplogyManagerを実装した.// ここではTopologyManagerがどのようなものかを述べる.TopologyManagerとは,Topologyを形成するために,参加を表明したノード,TopologyNodeに名前を与え,必要があればノード同士の配線も行うコードである.TopologyManagerのTopology形成方法として,静的Topologyと動的Topologyがある.静的Topologyはコード\ref{code:dot-example}のようなdotファイルを与えることで,ノードの関係を図\ref{fig:dot-example}のようにする.静的Topologyはdotがいるのノード数と同等のTopologyNodeがあって初めて,CodeGearが実行される. @@ -330,7 +330,7 @@ \end{figure} 動的Topologyは参加を表明したノードに対し,動的にノード同士の関係を作る.例えばTreeを構成する場合,参加したノードから順に,rootに近い位置の役割を与える.また,CodeGearはノードが参加しmparentに接続された後に実行される. -\section{Chrisiteにおけるブロックチェーンの実装の利点と欠点} +\subsection{Chrisiteにおけるブロックチェーンの実装の利点と欠点} Christieにおいてブロック, トランザクション, Paxos, Proof of Workを実装した. @@ -353,7 +353,7 @@ \section{評価} 本研究室では,実際にコンセンサスアルゴリズムPaxosを分散環境場で実行した,分散環境場で動かすため,JobSchedulerの一種であるTorque Resource Manager(Torque)を使用した.ここではTorqueとは何か,どのような評価をしたかを述べる. -\section{Torqueとは} +\subsection{Torqueとは} PCクラスタ上でプログラムの実験を行う際には,他のプログラムとリソースを取り合う懸念がある.それを防ぐためにTorqueを使用する.Torqueはjobという単位でプログラムを管理し,リソースを確保できたら実行する.jobはqsubというコマンドを使って,複数登録することができる.また,実行中の様子もqstatというコマンドを使うことで監視ができる.\\ Torqueには主に3つのNodeの種類がある.\\ @@ -363,7 +363,7 @@ \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の投入を行なった. +今回は図\ref{fig:kvm}のように,学科のKVM上にMaster Node, Submit/Interactive Nodeの役割を持つVM1台と,Computer Nodesとして15台のVMうぶbを用意し,jobの投入を行なった. \begin{figure}[h] \begin{center} @@ -380,6 +380,24 @@ 「\#PBS オプション」とすることにより実行環境を設定できる. 使用できるオプションは参考文献に書かれてある. このスクリプトでは, ノード数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}[h] +\begin{center} +\includegraphics[width=300pt]{./images/paxos1.pdf} +\caption{Paxos動作を表したシーケンス図} +\end{center} +\label{fig:paxos} +\end{figure} + +一意の値を決めることができており,また,Learnerが値を選択した後でも,Paxosは常に決めた値を持ち続けるアルゴリズムである.ログの出力では提案番号がより大きいものの提案まで続いていたが,値がこれ以上覆らなかった。 +今回はわかりやすいよう値を数字で行なった実験であるが,これをタランザクション,ブロックに応用することで,ブロックチェーンにおけるコンセンサス部分を完成させることができる. + +\section{計測実験} + +\section{まとめ} + \end{document} \ No newline at end of file