Lamport 的拜占庭将军算法的 Python 实现

python| 2025-08-07

简介

假设有一群拜占庭军队的将军带着他们的部队围困在敌方城市周围。这些将军必须就一个共同的作战计划达成一致：要么进攻，要么撤退。然而，其中一些人可能是叛徒！非叛徒将军只有在所有人都选择同一行动时才能成功——要么所有人都进攻，要么所有人都撤退；如果甚至有一名非叛徒将军采取不同行动，战斗就会失败。

在他们的开创性论文《拜占庭将军问题》中，Lamport、Shostak 和 Pease 提出了这个问题的类比，并使用分布式算法给出了解决方案。他们的摘要写道：

可靠的计算机系统必须处理向系统不同部分提供冲突信息的故障组件。这种情况可以抽象地用拜占庭军队的一群将军来表达，他们带着军队围困敌方城市。将军们只能通过信使沟通，必须就共同的作战计划达成一致。然而，其中一两个可能是叛徒，试图混淆其他人。该问题旨在寻找一种算法，确保忠诚的将军能够达成一致。研究表明，仅使用口头消息时，该问题可解的充要条件是忠诚将军数量超过总数的三分之二；因此，单个叛徒即可扰乱两名忠诚将军。若使用不可篡改的书面消息，该问题对任意数量的将军和叛徒均可解。随后讨论了这些解决方案在可靠计算机系统中的应用。

图0：Lamport 的拜占庭将军算法的 Python 实现

该问题提出：当分布式进程中的一部分(最多M个节点，总数为N个节点)可能随意行为、说谎、省略或伪造消息时，如何使这些进程达成一致？此类故障被称为“拜占庭故障”，因为它们与叛徒将军类似，不仅会崩溃，还会主动试图误导系统其他部分。

本文将实现Lamport经典的拜占庭将军问题解决方案，即该问题的“口头消息”版本；本文讨论的正是此版本。

代码位于Github: mtrencseni/dca/byzantine

问题陈述

问题陈述的通俗表述如下：有N�名将军，其中M�名是叛徒或故障将军。他们需要就一个共同的命令达成一致，该命令通常被视为两个值“攻击”和“撤退”。其中一名将军是国王，他提出初始值(攻击或撤退)并启动算法。注意，国王也可能是叛徒！此外，如果国王不是叛徒，我们希望所有其他非叛徒将军都服从国王的命令。

注：在Lamport的论文中，使用“指挥官”一词代替“国王”；然而，我认为Lamport的术语令人困惑，因为“指挥官”一词在算法的后期阶段也被用于其他节点。因此，在本讨论中，我完全避免使用“指挥官”一词。

假设是：如果所有非叛徒将军同时进攻，他们将取得胜利，否则他们将被击败。如果他们都同意撤退，这也是一个可接受的结果。在拜占庭将军的类比故事中，攻击或撤退的行为本身无关紧要，关键在于他们达成一致的值。从这个意义上说，攻击和撤退是任意的，值可以是任意字符串——关键在于所有非叛徒将军应达成一致的值。

挑战在于设计一种满足这些要求的将军间消息交换算法。

需要注意的是，如果我们可以假设国王不是叛徒，那么解决方案就很简单：国王只需将他的命令(值)发送给其他将军，他们就会按照国王的指示行事。问题只有在国王可能是非M�叛徒之一时才有趣。

假设

将问题转化为现代计算机语言时，我们做出以下假设：

存在N�个节点，它们通过发送消息进行通信。
在N�个总节点中，M�个是叛徒(恶意、故障、行为异常、离线)。
非叛徒节点不知道叛徒的身份。叛徒之间可以相互识别并串通。
其中一个节点(国王)以初始值启动分布式算法。
对于接收到的所有消息，节点可以识别发送者节点——叛徒无法伪造消息。
非叛徒节点遵循给定的分布式算法。
叛徒节点不遵循分布式算法，它们可以：

不发送部分或全部消息
发送重复消息
发送格式错误的消息
发送符合格式但不遵循分布式算法的消息
发送延迟消息
发送顺序错误的消息

