Mercurial > hg > Papers > 2019 > aka-thesis

changeset 12:2e843f65ac5f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update
author akahori
date Tue, 19 Feb 2019 15:28:07 +0900
parents 534d552b4273
children 117794d50054
files final_main/chapter3/chapter3.tex final_main/images/accept-accepted.graffle final_main/images/accept-accepted.pdf final_main/images/prepare-promise.graffle final_main/images/prepare-promise.pdf final_main/main.pdf final_pre/main.pdf final_pre/pre.pdf final_pre/pre.tex slide/slide.html slide/slide.md
diffstat 11 files changed, 220 insertions(+), 124 deletions(-) [+]
line wrap: on
line diff
--- 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つの方法はメッセージ通信量と耐障害性のトレードオフになっていることがわかる.
Binary file final_main/images/accept-accepted.graffle has changed
Binary file final_main/images/accept-accepted.pdf has changed
Binary file final_main/images/prepare-promise.graffle has changed
Binary file final_main/images/prepare-promise.pdf has changed
Binary file final_main/main.pdf has changed
Binary file final_pre/main.pdf has changed
Binary file final_pre/pre.pdf has changed
--- /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
--- 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 @@
 <!-- === begin markdown block ===
 
       generated by markdown/1.2.0 on Ruby 2.3.7 (2018-03-28) [universal.x86_64-darwin17]
-                on 2019-02-18 23:27:37 +0900 with Markdown engine kramdown (1.17.0)
+                on 2019-02-19 10:39:13 +0900 with Markdown engine kramdown (1.17.0)
                   using options {}
   -->
 
@@ -98,7 +98,10 @@
   <li>ブロックチェーンとは</li>
   <li>ブロックチェーンのfork</li>
   <li>コンセンサスアルゴリズム
-      - Proof of Work と Paxos</li>
+    <ul>
+      <li>Proof of Work と Paxos</li>
+    </ul>
+  </li>
   <li>Christieとは</li>
   <li>TopologyManagerの実装</li>
   <li>PCクラスタ上でPaxosを動かした話</li>
@@ -112,21 +115,11 @@
 <h1 id="os">OS単位での分散システム</h1>
 
 <ul>
-  <li>
-    <p>コンピュータでデータが壊れることはあり得る. 誤操作や, データの破損, 最悪の場合システムの重要な部分のデータの破損も起こりうる.</p>
-  </li>
-  <li>
-    <p>ブロックチェーンはデータを分散でき, 破損や不整合の検知が可能である.</p>
-  </li>
-  <li>
-    <p>当研究室ではGearsOS, そしてGearsOSに組み込む予定がある分散フレームワークChristieがある.</p>
-  </li>
-  <li>
-    <p>Christieにブロックチェーンを実装し, GearsOSに組み込むことで, GearsOS間の分散システムが可能になる. また, 分散システムを作らずとも, hash chainとしてデータの破損を検知できる.</p>
-  </li>
-  <li>
-    <p>よって, Christieにブロックチェーンを実装する.</p>
-  </li>
+  <li>コンピュータでデータが壊れることはあり得る. 誤操作や, データの破損, 最悪の場合システムの重要な部分のデータの破損も起こりうる.</li>
+  <li>ブロックチェーンはデータを分散でき, 破損や不整合の検知が可能である.</li>
+  <li>当研究室ではGearsOS, そしてGearsOSに組み込む予定がある分散フレームワークChristieがある.</li>
+  <li>Christieにブロックチェーンを実装し, GearsOSに組み込むことで, GearsOS間の分散システムが可能になる. また, 分散システムを作らずとも, hash chainとしてデータの破損を検知できる.</li>
+  <li>よって, Christieにブロックチェーンを実装する.</li>
 </ul>
 
 
@@ -135,7 +128,7 @@
 <!-- _S9SLIDE_ -->
 <h1 id="section-1">ブロックチェーンとは</h1>
 
-<p>ブロックチェーンとは分散型台帳技術と呼ばれる. 複数のトランザクションをまとめたブロックをつなげたものを, 台帳と呼ぶ. その台帳をシステムに参加しているすノードが参照できる技術である.</p>
+<p>ブロックチェーンとは分散型台帳技術と呼ばれる. 複数のトランザクションをまとめたブロックをつなげたものを, 台帳と呼ぶ. その台帳をシステムに参加しているノードが保持する技術である.</p>
 
 <p>ノード同士はP2Pでつながっており, 対等である. そのため, 管理者がいなくてもデータの管理が行える.</p>
 
