工作证明共识机制算法

区块链共识是让一个小组中的所有流程根据每个流程的投票达成一致的具体价值的任务。

所有进程必须达成相同的价值，并且必须是由至少一个进程提交的值（即，一致性算法不能仅发明一个值）。

在最基本的情况下，值可以是二进制（0或1），这将允许所有进程使用它来做出是否做某事的决定。

通过选举算法，我们的目标是挑选一名领导。

对于分布式事务，我们需要一致同意是否提交。

这些是共识的形式。用一致的算法，我们需要得到一致的一致同意。

这是一个听起来很简单的问题，但在分布式系统中发现了令人惊讶的大量使用。

任何依靠多个进程保持共同状态的算法都依赖于解决共识问题，达成共识的地方的一些例子是：

• 同步复制的状态机并确保所有副本具有相同（一致）的系统状态视图。
• 选举领导人。（例如互相排斥）
• 分布式容错日志记录与全球一致的排序。
• 管理组员资格。
• 决定承诺或中止分布式交易。

进程之间的共识很容易在一个完美的世界中实现。

例如，当我们较早地研究了分布式互斥算法时，我们访问了一个共识的形式，每个人都可以就谁可以访问资源达成同样的决定。

最简单的实施是指定负责确定结果的全系统协调员。

两阶段提交协议也是一个系统的例子，我们假设协调员和同事是活着的并且沟通或者我们可以等待他们无限期地重启，如果有必要的话。这些算法的结果是，所有进程必须能够正常运行，并且能够相互通信。

故障使之变得困难,故障包括进程故障和通信故障。区块链扩容方式

---

区块链共识机制

既然接受者有一个提议的价值，那么我们就需要一种方法来了解一个提案已被大多数接受者所接受。

该学习者负责获取这些信息。每个接受者在接受提案后，都会将其转发给所有的学习者。这样做的问题是潜在的大量重复消息：（接受者数量）*（学习者数量）。如果需要的话，这可以被优化。可以选出一个或多个 “杰出的学习者”。接受者将与他们交流，他们反过来会通知其他学习者。

---

处理失败

我们不可能完全同意完全异步的错误过程，这意味着不要假定进程或网络通信的速度。

核心问题是没有办法检查一个进程是否失败，或者这个进程是否还活着，但是与进程的通信速度是难以忍受的。

菲舍尔,林奇,帕特森证明了这种不可能性。

另外，在不可靠的沟通的情况下，由于我们可能永远无法与流程进行沟通，所以达成共识是不可能实现的。

我们将研究两个容错方案，这些方案说明了强加给我们的一些基本约束。两军问题尤其相关。

拜占庭两军将军问题

我们来看一下好处理器的情况，但通信线路有问题。这就是所谓的两军问题，可以概括如下：

A，B 两军师协同攻击敌军C， A和B在物理上是分开的，并使用信使进行通信。 A向B发送一个消息“ 让我们在黎明发起攻击 ”。 B收到消息并同意，用“ OK ”消息发送回信使者。信使到达A，但是A意识到B不知道信使是否安全地返回了。如果B不相信A得到了承认，那么就不会相信这次袭击应该发生，因为军队不会自己胜利。 A可以选择用“ A received the OK ” 的消息将信使发送回B，但A将不确定B是否接收到该消息。二军的问题表明，即使与没有缺陷的处理器，两个进程之间可证明协议是不是 可以用不可靠的通信通道。

---

paxos算法协议

Paxos是一种流行的容错分布式共识算法，它允许将全球一致的（全部）订单分配给客户端消息（操作）。

分布式一致性算法的目标是允许一组计算机都同意系统中提出的一个节点（而不是一个随机值）的单个值。

在分布式系统中这样做的挑战是消息可能丢失或者机器cn失败。Paxos保证只要参与算法的大多数系统可用，一组机器将选择一个建议值。

---

 

POW(Proof of Work)工作证明

共识机制在以前一般被称为证明方式（Proof），因为比特币采用工作量证明（即Proof-Of-Work，简写为POW）。

POW系统构建区块的过程一般称为“挖矿”（mine）

随着大家对分布式账本一致性问题的不断探索，很多方法被提出来，尤其近期有很多区块链项目回归了对传统BFT算法的改进，在思路上已经跳出了“证明”的语义，因此进一步高度概括为共识机制。

---

分布式系统复制的状态机

构建分布式系统的一个重要动机是实现高可扩展性和高可用性。

高可用性可以通过冗余实现：复制功能组件将取代那些停止运作的组件。为了实现多个活动组件的冗余，我们希望所有正在运行的副本执行相同的操作：在给定相同的输入的情况下生成相同的输出。

系统的状态机方法设计每个副本（系统的每个组件）作为确定性状态机。对于给定系统某个特定状态的一些给定输入，将产生确定性输出并转换到新状态。我们将每个副本（组件）称为一个进程。为了正确执行和高可用性，每个进程看到相同的输入是非常重要的。要做到这一点，我们依靠共识算法。这确保多个进程将执行相同的操作，因为它们将被提供相同的一组输入。

输入的例子可以是来自客户端的从文件的特定位置读取数据或将数据写入文件的特定位置的请求。我们希望复制的文件包含完全相同的数据并产生相同的结果。为了实现这一点，我们需要在所有进程中就客户端请求达成一致，并且请求必须完全排序：每个服务器必须以与其他人完全相同的顺序看到文件读/写请求。总的排序部分最容易通过选择一个进程来服务序列号（尽管还有其他更复杂但更分散的实现。

---

确保进展

该算法的一个问题是，对于两个提议者来说可能会继续发出数量增加的提议序列，其中没有一个被选择。来自一个提议者的接受消息可能被接受者忽略，因为已经从另一个提议者处理了更高编号的准备消息。为了确保算法的进展，选择一个“杰出提议者”作为唯一的尝试发布提议。

在操作中，客户向领导者发送命令，这是一个当选的“杰出提议者”。这个提议者对命令进行排序（分配一个值）并运行Paxos算法，以确保选择了一致的序列号。由于失败或其他服务器可能会有冲突，因此认为它是领导者，使用Paxos可以确保只有一个命令（提案）被赋值。

---

分布式租赁与锁定

进程通常依靠锁来确保对资源的独占访问。

锁的难点在于它们不具有容错性。如果持有锁的进程死亡或忘记释放锁，则除非有附加软件来检测这些动作并打破锁定，否则锁就会存在。

出于这个原因，为锁添加到期时间更安全。这把 锁变成租约。

我们在两阶段和三阶段提交协议中看到了这种方法的一个例子。两阶段提交协议使用锁定，而三阶段提交使用租用; 如果租约到期，交易将被中止。我们也看到了这种方法，保持对远程对象的引用。如果租约到期，服务器认为该对象未被引用并且适合于删除。客户负责定期更新租约，只要它需要这个对象。

租赁方法的缺点是在租约到期之前资源不可用。现在我们有一个权衡：失败后可能会有很长一段时间的租赁，或者需要经常更新的短租赁。

---

层级租约与共识

在具有复制组件的容错系统中，应该通过运行共识算法来授予资源租约。

从Paxos的角度来看，很明显，虽然没有大量的消息传递发生，但涉及到的玩家数量很多，因此在使用该算法时存在一定的效率成本。折中方法是使用一致性算法作为选举算法来选择协调器。

该协调员被授予大量资源或系统状态的租约。现在，协调员负责为全部或部分系统状态分配租约。

当协调员的主要租约到期时，必须再次运行一致的算法来授予新的租约，并有可能选出一个新的协调员，但是不必为每个客户端都运行，请求;

这是由协调员简单地处理。