在实现层面，大多数背叛行为必须在软件工程层面进行处理。例如，非叛徒节点在停止等待并假设默认值以推进算法之前，应等待其他节点消息多长时间？_这些考虑不在本文玩具实现的范围之内。_在此给出的玩具实现中，叛徒节点在发送消息时基本上遵循协议，但它们发送错误的值(例如撤退而不是攻击)，试图混淆其他节点。

算法

Lamport、Shostak 和 Pease 证明了对于 N<3M+1�<3�+1 的情况，不存在解决拜占庭将军问题的算法，并给出了适用于 N≥3M+1�≥3�+1 情况的分布式算法。让我们以(M,N)=(1,4)的案例来说明挑战和解决方案。假设国王是叛徒，他向其他3个非叛徒将军发送相互矛盾的消息：进攻、撤退、撤退。如果将军们仅仅按照国王的指示行动，那么进攻的将军将会被击败。要么3人都进攻，要么3人都撤退。基本思路是，他们将国王告诉他们的内容转发给彼此，收集这些值，然后对收集的值运行相同的majority()函数，以达成一致决策。让我们使用以下majority()函数，该函数使用计数较高的值，或在平局时撤退：

def majority(values):
    c = Counter(values)
    return "attack" if c["attack"] > c["retreat"] else "retreat"

假设节点(将军)从0开始编号，国王为节点0，在前例中，叛徒国王向以下节点发送了以下值(命令)：

节点1：进攻
节点2：撤退
节点3：撤退

我们将国王发送这些初始命令的初始阶段称为k=1阶段。剩余节点现在均运行k=0阶段；在此阶段，它们相互发送国王发送给它们的值：

节点1向节点2和3发送其接收的值，即攻击
节点2向节点1和3发送其接收的值，即撤退
节点 3 将其收到的值(撤退)发送给节点 1 和 2

总体而言，三个节点将拥有以下值：

节点 1：攻击(来自国王)、撤退、撤退
节点 2：撤退(来自国王)、攻击、撤退
节点 3：撤退(来自国王)、攻击、撤退

该算法的要点在于，三个节点最终将获得相同的三个汇总值：攻击、撤退、撤退。然后它们可以对这些值运行相同的 majority() 函数，该函数将返回撤退，因此三个节点都会撤退。叛徒国王未能欺骗它们。

注意，将军们并不知道国王是否是叛徒，但算法在这种情况下也必须有效。如果国王不是叛徒，但其他3个将军中有一个是叛徒，会发生什么？在这种情况下，国王最初向所有3个节点发送相同的命令。假设国王的命令是攻击(但这只是假设，也可能是撤退或其他任何文本)。国王发送给：

节点1：攻击
节点2：攻击
节点3：攻击

节点随后运行相同的算法，但其中一个是叛徒。假设叛徒是节点3，他破坏了算法，并将收到的“进攻”命令改为“撤退”并转发。

节点1向节点2和3发送收到的值“进攻”
节点2向节点1和3发送收到的值“进攻”
节点 3 是叛徒，向节点 1 和 2 发送错误值撤退

总体而言，两个非叛徒节点 1 和 2 将拥有以下值：

节点 1：攻击(来自国王)、攻击、撤退
节点 2：攻击(来自国王)、攻击、撤退

由于它们都拥有攻击、攻击、撤退的值，当它们对这组值运行majority()函数时，两者都会选择攻击。国王不参与该算法，始终遵循其初始指令，因此最终，三个非叛徒节点(节点0［国王］、1和2)均选择攻击；与之前一样，叛徒节点未能欺骗它们。

需注意我们不关心叛徒节点的行为——由于它们是叛徒(或故障节点)，本就不会遵循算法。

在(M,N)=(1,4)(�,�)=(1,4)的情况下，一个易于理解的两阶段协议有效：在M=1�=1阶段，国王发送初始命令；随后在M=0�=0阶段，其他节点相互通报国王发送的命令，以确保所有节点最终获得相同的多数值。

现在考虑(M,N)=(2,7)(�,�)=(2,7)的情况。假设国王是叛徒，并向其他6个将军发送以下值：