@@ -145,6 +138,16 @@
 <!-- _S9SLIDE_ -->
 <h1 id="section-2">ブロックチェーンとは</h1>
 
+<div style="text-align: center;">
+    <img src="./images/blockchain.svg" alt="blockchain" width="1000" height="600" />
+</div>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h1 id="section-3">ブロックチェーンとは</h1>
+
 <p>ブロックチェーンにも種類がある. パブリックブロックチェーンとプライベートブロックチェーンである. 以下に, その違いを述べる.</p>
 
 <table>
@@ -185,57 +188,42 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h1 id="section-3">コンセンサスアルゴリズム</h1>
+<h1 id="section-4">コンセンサスアルゴリズム</h1>
 
 <ul>
-  <li>
-    <p>コンセンサスアルゴリズムは分散環境上で値を一意に決めるためのアルゴリズムである.
-      - Paxos, Raftなどが有名. 簡単に言えば多数決を安全に行うためのアルゴリズム.
-      - 故障モデルというものがあって, コンセンサスアルゴリズムでレベルが4段階ある. Paxos, Raftはレベル3で, ノードに裏切り者がいなければ安全に動く.
-      - PBFTがレベル4である<s>が読んでないのでわからない</s></p>
+  <li>コンセンサスアルゴリズムは分散環境上で値を一意に決めるためのアルゴリズムである.
+    <ul>
+      <li>Paxos, Raftなどが有名. 簡単に言えば多数決を安全に行うためのアルゴリズム.</li>
+      <li>故障モデルというものがあって, コンセンサスアルゴリズムでレベルが4段階ある. Paxos, Raftはレベル3で, ノードに裏切り者がいなければ安全に動く.</li>
+      <li>PBFTがレベル4である<s>が読んでないのでわからない</s></li>
+    </ul>
   </li>
-  <li>
-    <p>Proof of Workを使っているパブリックブロックチェーンは「ブロックが多ければ多いほど」, レベル4に近づく.</p>
-  </li>
+  <li>Proof of Workを使っているパブリックブロックチェーンは「ブロックが多ければ多いほど」, レベル4に近づく.</li>
 </ul>
 
 
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h1 id="section-4">パブリックブロックチェーンのコンセンサスアルゴリズム</h1>
+<h1 id="section-5">パブリックブロックチェーンのコンセンサスアルゴリズム</h1>
 
 <ul>
-  <li>
-    <p>パブリックブロックチェーンのコンセンサスアルゴリズムは, 「ある程度ブロックの差がついたら, 長い方を正とする」というもの.</p>
-  </li>
-  <li>
-    <p>これだけだと, 裏切り者が適当なブロックガシガシ積めば攻撃できるのでレベル4にはなれない. これを大幅に補強したのがProof of Work.</p>
-  </li>
-  <li>
-    <p>Proof of Workは, 簡単に言えばブロックのHashに条件をつけるアルゴリズム. つまり, 新しいブロックを作るのが難しくなる.</p>
-  </li>
-  <li>
-    <p>新しいブロックを作るのが難しいので, みんなで協力して作ったチェーンが自然に勝つ. また, 改ざんも難しくなる. ただし, トランザクションの確定が遅い.</p>
-  </li>
+  <li>パブリックブロックチェーンのコンセンサスアルゴリズムは, 「ある程度ブロックの差がついたら, 長い方を正とする」というもの.</li>
+  <li>これだけだと, 裏切り者が適当なブロックをガシガシ積めば攻撃できるのでレベル4にはなれない. これを大幅に補強したのがProof of Work.</li>
+  <li>Proof of Workは, 簡単に言えばブロックのHashに条件をつけるアルゴリズム. つまり, 新しいブロックを作るのが難しくなる.</li>
+  <li>新しいブロックを作るのが難しいので, みんなで協力して作ったチェーンが自然に勝つ. また, 改ざんも難しくなる. ただし, トランザクションの確定が遅い.</li>
 </ul>
 
 
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h1 id="section-5">プライベートブロックチェーンのコンセンサスアルゴリズム</h1>
+<h1 id="section-6">プライベートブロックチェーンのコンセンサスアルゴリズム</h1>
 
 <ul>
