hatsune miku, VOCALOID / 16TH / August 31st, 2023 - pixiv

The Read⁄Write Register Communication Abstraction

Read/Write Register 可以说是 sequential computing 中最重要，也最基本的通信元件。我们根据该 Register 是否被顺序执行序列被定义分为两类，不被顺序执行序列定义的称 Regular Register，另一类根据顺序执行序列的不同，被称为 Atomic Register 和 Sequential Register（分别对应原子性(Atomicity)也称线性一致性(linearizability)和顺序一致性(sequential consistency)）。

Regular Register

首先我们介绍 Regular Register，他是一个 single-writer/multi-reader(SWMR) 的 Register，可以执行write(v)和read()两个操作。其中有相关规定：当 read 操作没有与 write 并发时，read 返回当前值。当 read 操作与 write 并发时，read 返回 write 的值的一个或没在 write 之前的值。

这很自然的引入了 new/old inversion，当有操作序列write(1)、read()、write(2)、read()且四个操作均并发时，第一个 read 返回 2，第二个 read 返回 1。这是合法的，但是最终状态是 2，这就导致了 new/old inversion。

Atomic Register and Sequential Register

Atomic Register 是一个 multi-writer/multi-reader(MWMR) 的 Register，并且由名字可知，它不会出现 new/old inversion 问题。它的相关规定如下：所有操作都被看作是顺序执行的，将执行序列记为$ S $，如果$ op_1 $在$ op_2 $开始前终止，那么$ op_1 $在$ S $中出现在$ op_2 $之前。且每一个 read 操作都返回最近的 write 操作的值。

这样的序列$ S $被称作该 Register 的一个 linearization。注意到，上文中没有提到并发时的规定，这意味着并发时的顺序是任意的，因此一个执行顺序因为并发可能有不同的 linearization。

Sequential Register 是一个 multi-writer/multi-reader(MWMR) 的 Register，它与 Atomic Register 类似，只不过我们需要注意，在 Atomic Register 中，我们需要一个全局外部时钟来确定不同进程的操作的顺序，而在 Sequential Register 中，我们将其弱化为单个进程的操作顺序。即，对任意的$ p_i $，如果$ p_i $先执行了$ op_1 $，再执行了$ op_2 $，那么$ op_1 $在$ S $中出现在$ op_2 $之前。

最后，我们证明一下在$ CAMP_{n,t}[t \geq n/2] $中是无法实现的，在此，我们用到了 indistinguishability argument 的技巧。

我们将所有 process 分为两个子集$ P1 $和$ P2 $，其中$ P1 \cap P2 = \empty $、$ P1 \cup P2 = \{p_1,...,p_n\} $且$ |P1|=\lceil n/2 \rceil, |P2|=\lfloor n/2 \rfloor $。我们考虑这样的情况，在$ \tau_{write} $时间之前，$ P1 $中的一个进程执行了R.write(1)并在$ \tau_{write} $时间之前返回。在$ \tau_{read} $时间之前、$ \tau_{write} $时间之后，$ P2 $中的一个进程执行了R.read()并在$ \tau_{read} $时间之前返回。现在我们考虑如下两个情况：

  • $ E_1 $：所有的$ P_2 $中的进程在最开始崩溃，所有的$ P_1 $中的进程都是 non-faulty 的。
  • $ E_2 $：所有的$ P_1 $中的进程在最开始崩溃，所有的$ P_2 $中的进程都是 non-faulty 的。
  • $ E_{10} $：TODO

Read/Write Register 在$ CAMP_{n,t}[t < n/2] $下的实现

Implementing an SWMR Regular Register in $ CAMP_{n,t}[t < n/2] $