节点1：进攻
节点2：进攻
节点3：进攻
节点4：撤退
节点5：撤退
节点6：撤退

有M=2个叛徒，假设节点6是第二个叛徒。与国王类似，节点6也会向其他节点转发不同的值，以改变他们的多数派平衡并导致他们意见不一致。节点6转发给：

节点 1：撤退
节点 2：撤退
节点 3：撤退
节点 4：进攻
节点 5：进攻

其他节点(1..5)均为非叛徒，遵循算法，因此它们将从国王处接收的值转发出去。每个节点最终会收到 6 个值(1 个来自国王，5 个来自其他将军)，假设算法在此结束，则对这些值调用 majority() 函数。

让我们看看节点 1 收到了哪些值，来自：

节点 0：进攻(第一轮)
节点 2：进攻
节点 3：进攻
节点 4：撤退
节点5：撤退
节点6：撤退(叛徒)

对上述6个值运行majority()将为节点1返回撤退。

现在，让我们看看节点4收到了什么，来自：

节点0：撤退(第一轮)
节点1：攻击
节点2：攻击
节点 3：攻击
节点 5：撤退
节点 6：攻击(叛徒)

对上述 6 个值运行 majority() 函数，节点 4 的结果为 攻击。节点 1 和 4 的意见不一致！

解决方法是再运行一轮算法，重新验证上一轮接收的值。 在上述示例中，非故障将军可以互相发送叛徒节点 6 发送给他们的值，将其与节点 6 的原始值合并，对合并后的值运行 majority()，然后使用该多数值(由于该组中不再有叛徒，因此他们彼此之间是诚实的)，而不是他们最初从 6 接收的值。具体来说，如果他们这样做，他们最终都会得到节点6转发给他们的5个值(撤退、撤退、撤退、攻击、攻击)，这将导致majority(...) = 撤退。因此，通过这个额外的验证步骤，节点4会将他的最后一个值从攻击改为撤退，并也选择撤退，算法继续正常工作！

当然，节点并不知道谁是叛徒谁不是，因此它们必须对第二轮接收的所有消息运行这个额外的第三轮验证，这导致消息数量呈指数级增长。因此，在M=2的情况下，需要3轮消息。同样，在 M=3 的情况下，需要 4 轮来持续检查叛徒是否破坏了多数派的汇总值。

一般来说，当 M 个叛徒存在于 N≥M+1 个节点中时，需要 M+1 轮来确保算法的正确性。这些轮次被称为k=M的轮次，其中国王在第一轮向其他N-1将军发送命令，一直到k=0的轮次。这种k值递减的命名法源自Lamport的原始论文。

消息路径

在上述 M=1�=1 的示例中，3 个将军在第 0 轮互相发送国王在第 1 轮发送给他们的内容，但他们不会将内容发送回国王。在第二个 M=2�=2 的示例中，当节点 1 到 5 检查节点 6 发送给他们的内容时，他们不会将任何内容发送回节点 0 或 6。一般来说，后续的检查阶段发生在未参与被检查的消息级联路径的节点之间。为了确定消息所经过的“路径”，消息中包含一个path字段，该字段是一系列节点ID。最后一个ID始终是发送消息的节点的ID。在上例中，国王的原始消息路径为[0]，而节点6发送的、被其他节点验证的消息路径为[0, 6]。需注意，此处“路径”并非指同一条消息沿此路径传输——而是指节点6因接收了节点0发送的原始消息(触发后续消息)而发送消息。

维护这些路径至关重要，否则节点将无法确定正在验证的消息，因为在较高的 M� 值下，节点在后续轮次中交换的消息数量可能任意高。如果消息中不包含路径信息，节点将无法处理这些值。

一个有趣的问题是，如果叛徒节点更改路径，即它们发送[0, 1, 2, 3]而不是[0, 2, 3, 4]，会发生什么？它们能这样破坏算法吗？有趣的是，答案再次是这是一个工程问题，从理论上讲它们无法破坏算法：