-  <li>
-    <p>プライベートブロックチェーンは管理者が許可するノードしか参加しない. つまり, レベル3のコンセンサスアルゴリズムで十分.</p>
-  </li>
-  <li>
-    <p>新しいブロックもパブリックブロックチェーンより早く作れる.</p>
-  </li>
-  <li>
-    <p>コンセンサスアルゴリズムの中でPaxosが速いらしいので, 今回はこちらも実装してみます.</p>
-  </li>
+  <li>プライベートブロックチェーンは管理者が許可するノードしか参加しない. つまり, レベル3のコンセンサスアルゴリズムで十分.</li>
+  <li>新しいブロックもパブリックブロックチェーンより早く作れる.</li>
+  <li>コンセンサスアルゴリズムの中でPaxosが速いらしいので, 今回はこちらも実装してみます.</li>
 </ul>
 
 
@@ -245,15 +233,9 @@
 <h1 id="christie">Christieとは</h1>
 
 <ul>
-  <li>
-    <p>研究室で使っていたAliceの問題点を解消した, 分散プログラミングを簡単に書けるjavaのフレームワーク.</p>
-  </li>
-  <li>
-    <p>Continued based C(CbC)と似た書き方が可能.</p>
-  </li>
-  <li>
-    <p>まだAliceから引き継いでない機能でTopologyManagerというものがあるので, それも実装.</p>
-  </li>
+  <li>研究室で使っていたAliceの問題点を解消した, 分散プログラミングを簡単に書けるjavaのフレームワーク.</li>
+  <li>Continued based C(CbC)と似た書き方が可能.</li>
+  <li>まだAliceから引き継いでない機能でTopologyManagerというものがあるので, それも実装.</li>
 </ul>
 
 
@@ -263,18 +245,10 @@
 <h1 id="topologymanager">TopologyManagerとは</h1>
 
 <ul>
-  <li>
-    <p>TopologyManagerは参加を表明したノード(TopologyNode)を元にTopologyを作る.</p>
-  </li>
-  <li>
-    <p>TopologyManagerは静的Topologyと動的Topologyを作れる.</p>
-  </li>
-  <li>
-    <p>静的Topologyはdotファイルというものを読み込んで, そのとおりにTopologyを生成する.</p>
-  </li>
-  <li>
-    <p>動的Topologyは参加を表明したノードを動的に配置する. が, 今はTreeしか実装していません.</p>
-  </li>
+  <li>TopologyManagerは参加を表明したノード(TopologyNode)を元にTopologyを作る.</li>
+  <li>TopologyManagerは静的Topologyと動的Topologyを作れる.</li>
+  <li>静的Topologyはdotファイルというものを読み込んで, そのとおりにTopologyを生成する.</li>
+  <li>動的Topologyは参加を表明したノードを動的に配置する. が, 今はTreeしか実装していません.</li>
 </ul>
 
 
@@ -284,51 +258,39 @@
 <h1 id="pcpaxos">PCクラスタ上でPaxosを動かした話</h1>
 
 <ul>
-  <li>
-    <p>ブロックチェーンにおいて, 分散環境上でテストしなければいけないのはコンセンサスアルゴリズムである. そのため, Paxosを実装し, 実際の分散環境上で動かした.</p>
-  </li>
-  <li>
-    <p>評価は値が一意に決まるかどうかである. 値が一意に決まるならば, リーダーがコンセンサスをとっても良いし, ブロックについてコンセンサスをとっても良い.</p>
-  </li>
-  <li>
-    <p>今回は単純化のために, 整数でコンセンサスを取る.</p>
-  </li>
+  <li>ブロックチェーンにおいて, 分散環境上でテストしなければいけないのはコンセンサスアルゴリズムである. そのため, Paxosを実装し, 実際の分散環境上で動かした.</li>
+  <li>評価は値が一意に決まるかどうかである. 値が一意に決まるならば, リーダーがコンセンサスをとっても良いし, ブロックについてコンセンサスをとっても良い.</li>
+  <li>今回は単純化のために, 整数でコンセンサスを取る.</li>
 </ul>
 
 
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h1 id="section-6">実験1</h1>
+<h1 id="section-7">実験1</h1>
 
 
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h1 id="section-7">実験2</h1>
+<h1 id="section-8">実験2</h1>
 
 
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h1 id="section-8">実験3</h1>
+<h1 id="section-9">実験3</h1>
 
 
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h1 id="section-9">まとめ</h1>
+<h1 id="section-10">まとめ</h1>
 
 <ul>
