Bipartisan Paxos 两党Paxos

两党派的Paxos（BPaxos）。BPaxos 是一系列协议，它实现了三件事：低延迟（2 条消息延迟）、高吞吐量（无领导）和简单性（模块化）。

BPaxos 系列由简单的 BPaxos、一致的 BPaxos和大多数提交 BPaxos 组成。出于教育目的，这些协议之间还有一些其他协议（Unsafe BPaxos 和 Deadlock BPaxos），但不是最终 BPaxos 协议的一部分。BPaxos在论文中呈现的方式类似于Avalanche BFT 协议。

BPaxos 不维护其日志的总顺序，而是维护一个有向图来解决冲突命令。这个有向图称为冲突图或部分 BPaxos 图。那么，什么是冲突图？

冲突图是一个有向无环图 C = (V, E, φ) 其中 V 是顶点，E 是一组边，φ: V → Cmd 是一个用命令标记每个顶点的函数。当且仅当 φ(v1) 和 φ(v2) 冲突时，每对顶点 v1,v2 ∈ V 在 v1 和 v2 之间都有一条边。

冲突命令被定义为两个命令 x 和 y 不能交换，例如，x*y ≠ y*x。如果它们确实可以交换，x，y，则无需维护顺序，因为所有副本中的结果都相同。

在图 1 中，总排序如图 (a) 所示。

在图 1 中，部分 BPaxos 图如图（b）所示。

BPaxos 为每个命令分配一个称为实例的唯一标识符，参见图 1b。

如果实例 (I) 的对发生冲突，则它们之间存在边。例如，deps(I5)={I1,I4} BPaxos 协议有两个基本不变量来保证 BPaxos 的正确性。

不变量 1. 分为两件事：一致性：在实例 I 中最多选择一个值 (x,deps(I))，以及非平凡性：如果选择了值 (x,deps(I))，那么它是之前的建议的。

不变量 2. 如果在实例 Ix 中选择 (x,deps(Ix )) 并且为实例 Iy 选择 (y,deps(Iy ))，并且如果 x 和 y 冲突，则 Ix ∈ deps(Iy ) 或 Iy ∈ deps(Ix) 或两者兼而有之。

Simple BPaxos 是 BPaxos 中第一个也是简单的协议。它具有以下三个组成部分：

1- 保持不变式 1 和 2 的简单 BPaxos 节点的数量。

2- 维护不变量的依赖服务节点2.

3- 维护不变量的共识服务节点1。

简单的 BPaxos 协议从客户端发送命令到简单的 BPaxos 节点开始执行。 BPaxos 收到客户端命令后，为命令分配实例 I 并以元组形式 (I, x) 转发给 2f+1 个依赖服务节点。依赖服务是一种跟踪所有依赖的服务。依赖服务节点回复 (I,x, deps(I))。从依赖服务节点 Q = (f+1) 接收到，简单的 BPaxos 节点 Bi 将所有回复的联合并提出值给实例 I 中的共识服务。 共识服务为每个实例 I 实现共识，例如 Paxos。共识服务在无故障情况下回复选择的值 (x,deps(I))。简单的 BPaxos bi 将值添加到其最终要执行的日志中。最后，简单的 BPaxos bi 将其值通知其他简单的 BPaxos 节点（有关更多说明，请参见图 2,3）。

在 Simple BPaxos 中，存在活性问题。为了从此问题中恢复，该协议使用 noop 命令。如果 bi 注意到 I' 没有选择，一段时间后，bi 可以向共识服务节点提议在没有依赖关系的实例 I' 中选择命令 noop。