Distributed-Systems

Paxos paxos Paxos (Greek: Παξοί, pronounced Paksi in English ) 又名Paxi是希腊西南部一个风景如画的小岛。而Paxos算法则是现在很火的分布式一致性算法,为何以一个希腊小岛名字算法？Lamport这样解释道: I thought, and still think, that Paxos is an important algorithm. Inspired by my success at popularizing the consensus problem by describing it with Byzantine generals, I decided to cast the algorithm in terms of a parliament on an ancient Greek island. Leo Guibas suggested the name Paxos for the island. 为描述 Paxos 算法,Lamport 虚拟了一个叫做 Paxos 的希腊城邦,这个岛按照议会民主制的政治模式制订法律,但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员,议长或者传递纸条的服务员都不能承诺别人需要时一定会出现,也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题 (Byzantine failure,即虽然有可能一个消息被传递了两次,但是绝对不会出现错误的消息) ；只要等待足够的时间,消息就会被传到。另外,Paxos 岛上的议员是不会反对其他议员提出的决议的[1]。 ...

Gossip（流言 / 八卦）协议是一种用于在分布式系统中传播消息的通信协议，灵感来自瘟疫扩散、社交网络这类「一传十、十传百」的过程。Redis Cluster、Consul、Apache Cassandra 等系统都用它来做节点间的信息同步。 基本思想 一个节点想把某条信息分享给网络中的其他节点时，并不会一次性广播给所有人，而是周期性地随机挑选若干个节点把消息发过去；收到消息的节点接下来做同样的事，再随机转发给另一些节点。如此一轮轮扩散，消息最终会传遍整个网络。 每次随机发送的目标节点数量记作 fanout（扇出）。比如 fanout = 4，就是每个被「感染」的节点每个周期向 4 个随机节点传播消息。 它的名字和「社交网络」的联想，背后是著名的「六度分隔」现象：1967 年哈佛大学 Stanley Milgram 通过连锁信实验发现，你和任意一个陌生人之间间隔的人通常不超过六个。若每人平均认识 260 人，理论上 260⁶ 已远超全球人口——这种指数级扩散正是 Gossip 的雏形。 用途 主要用于信息的传播与扩散，常见场景包括：数据库复制、配置 / 状态扩散、集群成员关系维护、故障探测等。典型系统有 Apache Cassandra、Redis（Cluster 模式）、Consul 等。 特点 可扩展（scalable）：把消息传遍所有节点大约只需 O(log N) 个周期。发送时不需要等待对方确认（ack），即使个别消息丢失也不用补偿——节点会反复多次分享同一条消息，丢一两次不影响最终所有节点收到。在 fanout 固定时，节点数从 20 翻到 40、80、160，所需周期数也只是缓慢增长。 失败容错（fault-tolerant）：网络故障等情况下依然能工作。即使暂时连不上某个节点，其他被「感染」的节点也会继续尝试向它传播。 健壮（robust）：没有 leader 之类的特殊角色，任何节点随时上下线都不会破坏整体服务质量。 局限 Gossip 也有不完美的地方，比如难以应对拜占庭问题（Byzantine）：如果存在一个恶意传播错误消息的节点，普通 Gossip 协议的系统就会出问题——它假定节点只是可能失联，而不会主动作恶。 参考 阿飞的博客（简书）：https://www.jianshu.com/p/54eab117e6ae https://cloud.tencent.com/developer/article/1662426 维护记录 时间 修改内容 原因 2026-06-30 给「拜占庭问题」加内链指向 byzantine-generals-problem；标签由 Inbox 改为 distributed-systems/remix/AI-assisted，新增 lastmod 与拜占庭将军问题一文互链；规范标签 2026-06-30 从 inbox/Gossip.md 移到 cs/gossip.md；文件名改小写、title 改为「Gossip Protocol 流言协议」、url 改为 gossip（旧 Gossip 入 aliases）；分类 inbox→Algorithm、补 gossip 标签；重排为 ## 小标题、清掉无图的残留图注、改写为自有表述 文件原在未分类 inbox、文件名大写、结构零散，整理归类

接触区块链，多少会听到「某某算法解决了拜占庭将军问题」。它其实是分布式系统一致性（distributed consensus）领域一个很经典的抽象问题，由 Leslie Lamport（2013 年图灵奖得主，分布式系统领域奠基人之一，逻辑时钟、Paxos、LaTeX 的作者）与 Robert Shostak、Marshall Pease 在 1982 年的论文 《The Byzantine Generals Problem》 中提出。 什么是拜占庭将军问题 它也被叫作「拜占庭容错问题」。用一个比喻来描述： 拜占庭帝国派出 10 支军队去包围一个敌人。这个敌人能抵御 5 支常规军队的同时袭击，所以至少要有 6 支军队（过半）同时进攻才能取胜。这些军队分散在敌国四周，只能靠通信兵骑马互相传递消息来约定「进攻意向」和「进攻时间」。 麻烦在于：将军中可能有叛徒。叛徒会擅自篡改进攻意向或时间。那么，在可能存在叛徒的情况下，忠诚的将军们要如何达成一致、保证有多于 6 支军队在同一时间发起进攻？ 需要注意，这个问题里假定信道本身是可靠的（消息不会丢失、不会被截获）。至于「在可能丢消息的不可靠信道上，靠消息传递达成一致是不可能的」，那是另一个经典结论——两将军问题（Two Generals’ Problem），由 Akkoyunlu 等人在 1975 年提出并证明无解、Jim Gray 1978 年将其命名，是第一个被证明无解的计算机通信问题。它常被误记为 Lamport 的成果，其实和拜占庭将军问题是两回事：前者讲「信道不可靠」，后者讲「节点会作恶」。所以拜占庭将军问题把信道问题排除在外，焦点放在「节点（将军）本身可能作恶」上。 问题分析 先看没有叛徒的情况：将军 A 提一个进攻提议（「明天下午 1 点进攻，你加入吗？」），通过通信兵告诉其他将军。如果他收到 6 个以上将军的同意，就能发起进攻。但如果其他将军同时也在发不同的提议（2 点、3 点……），由于消息到达有时间差，不同将军收到并认可的提议可能不一样，于是出现 A 提议 3 票、B 提议 4 票、C 提议 2 票这种分裂局面。 再加入叛徒就更复杂了：一个叛徒会向不同的将军发出不同的提议（告诉 A 是 1 点、告诉 B 是 2 点），也可能同时同意多个互相冲突的提议。 叛徒发送的这种前后不一致、互相矛盾的信息，就叫「拜占庭错误（Byzantine fault）」。 ...