# HG changeset patch # User akahori # Date 1550557687 -32400 # Node ID 2e843f65ac5fd2c791a081702762b3981b445d9a # Parent 534d552b4273ec890d5b682d4d2b22b814e72168 update diff -r 534d552b4273 -r 2e843f65ac5f final_main/chapter3/chapter3.tex --- a/final_main/chapter3/chapter3.tex Mon Feb 18 23:59:41 2019 +0900 +++ b/final_main/chapter3/chapter3.tex Tue Feb 19 15:28:07 2019 +0900 @@ -115,6 +115,18 @@ \end{enumerate} +1フェーズ目を図にしたものを図\ref{fig:prepare-promise}に示す. + +\begin{figure}[H] +\centering + \fbox{ + \includegraphics[scale=0.5]{./images/prepare-promise.pdf} + } +\caption{prepare-promise} +\label{fig:prepare-promise} +\end{figure} + + 2つ目のフェーズ, accept-acceptedは次のような手順で動作する. \begin{enumerate} \item proposerは過半数のacceptorから返信が来たならば, 次の提案をacceptorに送る. これをacceptリクエストという. @@ -126,11 +138,23 @@ \item acceptorはacceptリクエストが来た場合, Promiseした提案よりもacceptリクエストで提案された提案番号が低ければ, その提案を拒否する. それ以外の場合はacceptする. \end{enumerate} +2フェーズ目を図にしたものを図\ref{fig:accept-accepted}に示す. + +\begin{figure}[H] +\centering + \fbox{ + \includegraphics[scale=0.5]{./images/accept-accepted.pdf} + } +\caption{accept-accepted} +\label{fig:accept-accepted} +\end{figure} + + このアルゴリズムによって, 各accptorごとに値が一意に決まる. 値を集計, 選択するのはLearnerの役割である. Learnerが値を集計する方法には2つの方法がある. \begin{enumerate} \item Acceptorによって値がacceptされた時に, 各Learnerに送信される. ただし, Message通信量が, $Acceptorの数 \times Learnerの数$になる. -\item 1つのLearnerが各Learnerに選択された値を送信する. 1の方法に比べてMessage通信量が少なくなる(Acceptorの数の通信量になる)代わりに, そのLearnerが故障した場合は各LearnerがMessageを受け取れない. +\item 1つのLearnerが各Learnerに選択された値を送信する. 1の方法に比べてMessage通信量が少なくなる($Acceptorの数 + Learnerの数$になる)代わりに, そのLearnerが故障した場合は各LearnerがMessageを受け取れない. \end{enumerate} 2つの方法はメッセージ通信量と耐障害性のトレードオフになっていることがわかる. diff -r 534d552b4273 -r 2e843f65ac5f final_main/images/accept-accepted.graffle Binary file final_main/images/accept-accepted.graffle has changed diff -r 534d552b4273 -r 2e843f65ac5f final_main/images/accept-accepted.pdf Binary file final_main/images/accept-accepted.pdf has changed diff -r 534d552b4273 -r 2e843f65ac5f final_main/images/prepare-promise.graffle Binary file final_main/images/prepare-promise.graffle has changed diff -r 534d552b4273 -r 2e843f65ac5f final_main/images/prepare-promise.pdf Binary file final_main/images/prepare-promise.pdf has changed diff -r 534d552b4273 -r 2e843f65ac5f final_main/main.pdf Binary file final_main/main.pdf has changed diff -r 534d552b4273 -r 2e843f65ac5f final_pre/main.pdf Binary file final_pre/main.pdf has changed diff -r 534d552b4273 -r 2e843f65ac5f final_pre/pre.pdf Binary file final_pre/pre.pdf has changed diff -r 534d552b4273 -r 2e843f65ac5f final_pre/pre.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/final_pre/pre.tex Tue Feb 19 15:28:07 2019 +0900 @@ -0,0 +1,113 @@ +\documentclass[twocolumn,twoside,9.5pt]{jarticle} +\usepackage[dvipdfmx]{graphicx} +\usepackage{picins} +\usepackage{fancyhdr} +\usepackage{abstract} +\usepackage{url} +%\pagestyle{fancy} +\lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 卒業研究発表会} +\rhead{} +\cfoot{} + +\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}} +\setlength{\headheight}{0mm} +\setlength{\headsep}{5mm} +\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}} +\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}} +\setlength{\textwidth}{181mm} +\setlength{\textheight}{261mm} +\setlength{\footskip}{0mm} +\pagestyle{empty} + +\input{dummy.tex} +\renewcommand{\abstractname}{Abstract} +\begin{document} +\title{Blockchain implements in Christie} +%\title{Supporting NAT in Screen Sharing System TreeVNC} +\author{155753A 氏名 {赤堀}{貴一} 指導教員 : 河野 真治} +\date{} +\twocolumn [ +\maketitle +\begin{onecolabstract} + +Data corruption and inconsistency in computers causes severe problem. Therefore, detect corruption and inconsistency by Blockchain. The Blockchain is a distributed system. It is possible to compare between hash value and data which is correct. Even if there are incorrect operation and tampering, data are possible to recover with Blockchain. + +We are developing Christie and GearsOS. Christie is a distributed framework and GearsOS is a Operating System. GearsOS Filesystem will refer to Christie. if implementing block chain in Christie and implementing it in GearsOS, makes it possible to detect data corruption and inconsistency in the GearsOS file system. In addition, it is possible to configure decentralized distributed network between Gears OS. if it does not configure, data is protected. So, our purpose can be achieved. + +In this study, We implement Blockchain in Christie and run it in distributed environment on PC cluster. +\end{onecolabstract}] +\thispagestyle{fancy} + +\section{研究目的} + +コンピュータにおいてデータの破損や不整合は深刻な異常を引き起こす原因となる. そのため, 破損, 不整合を検知するためにブロックチェーン技術を用いたい. ブロックチェーンは分散ネットワーク技術であり, データの破損や不整合をハッシュ値によって比較できる. そして, 誤操作や改ざんがあった場合でも, ブロックチェーンを用いることでデータの追跡が行える. + +当研究室では分散フレームワークとしてChristieを開発しており, これはGearsOSにファイルシステムに組み込む予定がある. そのため, Christieにブロックチェーンを実装し, GearsOSに組み込むことにより, GearsOSのファイルシステムにおいてデータの破損, 不整合を検知できる. また, GearsOS同士による分散ファイルシステムを構成することができ, 非中央的にデータの分散ができるようになる. もし分散システムを構成しない場合でもデータの整合性保持は行え, 上記の目的は達成できる. + +本研究では, Christieにブロックチェーンを実装し, 実際に学科のPCクラスタ上の分散環境で動かす. + +\section{ブロックチェーン} +ブロックチェーンとは分散型台帳技術とも呼ばれ, 複数のトランザクションをまとめたブロックをつなげたものを, システムに参加しているすべてのノードが参照できる技術である. +ブロックチェーンを実装することは次のようなメリットが有る. + +\begin{itemize} +\item データの追跡, 検証が容易である. +\item 中央管理者が存在しない. 単一障害点がない. +\end{itemize} + +データの追跡, 検証が容易であるのは, ブロックの構造によるものである. ブロックの構造は簡易化すれば次のようなものである. + +\begin{itemize} +\item 前のブロックの暗号化ハッシュ. +\item タイムスタンプ. +\item トランザクションリスト. +\end{itemize} + +ブロックは図\ref{fig:chain}のようにhashでつながっている. 一つのブロックが変更されれば, その後に連なるブロックも整合性が保たれないため, これによってデータの整合性保持が行える. + +\begin{figure}[h] +\centering + \fbox{ + \includegraphics[scale=0.3]{./images/chain.pdf} + } +\caption{hash chain} +\label{fig:chain} +\end{figure} + + +トランザクション, ブロックともにノード間で伝搬され, ノードごとに検証される. そして検証を終え, 不正なトランザクション, ブロックであれば破棄する. 検証に通った場合は, トランザクションはTransaction PoolにTransactionを貯めておき, ブロックはブロックチェーンに取り組まれ, また検証したノードからトランザクション, ブロックがブロードキャストされる. ノード間はP2Pで通信が行われている. + +同時に異なるノードで複数のブロックができることを, forkという. これによってブロックチェーンの分岐が起こる. +ブロックチェーンの分岐を収束させるにはコンセンサスアルゴリズムを使用する. + +\section{コンセンサスアルゴリズム} +コンセンサスアルゴリズムとは, 一意の値を分散環境上で決めるためのアルゴリズムである. + +今回は分散アルゴリズムとしてPaxosを実装した. + + +\section{Christie} + +Christieは当研究室で開発している分散フレームワークである. ChristieはJavaで書かれているが, 当研究室で開発しているGearsOSに組み込まれる予定がある. そのため, GearsOSを構成する言語Continuation based Cと似た概念がある. Christieに存在する概念として次のようなものがある. + +\begin{itemize} +\item CodeGear(以下CG) +\item DataGear(以下DG) +\item CodeGearManager(以下CGM) +\item DataGearManager(以下DGM) +\end{itemize} + +CGはクラス, スレッドに相当し, DGは変数データに相当する. CGMはノードであり, DGM, CG, DGを管理する. DGMはDGを管理するものであり, putという操作により変数データ, つまりDGを格納できる. + +DGMにはLocalとRemoteと2つの種類があり, Localであれば, LocalのCGMが管理しているDGMに対し, DGを格納していく. Remoteであれば接続したRemote先のCGMのDGMにDGを格納できる. DGを取り出す際にはアノテーションを付けることで, データの取り出し方も指定できる. Take, Peekという操作があり, Takeは読み込んだDGが消えるが, PeekはDGを消さずにそのまま残す. また, RemoteTake, RemotePeekというものもあり, リモート先を指定することにより, RemoteDGMからデータを取ることができる. + +CGはCGMによって実行されるが, 実行するにはCGに必要なDGが全て揃う必要がある. もしDGが全て揃わない場合, CGMはずっとlistenし, データが揃うまで実行を待つ. + + +\section{まとめ} + + +\nocite{*} +\bibliographystyle{junsrt} +\bibliography{reference} +\end{document} \ No newline at end of file diff -r 534d552b4273 -r 2e843f65ac5f slide/slide.html --- a/slide/slide.html Mon Feb 18 23:59:41 2019 +0900 +++ b/slide/slide.html Tue Feb 19 15:28:07 2019 +0900 @@ -86,7 +86,7 @@ @@ -98,7 +98,10 @@
コンピュータでデータが壊れることはあり得る. 誤操作や, データの破損, 最悪の場合システムの重要な部分のデータの破損も起こりうる.
-ブロックチェーンはデータを分散でき, 破損や不整合の検知が可能である.
-当研究室ではGearsOS, そしてGearsOSに組み込む予定がある分散フレームワークChristieがある.
-Christieにブロックチェーンを実装し, GearsOSに組み込むことで, GearsOS間の分散システムが可能になる. また, 分散システムを作らずとも, hash chainとしてデータの破損を検知できる.
-よって, Christieにブロックチェーンを実装する.
-ブロックチェーンとは分散型台帳技術と呼ばれる. 複数のトランザクションをまとめたブロックをつなげたものを, 台帳と呼ぶ. その台帳をシステムに参加しているすノードが参照できる技術である.
+ブロックチェーンとは分散型台帳技術と呼ばれる. 複数のトランザクションをまとめたブロックをつなげたものを, 台帳と呼ぶ. その台帳をシステムに参加しているノードが保持する技術である.
ノード同士はP2Pでつながっており, 対等である. そのため, 管理者がいなくてもデータの管理が行える.
@@ -145,6 +138,16 @@