algorithm - 哪种共识算法本质上是同步的？

Question

有不同的共识算法，用于权限导向的区 block 链，例如

1. PAXOS
2. 筏
3. 拜占庭通用模型

哪些共识算法是同步的和异步的，为什么？请详细说明。谢谢

Answer 1

*我不是分布式系统方面的专家，但我会尝试回答您的问题。

在分布式系统中，人们使用一个底层模型，该模型假定一些关于时间的属性(“这条消息需要多长时间才能到达？”)和一些关于故障类型的属性(“协议(protocol)中的节点如何做错误的东西？”)。

通常用于分布式系统的时序模型主要有三种类型:同步模型、异步模型和部分同步模型。这些模型中的每一个都对在协议(protocol)执行的给定轮次中节点之间的消息交换之间可能发生的时间长度(“延迟”)做出了一些保证。这种分类很重要，因为在分布式设置中，单个节点无法区分发生故障的对等节点和需要很长时间响应的对等节点。

在同步模型中，从节点发送消息到您可以确定接收节点听到消息之间的时间存在某个最大值(“上限”)T。您还有一个关于节点之间速度相对差异的上限 P(因此您可以考虑处理器速度较慢的机器)。

在异步模型中，我们删除了上限 T 和 P。消息可以花费任意长的时间到达对等点，每个节点可以花费任意长的时间来响应。当我们说任意时，我们包括“无限”，这意味着某些事件需要永远发生。

混合了两者的部分同步模型:T 和 P 存在上限，但协议(protocol)设计者不知道它们，任务是设计根据这一事实仍能达成共识的机制。在实践中，鉴于现代网络/机器的现实特征(消息通常到达它们要去的地方)并使用超时等策略来指示节点何时应重试发送消息，协议(protocol)实现者可以实现类似于此模型的系统。

记住以上事实，Paxos和Raft都属于部分同步模型。

拜占庭将军问题是任何分布式计算机系统网络都面临的经典问题。目的是在存在恶意节点的情况下在所有参与节点上保持相同的状态。

在分布式系统中，有许多您需要不断处理的难题。

 Things fail. You can never count on anything being reliable. Even if you have
 perfectly bug-free software, and hardware that never breaks, you’ve still got 
 to deal with the fact that network connections can break, or messages within a 
 network can get lost, or that some bozo might sever your network connection
 with a bulldozer. (That really happened while I was at Google!)

 Given (1), you can never rely on one copy of anything, because that copy might 
 become unavailable due to a failure. So you need to keep multiple copies, and
 those copies need to be consistent – meaning that at any time, all of the
 copies agree about their contents.

 There’s no way to maintain a single completely consistent view of time between
 multiple computers. Due to inconsistencies in individual machine performance,
 and variable network delays, variable storage latency, and several other
 factors, there’s no canonical way of saying that for two events X and Y, “X
 happened before Y”. What that means is that when you try to maintain a consistent set of data, you can’t just say “Run all of the events in order”, because while one server maintaining one copy might “know” that X happened before Y, another server maintaining another copy might be just as certain that Y happened before X.

简而言之，任何事情都可能随时失败；失败后，参与者可以恢复并重新加入系统；系统的任何部分都不会以积极的对抗方式运行(拜占庭故障可能是由于恶意软件造成的)。

为了解决这个问题，我们有共识算法，目的是让所有参与者就同一状态达成一致。共识涉及多个服务器就值(value)观达成一致。一旦他们就某个值做出决定，该决定就是最终决定。当大多数服务器可用时，典型的共识算法会取得进展。Paxos 和 Raft 是解决公共(public)或私有(private)分布式网络中拜占庭一般问题的共识算法。