在我们的示例和实现中，路径的第一个元素必须始终为0，因为总是节点0启动算法并开始消息级联；因此，如果一个节点收到来自叛徒节点的路径，而该路径不以0开头，它可以直接忽略该路径。
如果一个叛徒节点发送了两条路径匹配但值不同的消息，接收节点可以察觉到这一点，丢弃第二条及后续消息，仅继续处理第一条接收到的消息；发送节点本就是叛徒，只要N≥3M+1，算法会处理发送错误值的叛徒，因此保留哪条消息并不重要。
如果叛徒发送的消息最后一个元素与自己的ID不匹配，接收方可以直接丢弃该消息，因为根据我们的假设，节点无法伪造彼此的身份，因此接收方知道发送方的ID不匹配。
如果叛徒在路径的中间部分(既不是第一个，也不是最后一个)插入或修改了一些任意的节点ID，这也并非问题：如果这是他已经发送(或将要发送)的现有路径，则归结为上述第2种情况；而如果这是接收方根据算法实际上不需要或不期望的路径，那么接收方可以直接丢弃。为了理解这一点，请注意该算法的消息传播过程是完全确定性的，因此接收方预期并需要接收的不同路径对他而言是已知的！

因此，有趣的是，伪造路径在理论上不会破坏Lamport的分布式算法，尽管在实际实现中这些情况需要处理(例如通过超时机制)。出于这个原因，在我们的示例实现中，叛徒节点不会干扰它们传递的路径，只会修改路径中的值。

超时与默认值

还有一个需要解决的问题是默认值。如果叛徒节点简单地不发送某些消息，或者保持沉默而不参与算法，会发生什么？这再次是一个工程问题，因为它可以通过超时和默认值来处理。换句话说，如果叛徒节点没有发送任何值，我们可以假设它们发送了某个“不是正确值”的值。假设N≥3M+1且我们的算法正常工作，在超时(或类似)情况下，我们可以始终默认采用某种值(例如撤退)，并假设这就是节点发送给我们的值，总体而言算法仍将正确(所有非叛徒节点将决定相同的值)。

出于这个原因，在此给出的玩具实现中，叛徒节点始终参与消息级联(但传递不同值)，以保持实现中不包含超时/重试/默认逻辑，并易于理解。

两阶段

该算法本质上分为两个阶段：

接收和发送消息(消息级联)
使用接收到的消息递归检查级联树中的消息多数派

在Lamport的原始论文中，上述两个阶段以交错方式定义，我发现这非常难以理解。在此给出的玩具实现中，为了教学目的，两个阶段被分离：

**阶段1，消息级联：**节点递归地将消息转发给彼此，扩展path字段，进行M+1�+1轮；所有节点存储所有接收到的消息以供后续处理。
**阶段2，决策：**一旦消息级联完成，节点使用阶段1中存储的消息来确定最终值(攻击或撤退)；本阶段不交换消息。

基于 HTTP Flask 服务器的 Python 实现

与之前的分布式算法类似，这里使用 Flask HTTP 服务器。驱动程序启动 N = 3M + 1 = 3 + 1 个 Python 进程，每个节点对应一个进程，其中 M 个节点在命令行中被指定为叛徒。为了简化，驱动程序始终将节点 0 设为国王(但 general.py 中的算法实现并未做此假设)。当所有节点启动并运行后，驱动程序通过/start端点启动国王节点，国王节点随后触发M+1�+1轮的消息级联。驱动程序通过/status端点检查每个节点是否已接收所需的所有消息(即第一阶段是否完成)，然后调用/decide端点触发节点根据已接收并存储的消息做出决策。需注意，这种两阶段行为(由驱动程序专门控制)旨在使算法流程更易理解，例如在决策阶段，节点可按顺序打印调试日志，而非交错显示。节点在自动接收所有消息后可自行触发决策阶段，即节点可在无需驱动程序指令的情况下直接过渡到第二阶段。

driver.py 代码：

m = int(sys.argv[1]) if len(sys.argv) >= 2 else 1
n = 3*m + 1

# randomly pick m traitors (could include commander 0)
traitors = set(random.sample(range(n), m))
print(f'Traitors: {traitors}')