-  <li>
-    <p>コンセンサスアルゴリズムのPaxosを実装しました.</p>
-  </li>
-  <li>
-    <p>ブロック, トランザクション, proof of workも実装しました. ただ, トランザクションはファイルのデータを読めるようにはしていません.</p>
-  </li>
-  <li>
-    <p>これらを繋げてブロックチェーンにできれば, Christieにブロックチェーンが実装されます. パブリックブロックチェーンもプライベートブロックチェーンもどちらも作れます.</p>
-  </li>
+  <li>コンセンサスアルゴリズムのPaxosを実装しました.</li>
+  <li>ブロック, トランザクション, proof of workも実装しました. ただ, トランザクションはファイルのデータを読めるようにはしていません.</li>
+  <li>これらを繋げてブロックチェーンにできれば, Christieにブロックチェーンが実装されます. パブリックブロックチェーンもプライベートブロックチェーンもどちらも作れます.</li>
 </ul>
 <!-- === end markdown block === -->
 </div>
--- a/slide/slide.md	Mon Feb 18 23:59:41 2019 +0900
+++ b/slide/slide.md	Tue Feb 19 15:28:07 2019 +0900
@@ -10,34 +10,34 @@
 - ブロックチェーンとは
 - ブロックチェーンのfork
 - コンセンサスアルゴリズム
-        - Proof of Work と Paxos
+    - Proof of Work と Paxos
 - Christieとは
 - TopologyManagerの実装
 - PCクラスタ上でPaxosを動かした話
 - まとめ
 
-
 # OS単位での分散システム
 
 - コンピュータでデータが壊れることはあり得る. 誤操作や, データの破損, 最悪の場合システムの重要な部分のデータの破損も起こりうる.
-
 - ブロックチェーンはデータを分散でき, 破損や不整合の検知が可能である.
-
 - 当研究室ではGearsOS, そしてGearsOSに組み込む予定がある分散フレームワークChristieがある.
-
 - Christieにブロックチェーンを実装し, GearsOSに組み込むことで, GearsOS間の分散システムが可能になる. また, 分散システムを作らずとも, hash chainとしてデータの破損を検知できる.
-
 - よって, Christieにブロックチェーンを実装する.
 
-
 # ブロックチェーンとは
 
-ブロックチェーンとは分散型台帳技術と呼ばれる. 複数のトランザクションをまとめたブロックをつなげたものを, 台帳と呼ぶ. その台帳をシステムに参加しているすノードが参照できる技術である.
+ブロックチェーンとは分散型台帳技術と呼ばれる. 複数のトランザクションをまとめたブロックをつなげたものを, 台帳と呼ぶ. その台帳をシステムに参加しているノードが保持する技術である.
 
 ノード同士はP2Pでつながっており, 対等である. そのため, 管理者がいなくてもデータの管理が行える.
 
 # ブロックチェーンとは
 
+<div style="text-align: center;">
+    <img src="./images/blockchain.svg" alt="blockchain" width="1000" height="600">
+</div>
+
+# ブロックチェーンとは
+
 ブロックチェーンにも種類がある. パブリックブロックチェーンとプライベートブロックチェーンである. 以下に, その違いを述べる.
 
 |  | パブリックブロックチェーン | プライベートブロックチェーン |
@@ -53,59 +53,58 @@
 
 forkが起こった場合, どちらかを正しいものとしてブロックを積み上げたい. そのため, コンセンサスアルゴリズムを用いて, どちらか1方に統合する.
 
-
 # コンセンサスアルゴリズム
 
 - コンセンサスアルゴリズムは分散環境上で値を一意に決めるためのアルゴリズムである.
