# HG changeset patch
# User akahori
# Date 1550326520 -32400
# Node ID d6cca85616e23f2688d775828a11b28c89a2684a
# Parent  7ab85a536778c65747a40576f3af976da3dda94b
update

diff -r 7ab85a536778 -r d6cca85616e2 final_main/chapter2/chapter2.tex
--- a/final_main/chapter2/chapter2.tex	Fri Feb 15 21:46:26 2019 +0900
+++ b/final_main/chapter2/chapter2.tex	Sat Feb 16 23:15:20 2019 +0900
@@ -64,5 +64,6 @@
 
 
 
+
 %%文書終了****************************
 \end{document} 
\ No newline at end of file
diff -r 7ab85a536778 -r d6cca85616e2 final_main/chapter3/chapter3.tex
--- a/final_main/chapter3/chapter3.tex	Fri Feb 15 21:46:26 2019 +0900
+++ b/final_main/chapter3/chapter3.tex	Sat Feb 16 23:15:20 2019 +0900
@@ -69,7 +69,7 @@
 
 この方法でコンセンサスを取る場合の欠点を挙げる.
 \begin{itemize}
-\item この計算をするためだけにCPUを消費する. 単純計算であるため, とても重要な計算をしているわけではなく, CPUの資源が無駄に使われる.
+\item CPUのリソースを使用する. 
 \item Transactionが確定するのに時間がかかる. 
 \end{itemize}
 
@@ -86,6 +86,65 @@
 
 Proof of Workにある特性の4がないが, これは許可したノードのみが参加可能だからである. つまり, 悪意あるノードが参加する可能性が少ないためである. 
 
+Paxosは3つの役割のノードがある.
+
+\begin{description}
+\item[proposer] 値を提案するノード.
+\item[acceptor] 値を決めるノード.
+\item[learner] acceptorから値を集計し, 過半数以上のacceptorが持っている値を決める.
+\end{description}
+
+Paxosのアルゴリズムに入る前に, 定義された用語を説明する. 以下にその用語の定義を示す.\begin{description}
+\item[提案(リクエスト)] 提案は, 異なる提案ごとにユニークな提案番号と, 値からなる. 提案番号とは, 異なる提案を見分けるための識別子であり, 単調増加する. 値は一意に決まってほしいデータである.
+\item[値(提案)がacceptされる] acceptorによって値(提案)が決まること. 
+\item[値(提案)が選択される] 過半数以上のacceptorによって, 値(提案)がacceptされた場合, それを値(提案)が選択されたと言う.
+\end{description}
+
+
+Paxosのアルゴリズムは2フェーズある. 
+
+1つ目のフェーズ, prepare-promiseは次のような手順で動作する. 
+\begin{enumerate}
+\item proposerは提案番号nを設定した提案を過半数以上のacceptorに送る. これをprepareリクエストという. 
+\item acceptorはprepareリクエストが来たら次の動作をする. 
+\begin{enumerate}
+\item もし, 以前に送られたprepareリクエストの提案番号より, 今送られてきたprepareリクエストの提案番号のほうが大きければ, それ以下の提案番号の提案を拒否するという約束を返す. この状態をPromiseしたという.
+\item もし, 値がすでにacceptされていれば, accpetされた提案を返す. 
+\end{enumerate}
+
+\end{enumerate}
+
+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}
+
+このアルゴリズムによって, 各accptorごとに値が一意に決まる. 値を集計, 選択するのはLearnerの役割である. Learnerが値を集計する方法には2つの方法がある.
+
+\begin{enumerate}
+\item Acceptorによって値がacceptされた時に, 各Learnerに送信される. ただし, Message通信量が, $Acceptorの数 \times Learnerの数$になる.
+\item 1つのLearnerが各Learnerに選択された値を送信する. 1の方法に比べてMessage通信量が少なくなる(Acceptorの数の通信量になる)代わりに, そのLearnerが故障した場合は各LearnerがMessageを受け取れない.
+\end{enumerate}
+
+2つの方法はメッセージ通信量と耐障害性のトレードオフになっていることがわかる.
+
+Paxosでコンセンサスを取ることは, Proof of Workと比較して次のようなメリットがある.
+
+\begin{itemize}
+\item CPUのリソースを消費しない
+\item Transactionの確定に時間がかからない.
+\end{itemize}
+
+\section{Paxosによるブロックチェーン}
+
+PaxosはProof of Workに比べ, CPUのリソースを消費せず, Transactionの確定に時間がかからない. そのため, Paxosでブロックのコンセンサスを取るブロックチェーンを実装することにはメリットが有る.
+また, Paxos自体がそもそもリーダー選出に向いているアルゴリズムである. そのため, リーダーを決め, そのノードのブロックチェーンの一貫性のみを考えることもできる.
 
 
 
diff -r 7ab85a536778 -r d6cca85616e2 final_main/main.pdf
Binary file final_main/main.pdf has changed