问题标签 [consensus]

我已经阅读了 Lamport关于 Paxos的论文。我还听说，出于性能原因，它在实践中的使用并不多。分布式系统中共识常用的算法有哪些？

我正在研究 Paxos，我对算法在这个人为的例子中应该如何表现感到困惑。我希望下图能解释这个场景。

几点：

• 每个代理都充当提议者/接受者/学习者
• 准备消息有形式(instance, proposal_num)
• 提议消息有形式(instance, proposal_num, proposal_val)
• Server1 和 Server2 都决定同时启动提案流程
• 在开始时，消息 M1、M2 和 M3 同时出现

这里似乎虽然协议是“正确的”，即只S2选择了一个值，但 Server1 和 Server2 认为选择它是因为不同的提案编号。

Decide(...)Paxos 算法是否仅在消息发送给学习者时才终止？我一定是误解了Paxos Made Simple，但我认为选择是在提议者达到他们的Propose(...)消息的法定人数的那一刻做出的。

Decide(...)如果仅在将消息发送给代理后才做出选择，那么 Server2 是否应该Decide(1, 5, S2)在它恢复时终止其发送，因为它看到了较晚的消息Prepare(1, 7)？

有人能给我一份 Paxos 的真实用例列表吗？这是真正的问题，需要将共识作为更大问题的一部分。

以下是 Paxos 的用例吗？

假设有两个客户端在扑克服务器上互相玩扑克。扑克服务器被复制。我对 Paxos 的理解是，它可以用来保持代表当前扑克牌的内存数据结构的一致性。也就是说，确保所有副本都具有完全相同的内存状态。

但是为什么需要 Paxos？假设需要发一张新牌。如果一切正常，运行相同代码的每个副本都会生成相同的卡。为什么客户端不能只从所有复制的服务器请求最新状态并选择出现最多的卡。因此，如果一台服务器出现错误，客户端仍然可以通过选择大多数来获得正确的状态。

我在下面粘贴了 paxos 算法的伪代码，想知道是否有人能指出我正确的方向。我正在尝试实现下面的算法，但我对下面的“视图”到底代表什么感到困惑。我知道评论说它是“过去视图数字到值的映射”，但是如果有人可以向我解释这些“值”到底是什么以及“视图数字”是什么。

有人可以给我一个真实的例子，说明 Paxos 算法是如何在分布式数据库中使用的吗？我已经阅读了很多关于 Paxos 的论文来解释该算法，但没有一篇真正用一个实际的例子来解释。

一个简单的例子可以是一个银行应用程序，其中一个帐户正在通过多个会话进行修改（即在柜员处存款、借记操作等）。Paxos 是用来决定哪个操作先发生的吗？另外，Paxos 协议的多个实例是什么意思？这个什么时候用？基本上，我试图通过一个具体的例子而不是抽象的术语来理解这一切。

I have pasted pseudocode for a paxos algorithm here:

What is a "view" in the Paxos consensus algorithm?

and was wondering if someone could point me in the right direction.

The algorithm says that each node has a "state" which contains a bunch of information the node should keep track of.

Suppose we have two nodes: Node #1 and Node #2. In the simplest case Node #2 joins Node #1 and they both play paxos. What exactly happens to the states of Node #1 and Node #2 after 2 joins 1? When does the "views" data structure change and what does it contain? If someone can explain to me this simple case of two nodes playing paxos, then I think I can figure out multiple node case.

My current understanding (which I'm pretty sure is not correct) is as follows:

1. Node #2 sends a message to join Node #1.
2. Node #1 receives message from Node #2 asking to join.
3. Node #1 assumes leadership and kicks into phase 1, computes my_num = max(0,0) + 1 = 1
4. Node #1 sends all nodes in views[0] (which is empty) prepare(1,1)
5. Node #1 sends initial contact node (Node #2) prepare(1,1)
6. Node #1 sends Node #1 (itself) prepare(1,1)
7. Node #2 receives prepare(1,1). It sets its num_h=1 and returns to leader PROMISE(0,{empty list})
8. Node #1 receives prepare(1,1) and sets its num_h=1 and returns itself PROMISE(0,{empty list}).

now we get to phase 2

This is where I am quite confused.

Node #1 is the leader and it receives two PROMISE(0,{empty list}) messages. According to the algorithm, if the leader gets a majority of promises in views[0] then it can set a value for "v" and send the ACCEPT message to all responders.

What I am confused about is currently the views[0] for the leader is empty so how can you compute the majority of an empty list?

Also, let's assume the leader has received a majority of promises and proceeds to set v = set of pingable nodes (including self). What exactly are pingable nodes? Is it just Node #1 and Node #2?

Would appreciate all / any help and will definitely award points to those that help.

我已经实现了共识算法（基于 Paxos）。我添加了一些随机测试用例，看起来不错。但是想通过模型检查进行测试？找不到正确的文章。请分享如何在 Paxos 中进行模型检查

谢谢

当两个将军证明“设计算法不可能安全地达成一致”时，像Paxos这样的共识算法如何“保证安全（免于不一致） ”？

当我考虑让两台服务器（1）可靠地交换一个号码（即，两台服务器最终都知道对方肯定收到了号码）或（2）两台服务器最终都知道交换失败并且不改变他们的状态，看起来（就像两位将军一样）消息失败总是会以一种不一致的方式发生（即，一个服务器认为另一个完成了交换，但它没有）。

那么 Paxos（或其他任何东西）如何真正保证“免于不一致”？有简单的语言解释吗？演示两台服务器进行有保证的交换或在失败时完全放弃交换的最简单的伪代码是什么？

在已知的论文Impossibility of Distributed Consensus with one Faulty Process (JACM85)中，FLP（Fisher、Lynch 和 Paterson）证明了一个令人惊讶的结果，即没有完全异步的共识协议可以容忍甚至一个未通知的进程死亡。

在引理 3 中，在证明 D 包含 0 价和 1 价配置后，它说：

如果在一个步骤中一个结果来自另一个，则调用两个配置邻居。通过简单的归纳，存在邻居 C₀, C₁ ∈ C 使得 Dᵢ = e(Cᵢ) 是 i 价的，i = 0, 1。

我可以遵循整个证明，除非他们声称存在这样的 C₀ 和 C₁。你能给我一些提示吗？

我正在尝试编写代码来为文件夹中的 100 多个单独的 fasta 对齐文件中的每一个获得一致序列。一开始我只是想获得一个序列的共识（然后我将使用一个 for 循环来处理所有序列），但是我在共识的字母表上遇到了麻烦。我的测试fasta对齐是：

我希望达成的共识是：

我希望任何包含间隙的列都用“N”表示，而任何没有 100% 相同核苷酸的列都用歧义代码表示。

我的代码不起作用是：

对象“歧义”只接受一个字符串并将一个“N”放置在一致性中存在对齐多态性的任何位置，我似乎无法解决这个问题。任何有关如何纠正此问题的建议将不胜感激。谢谢！