def spawn(mod, *args):
    return subprocess.Popen([sys.executable, mod, *map(str, args)])

procs = []
# start every general
for gid in range(n):
    traitor = 1 if gid in traitors else 0
    procs.append(spawn("general.py", gid, n, m, traitor))
# let servers come up
time.sleep(1)
# kick off message cascade by telling the commander to issue his order
requests.post("http://127.0.0.1:8000/start", json={"order": "attack" if random.random() < 0.5 else "retreat"})
# wait until all generals report done
while True:
    time.sleep(0.1)
    try:
        if all(requests.get(f"http://127.0.0.1:{8000+i}/status").json()["done"] for i in range(n)):
            break # all done, exit waiting loop
    except:
        pass
# tell each general to decide based on what they've seen so far
print('Decisions:')
decisions = set()
for i in range(n):
    if i in traitors:
        print(f'General {i} is a traitor')
    else:
        value = requests.post(f"http://127.0.0.1:{8000+i}/decide").json()["value"]
        print(f'General {i} decided {value}')
        decisions.add(value)
if len(decisions) == 1:
    print(f'SUCCESS: all non-traitor generals decided to {value}!')
else:
    print('FAILURE: non-traitor generals decided differently')
# stop all generals
for p in procs:
    p.kill()

将军们在 general.py 中实现。/start 端点非常简单，它只是将第一轮消息发送给所有其他将军。如果国王不是叛徒，驱动程序指定的值将广播给所有其他将军，否则国王会交替发送攻击和撤退命令：

@app.route("/start", methods=["POST"])
def start():
    # /start is essentially like order with: path=[], value=order, k=0
    global value
    value = request.get_json()["order"]
    if not traitor:
        broadcast([id], value)
    else:
        for i in range(0, n):
            if i == id: continue # don't order myself
            msg = {"path": [id], "value": other_value(value) if traitor and i % 2 == 0 else value}
            async_order(i, msg)
    global done
    done=True
    return jsonify(ok=True)

第二个相关端点是 /order，将军们在此接收来自国王的消息，以及在后续消息级联轮次中来自其他将军的消息。

@app.route("/order", methods=["POST"])
def order():
    msg = request.get_json()
    path = list(msg["path"])
    value = msg["value"]
    k = 1 + m - len(path)
    msg = {"path": path, "value": value}
    received_values[tuple(path)] = value
    if k > 0:
        broadcast(path + [id], other_value(value) if traitor else value)
    if all_messages_received():
        global done
        done = True
    return jsonify(ok=True)

代码非常简单：

该消息中的值会被保存到 received_values 中以供后续处理
如果 k 值(用于标记消息级联的轮次，初始值为 M)尚未达到 0，则将消息广播给路径上的所有节点：

def broadcast(path, value):
    for i in range(n):
        if i not in path:
            async_order(i, msg={"path": path, "value": value})

order() 函数的最后一步是检查这是否是我们在消息级联中预期接收的最后一条消息——这一点将在后续章节中详细说明。如果所有消息均已接收，则设置 done 标志。

决策

驱动程序会反复检查所有消息是否已处理完毕，使用其简单的 /status 端点：

@app.route("/status")
def status():
    return jsonify(done=done)

一旦所有节点报告已完成(所有节点在级联中接收了所有消息)，驱动程序会调用每个节点的 /decide 端点。正是此时，保存的传入消息会被实际处理以决定最终值。此处使用的算法传统上称为 OM()，与 Lamport 在其原始论文中使用的命名法相同：

@app.route("/decide", methods=["POST"])
def decide():
    assert(done)
    global value
    if value is None:
        value = OM(path=shortest_path())
    return jsonify(value=value)

递归算法 OM(path) 的语义本质上是：对于由 path 标识的消息值，其多数决策是什么，我们使用 path=shortest_path() 调用它，因为我们想要决定的是从国王接收的原始消息(及其值)。由于驱动程序始终选择节点 0 作为国王，shortest_path() 实际上返回 [0]：

def shortest_path():
    return list(min(received_values.keys(), key=len, default=None))

现在，让我们来实现 OM()：

