Mercurial > hg > Papers > 2019 > aka-thesis

comparison final_main/chapter3/chapter3.tex @ 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 0ad9752c0c85
children
comparison
equal deleted inserted replaced
11:534d552b4273 12:2e843f65ac5f
113 \item もし, 値がすでにacceptされていれば, accpetされた提案を返す. 113 \item もし, 値がすでにacceptされていれば, accpetされた提案を返す.
114 \end{enumerate} 114 \end{enumerate}
115 115
116 \end{enumerate} 116 \end{enumerate}
117 117
118 1フェーズ目を図にしたものを図\ref{fig:prepare-promise}に示す.
119
120 \begin{figure}[H]
121 \centering
122 \fbox{
123 \includegraphics[scale=0.5]{./images/prepare-promise.pdf}
124 }
125 \caption{prepare-promise}
126 \label{fig:prepare-promise}
127 \end{figure}
128
129
118 2つ目のフェーズ, accept-acceptedは次のような手順で動作する. 130 2つ目のフェーズ, accept-acceptedは次のような手順で動作する.
119 \begin{enumerate} 131 \begin{enumerate}
120 \item proposerは過半数のacceptorから返信が来たならば, 次の提案をacceptorに送る. これをacceptリクエストという. 132 \item proposerは過半数のacceptorから返信が来たならば, 次の提案をacceptorに送る. これをacceptリクエストという.
121 \begin{enumerate} 133 \begin{enumerate}
122 \item もし, 約束のみが返ってきているならば, 任意の値vをprepareリクエストで送った提案に設定する. 134 \item もし, 約束のみが返ってきているならば, 任意の値vをprepareリクエストで送った提案に設定する.
124 \end{enumerate} 136 \end{enumerate}
125 137
126 \item acceptorはacceptリクエストが来た場合, Promiseした提案よりもacceptリクエストで提案された提案番号が低ければ, その提案を拒否する. それ以外の場合はacceptする. 138 \item acceptorはacceptリクエストが来た場合, Promiseした提案よりもacceptリクエストで提案された提案番号が低ければ, その提案を拒否する. それ以外の場合はacceptする.
127 \end{enumerate} 139 \end{enumerate}
128 140
141 2フェーズ目を図にしたものを図\ref{fig:accept-accepted}に示す.
142
143 \begin{figure}[H]
144 \centering
145 \fbox{
146 \includegraphics[scale=0.5]{./images/accept-accepted.pdf}
147 }
148 \caption{accept-accepted}
149 \label{fig:accept-accepted}
150 \end{figure}
151
152
129 このアルゴリズムによって, 各accptorごとに値が一意に決まる. 値を集計, 選択するのはLearnerの役割である. Learnerが値を集計する方法には2つの方法がある. 153 このアルゴリズムによって, 各accptorごとに値が一意に決まる. 値を集計, 選択するのはLearnerの役割である. Learnerが値を集計する方法には2つの方法がある.
130 154
131 \begin{enumerate} 155 \begin{enumerate}
132 \item Acceptorによって値がacceptされた時に, 各Learnerに送信される. ただし, Message通信量が, $Acceptorの数 \times Learnerの数$になる. 156 \item Acceptorによって値がacceptされた時に, 各Learnerに送信される. ただし, Message通信量が, $Acceptorの数 \times Learnerの数$になる.
133 \item 1つのLearnerが各Learnerに選択された値を送信する. 1の方法に比べてMessage通信量が少なくなる(Acceptorの数の通信量になる)代わりに, そのLearnerが故障した場合は各LearnerがMessageを受け取れない. 157 \item 1つのLearnerが各Learnerに選択された値を送信する. 1の方法に比べてMessage通信量が少なくなる($Acceptorの数 + Learnerの数$になる)代わりに, そのLearnerが故障した場合は各LearnerがMessageを受け取れない.
134 \end{enumerate} 158 \end{enumerate}
135 159
136 2つの方法はメッセージ通信量と耐障害性のトレードオフになっていることがわかる. 160 2つの方法はメッセージ通信量と耐障害性のトレードオフになっていることがわかる.
137 161
138 Paxosでコンセンサスを取ることは, Proof of Workと比較して次のようなメリットがある. 162 Paxosでコンセンサスを取ることは, Proof of Workと比較して次のようなメリットがある.