查看“︁Paxos algorithm”︁的源代码

=Paxos解决的是什么问题=
==state machine replication==

[[File:Log-Replication.png|600px]]

如上所示的系统中，如果客户端要执行某个命令，那么将遵循如下的步骤：

#发送命令到其中某一个server
#server首先将命令记录到log中，然后将命令发送到其他的服务中；其他server同样将其记录到log中
#当命令完整的记录到各个server之后，就可以传到state machine去执行了，并将结果返回给客户端

其中，consensus module用来保证log的复制是正确的，也就是paxos要解决的问题。


那么，对于这样一个系统有哪些要求呢？

* 所有的服务器将以同样的顺序执行相同的命令
* 只要集群中大多数服务器可用，系统就是可用状态

=Paxos算法=
<q>
The Paxos algorithm, when presented in plain English, is very simple.
</q>
==共识问题==
上述问题可以简化为，有多个服务可以propose value，而共识算法将保证有且仅有一个value会被选中（chosen）。这里面隐含的条件是：

* 如果没有任何value被propose，那么也不应该有任何值被选中
* 值一旦被选中，各个服务应该可以知晓（learn）选中的值

从而可以得出共识算法实现的安全性约束：

===Safety requirements===

;Validity (or non-triviality):Only a value that has been proposed may be chosen, A process never learns that a value has been chosen unless it actually has been.
;Agreement (or consistency, or safety):Only a single value is chosen, and
;Termination (or liveness): if a value has been chosen, then a process can eventually learn the value.

===assumptions===
另外，paxos中是不考虑拜占庭问题的，有如下假设成立：
* Agents operate at arbitrary speed, may fail by stopping, and may restart. Since all agents may fail after a value is chosen and then restart, a solution is impossible unless some information can be <span class="article-label">re- membered</span> by an agent that has failed and restarted.
* Messages can take arbitrarily long to be delivered, can be duplicated, and can be lost, but they are <span class="article-label">not corrupted</span>. 也即是 <span class="article-label">fail-stop/crash</span> (non-Byzantine) and <span class="article-label">message delay/loss</span>

==Choosing a Value==
===Quorum===
Paxos made simple中，从最简单（但不正确）的方式开始，逐步加强约束，最终得到正确的算法。

首先最简单的情况下，只有一个acceptor，然后choose第一个收到的提案。这种办法显然不行，因为一旦这个acceptor出问题了整个系统就没法用了，所以需要有多个acceptor，当系统中有大多数acceptor接受了提案则认为值被choosen。

为了在集群中形成多数派，其数目必须为基数，设集群中server总数为$$2F + 1$$，则至少可以由$$F+1$$个server构成多数派。

===P1===
如果仅有一个proposer提出了一个提案，那么这个提案显然是需要被接受的。也就是说，acceptor必须要接受它收到的第一个提案，否则如果只有一个proposal的时候就无法选出任何提案了。因此可推导出约束P1：

<q>
P1. An acceptor must accept the first proposal that it receives.
</q>


[[Category:Distributed]]