def OM(path):
    k = 1 + m - len(path)
    value = received_values[tuple(path)]
    if k == 0:
        # print(f'node={id}: in round {k} for OM({k}) for path={path} I am just returning the raw received message -> {value}')
        return value
    values = [value]
    # others = []
    for i in range(n):
        if i not in list(path) + [id]:
            # others.append(i)
            values.append(OM(list(path)+[i]))
    # print(f'node={id}: in round {k} I received from path={path} value {vals[0]}, my OM({k-1}) values from others ({others}) are {vals[1:]} -> {majority(values)}')
    return majority(values)

算法 OM() 实现了 Lamport 在介绍中解释的逻辑，通过检查从节点 X 接收的每个值(最多 k>1)，其他节点对 X 发送的同一值的报告情况。通过查看示例运行中的跟踪记录(上述及GitHub上已注释的)可更好地理解该过程。以下是一个示例运行，其中(M,N)=(2,7)且(�,�)=(2,7)，仅展示其中一个节点的上述跟踪记录：

$ python3 driver.py 2
Traitors: {3, 5}
...
node=1: in round 0 for path=[0, 2, 3] I am just returning the raw received message -> retreat
node=1: in round 0 for path=[0, 2, 4] I am just returning the raw received message -> attack
node=1: in round 0 for path=[0, 2, 5] I am just returning the raw received message -> retreat
node=1: in round 0 for path=[0, 2, 6] I am just returning the raw received message -> attack
node=1: in round 1 I received from path=[0, 2] value attack, my OM(k=0) values from others ([3, 4, 5, 6]) are ['retreat', 'attack', 'retreat', 'attack'] -> attack
node=1: in round 0 for path=[0, 3, 2] I am just returning the raw received message -> retreat
node=1: in round 0 for path=[0, 3, 4] I am just returning the raw received message -> retreat
node=1: in round 0 for path=[0, 3, 5] I am just returning the raw received message -> attack
node=1: in round 0 for path=[0, 3, 6] I am just returning the raw received message -> retreat
node=1: in round 1 I received from path=[0, 3] value retreat, my OM(k=0) values from others ([2, 4, 5, 6]) are ['retreat', 'retreat', 'attack', 'retreat'] -> retreat
node=1: in round 0 for path=[0, 4, 2] I am just returning the raw received message -> attack
node=1: in round 0 for path=[0, 4, 3] I am just returning the raw received message -> retreat
node=1: in round 0 for path=[0, 4, 5] I am just returning the raw received message -> retreat
node=1: in round 0 for path=[0, 4, 6] I am just returning the raw received message -> attack
node=1: in round 1 I received from path=[0, 4] value attack, my OM(k=0) values from others ([2, 3, 5, 6]) are ['attack', 'retreat', 'retreat', 'attack'] -> attack
node=1: in round 0 for path=[0, 5, 2] I am just returning the raw received message -> retreat
node=1: in round 0 for path=[0, 5, 3] I am just returning the raw received message -> attack
node=1: in round 0 for path=[0, 5, 4] I am just returning the raw received message -> retreat
node=1: in round 0 for path=[0, 5, 6] I am just returning the raw received message -> retreat
node=1: in round 1 I received from path=[0, 5] value retreat, my OM(k=0) values from others ([2, 3, 4, 6]) are ['retreat', 'attack', 'retreat', 'retreat'] -> retreat
node=1: in round 0 for path=[0, 6, 2] I am just returning the raw received message -> attack
node=1: in round 0 for path=[0, 6, 3] I am just returning the raw received message -> retreat
node=1: in round 0 for path=[0, 6, 4] I am just returning the raw received message -> attack
node=1: in round 0 for path=[0, 6, 5] I am just returning the raw received message -> retreat
node=1: in round 1 I received from path=[0, 6] value attack, my OM(k=0) values from others ([2, 3, 4, 5]) are ['attack', 'retreat', 'attack', 'retreat'] -> attack
node=1: in round 2 I received from path=[0] value attack, my OM(k=1) values from others ([2, 3, 4, 5, 6]) are ['attack', 'retreat', 'attack', 'retreat', 'attack'] -> attack
General 1 decided attack
...