算法的主要思想是有一个写进程$ p_w $，它与一个 pair相关联，各个读进程保存它获得到的 sequence number 并实时更新最大值。每次write操作广播并等待至少大多数（超过半数）个进程。而每次read操作会广播自己的sequence number来查看是否其值是最大值。实际上，这就是 Quorum 的思想，也有 Quorum failure detector，即，$ \Sigma $。读者可自行查阅相关资料。具体来说，每个进程有如下本地变量：

  • $ reg_i $：进程$ p_i $保存的 Register 的值
  • $ wsn_i $：进程$ p_i $保存的与$ reg_i $相关联的 sequence number
  • $ regsn_i $：进程$ p_i $保存的上次读取的值所对应的 sequence number

算法的伪代码如下：

func REG.write(v):
    wsn_w = wsn_w + 1
    broadcast(Write<v, wsn_w>)
    wait(ACK_Write(wsn_w)) from a majority of processes
    return

func REG.read():
    regsn_i = regsn_i + 1
    broadcast(Read<regsn_i>)
    wait(ACK_Read(regsn_i, -, -)) from a majority of processes
    let v = v_i in ACK_Read(regsn_i, -, v_i) where regsn_i is the largest
    return v

when receive(Write<v, wsn>) from p_w:
    if wsn > wsn_w:
        wsn_w = wsn
        reg_w = v
    send(ACK_Write(wsn)) to p_w

when receive(Read<regsn>) from p_i:
    send(ACK_Read(regsn, wsn_w, reg_w)) to p_i

From an SWMR Regular Register to an SWMR Atomic Register

我们上述实现的 SWMR Regular Register 并不能保证 Atomicity，举例来说，我们现在有 5 个进程，其中值均为 14，现在一个write(15)被执行并更新了进程 1 和进程 2，如果此时一个read()被执行并且收到了进程 1、2、3 的 ACK，那么它会返回 15（因为进程 1、2 包含了 15），当这个read()执行完毕后又有一个read()被执行并收到了进程 3、4、5 的 ACK 且此时write(15)还没有被进程 3、4、5 执行，那么它会返回 14。而我们知道最终在write(15)执行完毕后，所有的read()都应该返回 15。这就是一个典型的 new/old inversion 问题。

造成上述的根本问题我们可以看出，是因为write的操作还没有更新大多数进程，read就开始执行。解决方法也很简单，当read操作时，让它执行一个write操作。具体来说，我们只需在上述伪代码中的func REG.read()，在该方法返回之前加上broadcast(Write<v, wsn>)和wait(ACK_Write(wsn)) from a majority of processes并且将接收到Write的进程p_w改为p_i即可。这样我们保证了在read操作返回之前，大多数进程也都已经更新了值。

From an SWMR Atomic Register to an MWMR Atomic Register

从 SWMR 转到 MWMR 的一个新问题就是我们如何保证所有进程都能够根据一个统一的 sequence number generator 来更新他们向寄存器所写的 sequence number。我们考虑如下想法，每个进程的在write时候都 broadcast 他们的$ wsn_i $，并收集到大多数进程的$ wsn_i $，随后将自己的$ wsn_i $ + 1，这看似能解决问题，但是考虑到write操作可能是并发的，有几率会出现两个进程的$ wsn_i $相同的情况。不过我们可以引入 timestamp 作为$ wsn_i $来解决这个问题。

timestamp 就是一个二元对，logical date 对于每个进程单调递增。我们需要保证 timestamp 的最大值，所以我们将其作以下定义：
$$ \langle sn_1, i \rangle < \langle sn_2, j \rangle \equiv ((sn_1 < sn_2) \lor (sn_1 = sn_2 \land i < j)) $$

具体来说，每次执行read或write操作时，每个进程首先广播自己的请求来获得最近的控制信息，即，timestamp。根据本地计算得出最新值，随后进行第二次广播来更新值。这种技巧被称为 two-phase algorithms，在各个领域都有应用。

上述所介绍的算法被称为 ABD algorithm，具体代码在此不表。

A Broadcast Abstraction Suited to the Family of Read/Write Implementable Objects

