共识桌游
摘要
本文通过桌游隐喻解释共识算法（如Paxos），利用视觉图表说明投票、领导者选举以及分布式系统中的容错性。
<header>
<h1>共识桌游</h1>
<time class="meta" datetime="2026-03-19">2026年3月19日</time>
</header>
<p>我在早期成年期因试图在无数糟糕的解释中理解共识而留下了创伤。为了弥补，我决定也加入自己的尝试。今天，我想画一系列可能有助于理解的图片。你可以将此帖子视为<a href="https://matklad.github.io/2020/11/01/notes-on-paxos.html"><em>Notes on Paxos</em></a>的缺失插图，或者，你也可以将<em>那篇</em>帖子视为本篇的更正式的叙述性对应文章。</p>
<p>这个想法来源于我的<a href="https://tigerbeetle.com/blog/2025-11-22-mathematics-of-consensus/">mathematics of consensus</a>讲座，有<a href="https://www.youtube.com/watch?v=thY12Wnrmyw">英语</a>和<a href="https://www.youtube.com/watch?v=h8nj65jvXl0">俄语</a>版本。</p>
<section id="The-Preamble">
<h2><a href="#The-Preamble">前言</a></h2>
<p>我将<em>极力</em>省略细节，请参阅<a href="https://matklad.github.io/2020/11/01/notes-on-paxos.html"><em>Notes</em></a>以填补空白。</p>
<p>在开始之前，我想再次强调，这里我严格关注算法背后的<em>数学</em>，即宇宙的逻辑结构，它使某些事情不可能，而另一些事情可行。共识只是真实数据管理系统工程中的一小部分，我将来可能会讨论共识的<em>实用</em>方面，但今天不会 ;)</p>
</section>
<section id="The-Problem">
<h2><a href="#The-Problem">问题</a></h2>
<p>有一个由五名成员组成的委员会，试图为自行车棚选择一种颜色，但委员会成员并不可靠。我们希望即使在部分成员缺席的情况下也能达成决定。</p>
</section>
<section id="The-Vote">
<h2><a href="#The-Vote">投票</a></h2>
<p>共识的基本思想是简单多数投票。如果R0到R4是五名委员会成员，我们可以用下面的棋盘来记录投票：</p>
<figure>
<img alt="" src="/assets/2026-03-19-consensus-board-game/blank.svg">
</figure>
<p>一次成功的投票如下所示：</p>
<figure>
<img alt="" src="/assets/2026-03-19-consensus-board-game/red-wins.svg">
</figure>
<p>在这里，红色获得了5票中的3票，获胜。注意R4尚未投票。它最终可能会投票，也可能不会，但这不会影响结果。</p>
<p>投票的问题是它可能陷入以下僵局：</p>
<figure>
<img alt="" src="/assets/2026-03-19-consensus-board-game/stuck.svg">
</figure>
<p>在这里，红色有两票，蓝色有两票，但潜在的决胜票R4投给了绿色，这个捣蛋鬼！</p>
<p>为了解决分裂投票，我们将指定R0为委员会的主席，让它选择颜色，并允许其他人仅批准。注意有意义的投票仍然进行，因为有人可能弃权——你需要至少50%的投票率才算投票完成：</p>
<figure>
<img alt="" src="/assets/2026-03-19-consensus-board-game/leader.svg">
</figure>
<p>在这里，R0（主席，用黄色拿破仑双角帽标记）选择了红色，R2和R3同意，因此红色“获胜”，即使R1和R4弃权（x表示缺少投票）。</p>
<p><em>这个</em>的问题是，我们指定的主席本身可能不可用：</p>
<figure>
<img alt="" src="/assets/2026-03-19-consensus-board-game/leader-dead.svg">
</figure>
</section>
<section id="The-Board">
<h2><a href="#The-Board">棋盘</a></h2>
<p>这就引出了我想分享的中心插图。我们现在要做的是<em>倍增</em>我们的投票。委员会不是只进行一次指定主席的投票，而是进行一系列并发投票，主席按轮询顺序轮换。这产生了以下半无限的二维棋盘，共识游戏就在上面进行：</p>
<figure>
<img alt="" src="/assets/2026-03-19-consensus-board-game/board-blank.svg">
</figure>
<p>每一列独立进行。如果你是一列的主席，且你的格子是空的，你可以选择任何颜色。如果你是追随者，你需要等待该列主席的决定，然后你可以填充相同的颜色，或者弃权。几轮之后，棋盘可能看起来像这样：</p>
<figure>
<img alt="" src="/assets/2026-03-19-consensus-board-game/board-filled.svg">
</figure>
<p>二维设置的好处是，如果任何委员会成员不可用，<em>他们</em>的列可能会卡住，但只要多数成员可用，总会有某一列完成。缺点在于，虽然单个列的决定清晰明确，但整个棋盘的结果是未定义的。在上面的例子中，有一列红色获胜，另一列蓝色获胜。</p>
<p>所以我们将丢弃上述无效棋盘，而是<em>要求</em>任何达到多数的列<em>必须</em>在颜色上达成一致。换句话说，整个棋盘的结果是任何一列的结果，以最先完成的为准，安全条件是不同列中不能有两种颜色达到多数。</p>
<p>让我们退回到棋盘还没乱的时候，从R3的角度思考下一步的选择：</p>
<figure>
<img alt="" src="/assets/2026-03-19-consensus-board-game/board-choice.svg">
</figure>
<p>作为R3和你所在列的主席，你需要选择一个不会与任何过去或<em>未来</em>其他列的决定冲突的颜色。鉴于已经有一些绿色和蓝色，感觉你也许不应该选红色……但有可能三个部分填充的列将来不会移动，而第一列获得一条坚实的红线！艰难的选择！你需要担心未来<em>和</em>右边无限数量的列！</p>
<p>幸运的是，如果我们假设每个人都遵循相同的规则，问题可以大大简化，那样只需要担心左边的列。假设你和其他人都仔细选择行动，不与左边的列冲突。那么，如果你选了红色，你的列获胜，随后右边某个傻瓜选了绿色，那是<em>他们</em>的问题，因为你在他们左边。</p>
<p>所以我们只关注棋盘的左边部分。同样，蓝色或绿色似乎是好的选择，因为它们已经出现在棋盘上，但第一列最终可能会投红色。为了防止这种情况，我们将收集多数参与者（R0、R2、R3），并要求他们承诺<em>不</em>在第一列投票。实际上，为此，我们阻止他们在<em>任何</em>左边的列投票：</p>
<figure>
<img alt="" src="/assets/2026-03-19-consensus-board-game/board-x.svg">
</figure>
<p>在这里，你要求R0、R2和R3在前三列放弃进一步投票，用黑色x表示。有了这张图，我们现在可以确定红色无法在第一列获胜——那里没有颜色能获胜，因为那里只有五个投票中的两个可用！</p>
<p>尽管如此，我们仍然需要在绿色和蓝色之间选择，应该选哪个？答案是选最右边的。我们左边紧邻的那一列中，选了蓝色的参与者R2正在执行相同的算法。如果他们选了蓝色，那一定是因为他们确信第二列最终不会投绿色。R2让不同的多数参与者放弃在第二列投票，虽然我们作为R3不知道那是哪些参与者，但我们"
查看缓存全文
缓存时间: 2026/05/16 03:33
# 共识棋盘游戏
来源：https://matklad.github.io/2026/03/19/consensus-board-game.html
2026年3月19日
我在早期成年期曾因苦苦理解共识而留下心理阴影，彼时各种解释糟糕透顶。为了弥补这一缺憾，我又一次亲自下场，试图贡献自己的解释。今天，我想画一系列可能有所帮助的图示。你可以将这篇博文看作《Paxos笔记》（https://matklad.github.io/2020/11/01/notes-on-paxos.html）缺失的插图；或者，你也可以将*那篇*博文视为本文更正式的文字叙述。
这个想法源自我的“共识的数学”（https://tigerbeetle.com/blog/2025-11-22-mathematics-of-consensus/）讲座，有英文版（https://www.youtube.com/watch?v=thY12Wnrmyw）和俄文版（https://www.youtube.com/watch?v=h8nj65jvXl0）。
## 前言（https://matklad.github.io/2026/03/19/consensus-board-game.html#The-Preamble）
我将*激进地*模糊处理细节，请参考*《笔记》*（https://matklad.github.io/2020/11/01/notes-on-paxos.html）来填补空白。
在开始之前，我想再次强调，这里我严格关注算法背后的*数学*，关注宇宙的逻辑结构——哪些事情不可能，哪些事情可以做到。共识仅仅是真实数据管理系统背后工程的一小部分，将来我可能会谈谈共识的*实用层面*，但今天不会 ;)
## 问题（https://matklad.github.io/2026/03/19/consensus-board-game.html#The-Problem）
有一个五人委员会，试图为自行车棚挑选一种颜色，但委员会成员并非完全可靠。我们希望即使部分成员缺席，也能达成决策。
## 投票（https://matklad.github.io/2026/03/19/consensus-board-game.html#The-Vote）
支撑共识的基本思想是简单多数投票。如果 R0, ... R4 是五位委员会成员，我们可以用下面的棋盘来记录投票：
一次成功的投票看起来是这样的：
这里，红色获得了5票中的3票，获胜。注意 R4 尚未投票。它可能最终会投，也可能不会，但这不影响结果。
投票的问题在于可能会陷入僵局：
这里，红色和蓝色各得两票，而潜在的决胜者 R4 却投给了绿色，这个捣蛋鬼！
为了解决分散投票的问题，我们指定 R0 作为委员会的领导者，让它选择颜色，其他成员只能批准。注意，有意义的投票仍然存在，因为有人可能弃权——你需要至少50%的投票率才算完成投票：
这里，领导者 R0（用黄色的拿破仑双角帽标记）选择了红色，R2 和 R3 表示同意，因此红色“赢”了，即使 R1 和 R4 弃权（x 表示未投票）。
但*这个*方案的问题在于，我们指定的领导者自己可能不可用：
## 棋盘（https://matklad.github.io/2026/03/19/consensus-board-game.html#The-Board）
这就引出了我想要分享的核心图示。接下来我们要做的是*倍增*我们的投票。委员会不再只进行一次有指定领导者的投票，而是进行一系列并发投票，领导者按轮询方式轮换。由此产生了以下半无限的二维棋盘，共识游戏就在这个棋盘上进行：
每一列独立进行投票。如果你是一列的领导者，而你的格子是空的，你可以选择任何颜色。如果你是跟随者，你需要等待该列领导者的决策，然后你可以填入相同的颜色，或者弃权。经过几轮后，棋盘可能看起来像这样：
我们二维设置的好处是，如果某个委员会成员不可用，*他们的*列可能会卡住，但只要大多数成员可用，总有一列可能完成。缺点是，虽然单列的决策清晰明确，但整个棋盘的结果是不确定的。在上面的例子中，有一列红色获胜，也有一列蓝色获胜。
因此，我们要废除上面无效的棋盘，转而*要求*任何获得多数的两列*必须*在颜色上达成一致。换句话说，整个棋盘的结果等于任意一列的结果（哪一列先完成就算哪一列），而安全条件是：不同列中不能有两种颜色各自获得多数。
让我们退回到棋盘尚未混乱的时候，从 R3 的角度思考下一步该如何选择：
作为 R3 和你的列的领导，你需要选择一种颜色，使其不会与任何过去或*未来*其他列的决策冲突。考虑到已经有了一些绿色和蓝色，感觉也许你不应该选红色……但也有可能那三列部分填充的列未来不再变动，而第一列反而得到了一条坚实的红线！艰难的选择！你必须担心未来*以及*右边无限多的列！
幸运的是，如果我们假设每个人都遵守相同的规则，问题就能大大简化——此时只需担心你左边的列。假设你和所有人都在谨慎选择行动，以避免与左边的列冲突。那么，如果你选择了红色，你的列获胜，之后右边某个傻瓜选了绿色，那是*他们的*问题，因为你在他们的左边。
所以让我们只关注棋盘的左边部分。同样，蓝色或绿色似乎是不错的选择，因为它们已经出现在棋盘上，但第一列有可能最终投票给红色。为了防止这种情况，我们要收集多数参与者（R0, R2, R3），要求他们承诺*不*在前几列投票。实际上，我们甚至要阻止他们在*任何*左边的列投票：
这里，你要求 R0、R2 和 R3 在前三列不再投票，用黑色的 x 表示。有了这张图，我们现在可以确定红色不可能在第一列获胜——没有颜色能在那里获胜，因为那里只有5票中的2票可用！
但我们仍然需要在绿色和蓝色之间做出选择，该选哪个呢？答案是选最右边的那个。R2——在紧邻我们左边的列选了蓝色的参与者——也执行了同样的算法。如果它选了蓝色，那是因为它确信第二列最终不可能投给绿色。R2 让另一组多数参与者承诺不在第二列投票，而我们作为 R3，虽然不知道那组多数是谁，但我们知道它存在，因为我们知道 R2 确实选了蓝色，并且我们假设公平游戏规则。
---
今天就到这里，这就是让共识在抽象层面得以成立的关键技巧。在完整的分布式系统中，情况更加复杂。每个参与者只看到自己的那一行，整个棋盘是隐藏的。参与者可以通过通信了解其他参与者的状态，但这种知识在时间上并不牢固。收到响应时，答案可能已经过时。然而，上述的鸟瞰视角可以通过几次消息交换来实现。
更多细节请参见*《笔记》*（https://matklad.github.io/2020/11/01/notes-on-paxos.html）。
相似文章
Paxos 简明 (2001)[pdf]
本文简明地解释了 Paxos 算法，该算法用于在分布式系统中达成共识。
我构建了一个计算层，其中分布式共识就是答案——而不仅仅是它的记录。
一种新的计算层，分布式共识作为核心计算机制，而不仅仅是记录工具。
IsabeLLM：自动定理证明在共识形式化验证中的应用
本文介绍了对基于Isabelle构建的自动定理证明工具IsabeLLM的改进，通过集成检索增强生成框架、错误追踪和反例生成。改进后的工具在比特币工作量证明共识协议的形式化验证上进行了评估。
合作博弈的非线性公理归因方法
本文提出了一类用于合作博弈的非线性公理归因方法，以克服线性Shapley值因零空间过大而导致的局限性。实验结果表明，与Shapley值变体相比，这些方法在包含AUC指标方面具有潜在的有效性。
我构建了一个 Hermes 技能，其中 3 个 AI 模型相互争论后才给出答案——采用 RRF 和 Borda Count 排名的对抗式多模型共识
PolyGnosis 是一个基于 Hermes 技能构建的对抗式多模型共识系统。它并行运行三个具有不同专家角色的 AI 模型，然后进入对抗性批评阶段，通过 RRF 和 Borda Count 进行评分，最后通过合成门——所有这些都使用 DeepSeek V4-Pro 以智能体方式构建。