最后说明：国王在驱动程序调用/start端点时已设置其value，他们只是决定最初提出的值并发送给所有其他将军。

消息级联中的消息计数

在消息级联中计数预期消息可通过两种方式实现：

显式模拟消息级联并计数
推导闭合形式公式

两种方法均简单易行。第一种方案可通过几行代码实现，例如：

def count_expected_messages():
    expected_messages = defaultdict(int)
    #
    def receive_message(node, path):
        k = 1 + m - len(path)
        expected_messages[node] += 1
        if k == 0: return
        for i in range(n):
            if i not in path+[node]:
                receive_message(i, path+[node])
    #
    for i in range(1, n):
        receive_message(i, path=shortest_path())
    return expected_messages[id]

对于第二种方案(即本实现实际采用的方法)，公式为：

def expected_messages(k):
    n = 3 * m + 1
    return perm(n-2, m-k)

在 /order 端点中用于检查是否已接收所有消息的函数则简单如下：

total_expected = sum(expected_messages(k) for k in range(m+1))
def all_messages_received():
    total_received = len(received_values)
    if total_received < total_expected:
        return False
    return True

让我们看看不同 M� 值下，每轮中每个节点接收的消息数量(注意 k=0�=0 总是最后一轮)：

	$M = 1$ M=1	$M = 2$ M=2	$M = 3$ M=3	$M = 4$ M=4
$k = 0$ k=0	$2$ 2	$20$ 20	$336$ 336	$7 920$ 7920
$k = 1$ k=1	$1$ 1	$5$ 5	$56$ 56	$990$ 990
$k = 2$ k=2		$1$ 1	$8$ 8	$110$ 110
$k = 3$ k=3			$1$ 1	$11$ 11
$k = 4$ k=4				$1$ 1
total	$3$ 3	$26$ 26	$401$ 401	$9 032$ 9032

M = 1

M=1

M = 2

M=2

M = 3

M=3

M = 4

M=4

k = 0

k=0

2

20

336

336

7 920

7920

k = 1

k=1

1

5

56

990

990

k = 2

k=2

1

8

110

110

k = 3

k=3

1

11

k = 4

k=4

1

total

3

26

401

401

9 032

9032

注意，国王向其他 N−1�−1 个节点各发送一条消息(前 k=M�=� 条消息)，之后国王不再发送或接收任何消息(因为后续所有消息的 path 字段中第一个元素均为国王的节点 ID)。

示例运行

以下是不同M�值的示例运行(N=3M+1�=3�+1始终成立)：

$ python3 driver.py 1
Traitors: {0}
Decisions:
General 0 is a traitor
General 1 decided retreat
General 2 decided retreat
General 3 decided retreat
SUCCESS: all non-traitor generals decided to retreat!

$ python3 driver.py 1
Traitors: {3}
Decisions:
General 0 decided attack
General 1 decided attack
General 2 decided attack
General 3 is a traitor
SUCCESS: all non-traitor generals decided to attack!

$ python3 driver.py 2
Traitors: {0, 5}
Decisions:
General 0 is a traitor
General 1 decided retreat
General 2 decided retreat
General 3 decided retreat
General 4 decided retreat
General 5 is a traitor
General 6 decided retreat
SUCCESS: all non-traitor generals decided to retreat!

$ python3 driver.py 3
Traitors: {4, 6, 8}
Decisions:
General 0 decided attack
General 1 decided attack
General 2 decided attack
General 3 decided attack
General 4 is a traitor
General 5 decided attack
General 6 is a traitor
General 7 decided attack
General 8 is a traitor
General 9 decided attack
SUCCESS: all non-traitor generals decided to attack!

$ python3 driver.py 4
Traitors: {0, 1, 5, 7}
Decisions:
General 0 is a traitor
General 1 is a traitor
General 2 decided retreat
General 3 decided retreat
General 4 decided retreat
General 5 is a traitor
General 6 decided retreat
General 7 is a traitor
General 8 decided retreat
General 9 decided retreat
General 10 decided retreat
General 11 decided retreat
General 12 decided retreat
SUCCESS: all non-traitor generals decided to retreat!