在上述中，我们实现了在$ CAMP_{n,t}[t < n/2] $下的 Register，自然我们会有一个疑问，是否有一个 broadcast abstraction 使得我们能在此之上能够实现上述算法且该 abstraction 是最小的。答案是肯定的，下面我们就来介绍 set-constrained delivery broadcast(SCD-broadcast)。实际上，它与 read/write registers 的 computability 是相同的。

Set-Constrained Delivery Broadcast

SCD-broadcast 与 URB-broadcast 类似，不过它 broadcast 消息，deliver 消息的集合。且相比于 URB-broadcast，它多了以下性质：

  • MS-ordering：若$ p_i $首先 deliver 了消息集$ ms_i $，随后 deliver 了消息集$ ms'_i $，那么对于任意的消息$ m \in ms_i $和$ m' \in ms'_i $，没有进程先 deliver 了包含$ m' $的消息集，随后 deliver 了包含$ m $的消息集。

如果 SCD-broadcast 去除掉上述性质且只能 deliver 单个消息，那么它就退化成了 URB-broadcast。

我们根据 MS-ordering 可以自然的定义一个偏序关系$ \mapsto_i $，如果$ p_i $先 deliver 了包含$ m $的消息集，随后 deliver 了包含$ m' $的消息集，那么$ m \mapsto_i m' $。因此，该算法的核心就在于保证如果有关系$ m \mapsto_i m' $，那么就没有关系$ m' \mapsto_j m $。

From SCD-Broadcast to an MWMR Atomic Register

我们介绍如下本地变量：

  • $ done_i $：一个 Synchronization Boolean variable。
  • $ reg_i $：进程$ p_i $保存的 Register 的值
  • $ tsa_i $：与$ reg_i $相关联的 timestamp，初始值为$ \langle 0, - \rangle $

算法的伪代码如下：

func read():
    done_i = false
    scd_broadcast(SYNC(i))
    wait(done_i = true)
    return reg_i

func write(v):
    done_i = false
    scd_broadcast(SYNC(i))
    wait(done_i = true)
    done_i = false
    scd_broadcast(Write<v, <tsa_i.date+1, i>)
    wait(done_i = true)

when scd-delivered({Write<v_j, <tsa_j.date, j>>, Write<v_k, <tsa_k.date, k>>, ..., SYNC(j), SYNC(k), ...}):
    let <date, writer> be the largest timestamp in the set
    if tsa_i < <date, writer>:
        tsa_i = <date, writer>
        reg_i = v in Write<v, <date, writer>>
    if exist k in SYNC(k) such that k == i:
        done_i = true

Atomic Snapshot Object and Atomic Counter

下面我们来介绍一下可以由 SCD-broadcast 实现的两个对象：Atomic Snapshot Object 和 Atomic Counter。由于它们的实现都与上述的 MWMR Atomic Register 十分类似，因此我们只介绍他们的相关定义。

Atomic Snapshot Object

Atomic Snapshot Object 是一个由数组 $ REG[1..m] $组成的 n 个 atomic register 的集合，它提供了两个操作：write(r, v)和snapshot()，其中前者将数组$ REG $的第$ r $个元素写为$ v $，后者返回数组$ REG $的一个快照。

Atomic Snapshot Object 通常被用作分布式协调或用来检查全局属性。

Atomic Counter

Atomic Counter 是一个 Counter Object，它提供了三个操作：increase()、decrease()和read()，其中前两个操作分别将计数器加一和减一，后者返回当前计数器的值。我们说increase()和decrease()是 commutative 的，即，如果一个进程先执行increase()后执行decrease()和先执行decrease()后执行increase()，最终 object 的状态是等价的。这其实是 CRDT(Conflict-free Replicated Data Type) 的主要思想。CRDT 有两种主要的形式：CvRDT 和 CmRDT，在实际应用中 Riak 就使用了 CRDT 来解决分布式冲突。关于 CRDT 的更多内容，有以下几篇文章作为参考：

Last modification：August 31, 2023
© Allow specification reprint