-        - Paxos, Raftなどが有名. 簡単に言えば多数決を安全に行うためのアルゴリズム.
-        - 故障モデルというものがあって, コンセンサスアルゴリズムでレベルが4段階ある. Paxos, Raftはレベル3で, ノードに裏切り者がいなければ安全に動く.
-        - PBFTがレベル4である<s>が読んでないのでわからない</s>
-        
+    - Paxos, Raftなどが有名. 簡単に言えば多数決を安全に行うためのアルゴリズム.
+    - 故障モデルというものがあって, コンセンサスアルゴリズムでレベルが4段階ある. Paxos, Raftはレベル3で, ノードに裏切り者がいなければ安全に動く.
+    - PBFTがレベル4である<s>が読んでないのでわからない</s>
 - Proof of Workを使っているパブリックブロックチェーンは「ブロックが多ければ多いほど」, レベル4に近づく.
 
 # パブリックブロックチェーンのコンセンサスアルゴリズム
 
 - パブリックブロックチェーンのコンセンサスアルゴリズムは, 「ある程度ブロックの差がついたら, 長い方を正とする」というもの.
-
-- これだけだと, 裏切り者が適当なブロックガシガシ積めば攻撃できるのでレベル4にはなれない. これを大幅に補強したのがProof of Work.
-
+- これだけだと, 裏切り者が適当なブロックをガシガシ積めば攻撃できるのでレベル4にはなれない. これを大幅に補強したのがProof of Work.
 - Proof of Workは, 簡単に言えばブロックのHashに条件をつけるアルゴリズム. つまり, 新しいブロックを作るのが難しくなる.
-
-- 新しいブロックを作るのが難しいので, みんなで協力して作ったチェーンが自然に勝つ. また, 改ざんも難しくなる. ただし, トランザクションの確定が遅い.
+- 新しいブロックを作るのが難しいので, みんなで協力して作ったチェーンが自然に勝つ. また, 改ざんも難しい. ただし, トランザクションの確定が遅い.
 
 # プライベートブロックチェーンのコンセンサスアルゴリズム
 
 - プライベートブロックチェーンは管理者が許可するノードしか参加しない. つまり, レベル3のコンセンサスアルゴリズムで十分.
+- 新しいブロックもパブリックブロックチェーンより早く作れる.
+- コンセンサスアルゴリズムの中でPaxosが速いらしいので, 今回はこちらも実装してみます.
 
-- 新しいブロックもパブリックブロックチェーンより早く作れる.
+# Paxos
+
+- Lamport先生が「故障モデルレベル3での合意が不可能なのを証明してやる」と言って証明の途中で逆に編み出してしまったらしいアルゴリズム.
+- レベル3のアルゴリズムの基礎となっている.
+- proposerが値を提案し, acceptorが決め, Learnerが集計して多数決を取って決まった値を保持.
 
-- コンセンサスアルゴリズムの中でPaxosが速いらしいので, 今回はこちらも実装してみます.
+# Paxos説明の前の用語説明
+
+- 
+
+# [25行でわかるPaxosアルゴリズム](http://nil.csail.mit.edu/6.824/2015/notes/paxos-code.html)
+
+- Proposerは
 
 # Christieとは
 
 - 研究室で使っていたAliceの問題点を解消した, 分散プログラミングを簡単に書けるjavaのフレームワーク.
-
 - Continued based C(CbC)と似た書き方が可能.
-
 - まだAliceから引き継いでない機能でTopologyManagerというものがあるので, それも実装.
 
 # TopologyManagerとは
 
 - TopologyManagerは参加を表明したノード(TopologyNode)を元にTopologyを作る.
-
 - TopologyManagerは静的Topologyと動的Topologyを作れる.
-
 - 静的Topologyはdotファイルというものを読み込んで, そのとおりにTopologyを生成する.
-
 - 動的Topologyは参加を表明したノードを動的に配置する. が, 今はTreeしか実装していません.
 
-
 # PCクラスタ上でPaxosを動かした話
 
 - ブロックチェーンにおいて, 分散環境上でテストしなければいけないのはコンセンサスアルゴリズムである. そのため, Paxosを実装し, 実際の分散環境上で動かした.
-
 - 評価は値が一意に決まるかどうかである. 値が一意に決まるならば, リーダーがコンセンサスをとっても良いし, ブロックについてコンセンサスをとっても良い.
-
 - 今回は単純化のために, 整数でコンセンサスを取る.
 
 
@@ -118,7 +117,5 @@
 # まとめ
 
 - コンセンサスアルゴリズムのPaxosを実装しました.
-
 - ブロック, トランザクション, proof of workも実装しました. ただ, トランザクションはファイルのデータを読めるようにはしていません.
-
 - これらを繋げてブロックチェーンにできれば, Christieにブロックチェーンが実装されます. パブリックブロックチェーンもプライベートブロックチェーンもどちらも作れます.