拜占庭容错寄存器算法解析

### 拜占庭容错寄存器算法解析 #### 1. 引言 在分布式系统中，处理拜占庭故障是一个极具挑战性的问题。拜占庭故障意味着进程可能会任意出错，返回错误的数据或行为异常。本文将深入探讨几种用于实现拜占庭容错寄存器的算法，包括拜占庭安全寄存器和拜占庭规则寄存器的相关算法。 #### 2. 拜占庭安全寄存器 ##### 2.1 接口与属性 - **模块名称**：(1, N)-ByzantineSafeRegister，实例为bonsr，有一个写入者w。 - **事件**： - 请求：⟨bonsr, Read ⟩ 用于发起读操作。 - 请求：⟨bonsr, Write | v ⟩ 用于发起写操作，仅由写入者w执行。 - 指示：⟨bonsr, ReadReturn | v ⟩ 完成读操作并返回值v。 - 指示：⟨bonsr, WriteReturn ⟩ 完成写操作，仅在写入者w处发生。 - **属性**： - BONSR1：终止性，若正确进程发起操作，操作最终会完成。 - BONSR2：有效性，非并发的读操作返回最后写入的值。 ##### 2.2 规范说明 (1, N) 拜占庭安全寄存器与 (1, N) 规则寄存器在崩溃停止故障模型下基本相同，但有效性属性对并发操作的返回结果未作规定。仅非并发的读操作必须返回最后写入的值，否则安全寄存器可返回其值域内的任意值。 在任意故障系统模型中，假设读写进程仅会出现崩溃故障，不会有任意（拜占庭）故障。这是因为定义由拜占庭进程操作的寄存器存在固有困难，任意故障的写入者可能会以复杂方式影响正确进程返回的值。 ##### 2.3 拜占庭掩码法定人数算法 该算法适用于 N > 4f 的情况，是一种无签名的算法，依赖拜占庭掩码法定人数。 - **写操作**：写入者增加时间戳，将时间戳/值对发送给所有进程，并期望 N - f 个进程回复确认。 - **读操作**：读者从超过 (N + 2f)/2 个进程接收时间戳/值对，过滤掉出现 f 次或更少的对，选择时间戳最高的对中的值。若过滤后无对剩余，选择默认值 v0。 ```python Algorithm 4.14: Byzantine Masking Quorum Implements: (1, N)-ByzantineSafeRegister, instance bonsr, with writer w. Uses: AuthPerfectPointToPointLinks, instance al. upon event ⟨bonsr, Init ⟩do (ts, val) := (0, ⊥); wts := 0; acklist := [⊥]N; rid := 0; readlist := [⊥]N; upon event ⟨bonsr, Write | v ⟩do // only process w wts := wts + 1; acklist := [⊥]N; forall q ∈Π do trigger ⟨al, Send | q, [WRITE, wts, v] ⟩; upon event ⟨al, Deliver | p, [WRITE, ts′, v′] ⟩such that p = w do if ts′ > ts then (ts, val) := (ts′, v′); trigger ⟨al, Send | p, [ACK, ts′] ⟩; upon event ⟨al, Deliver | q, [ACK, ts′] ⟩such that ts′ = wts do acklist[q] := ACK; if #(acklist) > (N + 2f)/2 then acklist := [⊥]N; trigger ⟨bonsr, WriteReturn ⟩; upon event ⟨bonsr, Read ⟩do rid := rid + 1; readlist := [⊥]N; forall q ∈Π do trigger ⟨al, Send | q, [READ, rid] ⟩; upon event ⟨al, Deliver | p, [READ, r] ⟩do trigger ⟨al, Send | p, [VALUE, r, ts, val] ⟩; upon event ⟨al, Deliver | q, [VALUE, r, ts′, v′] ⟩such that r = rid do readlist[q] := (ts′, v′); if #(readlist) > (N + 2f)/2 then v := byzhighestval(readlist); readlist := [⊥]N; trigger ⟨bonsr, ReadReturn | v ⟩; ``` - **正确性**：假设 N > 4f，该算法实现了 (1, N) 拜占庭安全寄存器。终止性显而易见，因为有 N - f 个正确进程，算法仅等待超过 (N + 2f)/2 个消息。有效性可通过拜占庭掩码法定人数保证，非并发的读操作返回最后写入的值。 - **性能**：该算法与故障静默模型下的规则寄存器算法使用相同数量的消息，每个操作使用一次通信往返和 O(N) 个消息。 #### 3. 拜占庭规则寄存器 ##### 3.1 规范说明 (1, N) 拜占庭规则寄存器与 (1, N) 规则寄存器基本相同，但明确标识了写入者 w，并限制读写进程为崩溃故障，如拜占庭安全寄存器一样。 ##### 3.2 认证数据拜占庭法定人数算法 该算法借助数字签名解决了之前算法的问题，实现了 (1, N) 拜占庭规则寄存器，且具有更好的弹性，仅需 N > 3f。 - **原理**：写入者对时间戳/值对签名并存储在进程中，读者验证接收到的每个时间戳/值对的签名，忽略无效签名的对。 ```python Algorithm 4.15: Authenticated-Data Byzantine Quorum Implements: (1, N)-ByzantineRegularRegister, instance bonrr, with writer w. Uses: AuthPerfectPointToPoint ```