The Client

发送<REQUEST, o, t, c>${\sigma}_c$请求信息给primary节点

o: operation

t: timestamp 保证该请求只会执行一次

c: client信息

${\sigma}_c$ ： client的签名

Replica（包含primary在内）发给client的信息包括 view number，以便client追踪最新的view和推导出primary, client会将请求信息发给它认为的primary。

Replica直接将结果信息返回给client， 信息是<REPLY, v, t, c, i, r>

i: replica的number

r: result

t: 请求的timestamp

client等待f+1个r和t相同的由不同的Replica有效签名信息，若client收不到足够多的此信息，会重新给所有replica广播请求，若replica处理过此请求，则重发处理结果； 若replica没有处理过该请求，且replica不是primary，则将请求转发给primary。 对于primary， 若它确定已广播过该请求，则会怀疑没有足够的replica跟随它而产生view change。

Normal-Case Operation

pre-prepare

<PRE-PREPARE, v, n, d>${\sigma}_p$ , m>

n: primary给client发过来的请求分配一个序列号n，n不一定和上一个pre-prepare序号连续

m: client的request

d: digest，m的摘要

p: primary

Backup（primary以外的replica）接受pre-prepare的条件如下

  1. Request带有签名，request是正确的，request的摘要确实是d
  2. Pre-prepare信息属于view v
  3. 对于<v, n>下的d不相同是不接受的
  4. $n\in [h,H]$ ,防止恶意耗尽n

prepare

<PREPARE, v, n, d, i>${\sigma}_i$

Replica将此消息加入日志的条件：

  1. 签名正确
  2. v是当前view
  3. $n\in [h,H]$
  4. i 本节点的编号

经过pre-prepare和prepare后，得出的结论

Prepared(m,v,n,i)正确的条件是当且仅当 $Replica_i$ 已经将请求插入日志， $Replica_i$ 将请求插入日志的判断如下：

  1. 自己的Pre-prepare中的m、v与其他2f个replica一致
  2. Pre-prepare和prepares是否有相同的v、n、d

pre-prepare和prepare阶段是为了保证view中request的总顺序：

  1. 假设某个Prepared(m,v,n,i) 为 true, Prepared(m‘,v,n,j)为false， i=j，(若$Replica_i$ 是fault，有可能发送这种错误信息)，我们还是可作出判断，因为我们已确定至多有f个fault Replica，2f+1个节点中no-fault Replicas至少有f+1个

commit

$Replica_i$ 认为Prepared(m,v,n,i) 为true时，会给其他所有Replicas广播commit消息，消息如下

<COMMIT, v, n, D(m), i>${\sigma}_i$

消息被其他Replicas接收的条件如下：

  1. 签名正确

  2. v时当前的view

  3. $n\in [h,H]$

结束提交阶段为true的有两种

  • Committed: 确定f+1个no-fault Replicas的Prepared(m,v,n,i) ($i\in {no-fault \ replicas \ id}$)为true
  • Committed-local: 当前Prepared(m,v,n,i) 为true，和接收到2f个replica的commit

Garbage Collection

<CHECKPOINT, n, d, i> ${\sigma}_i$

n : 最后一个以有状态输出的request number

d: digest of n

i: Rreplica’s number

收到2f+1个（包括自己）CHECKPOINT的n、d有相同，则认为此checkpoint可信，并删除所有checkpoint的request之前的log

[h, H]中，h等于最新可信checkpoint的request number。H = h+k, k要足够大，以至于足够等待下一次可信checkpoint。比如每100 request生成一个checkpoint，k可以设为200

View Changes

原因

避免无限期等待request

等待超时计算

首先request需要收集足够多有效决定，节点才会执行该request。当一个节点收到一个有效、未执行过的request，会进入等待其他节点的回应，并启计时，若能在有效期限内收集到足够的决定，则停止计时，处理request；若未能在有效期限内收集到足够多的决定，则启动一个View Changes。请求 v–> v+1

View Changes

  • 停止接收request相关消息，继续接收checkpoint、view-changes、new-view 等消息

  • 广播view changes请求消息 $<VIEW-CHANGE, V+1, n, C, P, i>{\sigma}_i$

    • n 当前节点 i 所知道的最新checkpoint
    • C 证明这个checkpoint收集到的2f+1个决定
    • n之后证明所有prepared request的决定的集合，就是$P_m$ 代表该决定的2f集合

  • v+1中的primary，收到2f个节点有效的view-change，则广播消息 $<NEW-VIEW, v+1, V, O>{\sigma}_i$

    • V 收集到的有效2f个view-change集合
    • O 从prepared转过来的pre-prepare，由primary决定

  • primary将O集合消息加入日志

  • 如果收到的最小checkpoint大于当前primary的checkpoint，则更新

参考

Castro M, Liskov B. Practical Byzantine fault tolerance[C]//OSDI. 1999, 99(1999): 173-186.