对 2025 的人工智能来说太复杂了

在过去的两年里，我一直在使用大语言模型(LLMs)，特别是最新的 ChatGPT 模型进行编码。这些大语言模型对于我为 Bytepawn 文章编写的 100-1000 行程序特别有用。在许多情况下，ChatGPT 能够一次就产生一个几乎完整的解决方案。有趣的是，在编写本文的代码时，OpenAI的o3模型多次无法生成可工作的实现，即使经过约10次尝试(包括优化、显示错误日志和从头开始)。似乎拜占庭将军问题存在以下问题：(i)过于复杂，(ii)算法描述过于模糊，(iii)在互联网上讨论和实现的案例过于稀少——因此在训练数据中罕见——导致o3无法正确处理。另一方面，当我要求它从阻塞 HTTP 调用(在将军之间)切换到非阻塞解决方案时，它一次就给出了可行的解决方案。鉴于他们的训练数据，大语言模型(LLMs) 作为软件工程师比作为计算机科学家更出色，这也许并不令人感到意外。

结论

通过将Lamport的消息级联和多数投票逻辑实现为代码，我们看到理论保证转化为可工作的系统：在完成M+1�+1轮转发后，每个非叛徒节点都会做出相同的决策。尽管指数级消息增长使该算法在大规模M�下不切实际，但这一练习为理解现代、更高效的拜占庭容错协议奠定了清晰的基础。

在未来的博文中，我计划探讨：

工程优化(例如，在将军之间使用原始TCP连接而非HTTP)
启用由不同节点发起的算法多次运行
实现Lamport的第二个拜占庭将军算法，该算法使用不可篡改的签名消息(数字签名)

本文文字及图片出自 Lamport's Byzantine Generals algorithm in Python

Lamport 的拜占庭将军算法的 Python 实现

简介

问题陈述

假设

算法

消息路径

超时与默认值

两阶段

基于 HTTP Flask 服务器的 Python 实现

决策

消息级联中的消息计数

示例运行

对 2025 的人工智能来说太复杂了

结论

发表回复取消回复

相关文章：

随机动画

简单所见即所得在线HTML编辑器

Markdown HTML 转换工具

HTML Markdown 转换工具

CSS 玻璃效果生成器

将iOS风格的液体玻璃添加到您的网页

变种数字消消乐 – 令人沉迷的数字游戏

扑克魔术

懒人的俄罗斯方块游戏

人间血照，一个令人深思的游戏

纯 CSS 构建的《我的世界(Minecraft)》

大脑错觉：撒切尔效应

webassembly 二维布料仿真模型

升级版青蛙过河智力游戏

网页小游戏：戳破泡泡

CSS Grid 布局代码生成器

一个 Div 能做的事情

青蛙过河智力小游戏

数字消消乐

交互式演示教程教会你精通掌握 CSS Flexbox 布局

链接收藏

Lamport 的拜占庭将军算法的 Python 实现

简介

问题陈述

假设

算法

消息路径

超时与默认值

两阶段

基于 HTTP Flask 服务器的 Python 实现

决策

消息级联中的消息计数

示例运行

对 2025 的人工智能来说太复杂了

结论

发表回复 取消回复

相关文章：

随机动画

简单所见即所得在线HTML编辑器

Markdown HTML 转换工具

HTML Markdown 转换工具

CSS 玻璃效果生成器

将iOS风格的液体玻璃添加到您的网页

变种数字消消乐 – 令人沉迷的数字游戏

扑克魔术

懒人的俄罗斯方块游戏

人间血照，一个令人深思的游戏

纯 CSS 构建的《我的世界(Minecraft)》

大脑错觉：撒切尔效应

webassembly 二维布料仿真模型

升级版青蛙过河智力游戏

网页小游戏：戳破泡泡

CSS Grid 布局代码生成器

一个 Div 能做的事情

青蛙过河智力小游戏

数字消消乐

交互式演示教程教会你精通掌握 CSS Flexbox 布局

链接收藏

发表回复取消回复