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,则无需维护顺序,因为所有副本中的结果都相同。

Bipartisan Paxos 两党Paxos-即刻学术

在图 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) 或两者兼而有之。

Bipartisan Paxos 两党Paxos-即刻学术

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)。

Bipartisan Paxos 两党Paxos-即刻学术
Bipartisan Paxos 两党Paxos-即刻学术

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

给TA买糖
共{{data.count}}人
人已赞赏
分布式

共识解耦 Compartmentalized Consensus

2021-6-2 11:06:01

分布式

raft协议为什么有election和heartbeat timeout的区分?

2021-6-9 22:08:30

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索