Arknights, Arknights, Arknights / 小羊\~ - pixiv

Intro. and Reliable Broadcast Abstraction

Introduction

Distributed Systems

一个分布式系统可以看作一个无向图G=(V,E)，其中V是一组进程，E是一组通信链路。E指向了G的属性，常见的分布式系统图有Ring(环)、Tree(树)、Clique(团/全连通图)等。

一个分布式算法可以看作 n 个自动机的集合，每个自动机可以在 Message-Passing 系统中执行 send() 方法或 receive() 方法，自动机之间通过通信链路通信。而在一个 Synchronous(同步) 算法中，分布式系统由一个外部全局单调时钟控制，每个自动机的每一轮与该时钟相关联。因此，有偏序关系 E，即，每个在 r 轮中执行的事件一定都早于在 r+1 轮中执行的事件。在 Asynchronous(异步) 算法中，分布式系统没有全局时钟，所以异步算法也称 time-free 算法。

常见 Fault 抽象：

  • Crash failure：进程可能会崩溃，在进程崩溃后，进程不会再执行任何操作。
  • Channel Failure：通信链路可能会崩溃，在某一段时间内，通信链路会丢失所有消息。

Example: Two Generals Problem

Two Generals Problem 是一个经典的分布式算法问题，描述如下：

两个将军分别带领各自的军队进攻敌方，两军需要同时进攻，否则会被敌方击败。两将军之间通过信使传递消息，但是信使可能会被敌方截获，因此两将军需要通过某种方式达成一致，使得两军同时进攻。

首先我们对两将军问题进行抽象：两方进程各有一个本地变量 state 和 done，state 表示进程的状态，done 表示进程是否已经完成。其中$ state_i \in \{0,1\} $，$ done_i \in \{no,yes\} $。进程$ p_1 $执行repeat send DECIDE(state_1) to p_2 until ACK(DECIDE) from p2，这样$ p_2 $首先等待信息，随后repeat send ACK(DECIDE) to p_1 until ACK^2(DECIDE) from p_1。但是若如此，进程$ p_1 $还需要重复发送ACK造成了循环。

实际上，两将军问题是无解的。我们来简单证明：

假设存在这样的最简算法A求解两将军问题，不失一般性，我们假设进程p1执行最少的操作且考虑p1最后发送的消息m。首先p1的终止与否一定不取决于m是否被p2接收。因为p1发送完m后终止，而m是否被接收是不一定的。相似的，p2的终止与否也一定不取决于m，因为m的接受与否对p1不可见，因而也不会影响p2的终止。因此，消息m是无用的，我们可以剔除发送消息m来获得一个更简单的算法A'。这与A是最简算法的假设矛盾，因此两将军问题无解。

Common Models

常见的分布式系统模型根据进程是否同步和进程错误类型的不同，可以简单分为以下几种：$ CAMP[\emptyset] $、$ CSMP[\emptyset] $、$ BAMP[\emptyset] $、$ BSMP[\emptyset] $。（C 代表 Crash-failure，B 代表 Byzantine-failure，A 代表 Asynchronous，S 代表 Synchronous，MP 代表 Message-Passing）

Enriched Model：$ CAMP_{t,n}[t < n/2] $，即，共有 n 个进程，其中可能发生崩溃的进程数量t小于n/2。

Weakened Model：$ CSMP_{t,n}[-FC] $，即，在基本模型的基础上，受到通信链路故障(Fair Channel)的影响。

并行计算与分布式计算的区别：并行计算注重于一个问题被分解为多个子问题，而分布式计算注重于在已知前提下进程之间的通信合作。

Uniform Reliable Broadcast

我们首先考虑在$ CAMP[\emptyset] $模型下，如何实现一种可靠的广播，它能够将操作broadcast(m)正确的传递给所有Correct的进程。

Uniform Reliable Broadcast(URB)是一种可靠的广播，它有两个基本操作URB_broadcast(m)和URB_deliver(m)。URB_broadcast(m) 是一个发送操作，它将消息 m 发送给所有进程（包括自己），而 URB_deliver(m) 是一个接收操作，它将消息 m 传递给上层。URB 的性质如下：

  • validity：如果一个进程 deliver 了一个消息 m，那么这个消息一定是由某个进程 broadcast 的。
  • integrity：如果一个进程 deliver 了一个消息 m，那么这个消息一定只被 deliver 一次。
  • termination1：如果一个 non-faulty 进程 broadcast 了一个消息 m，那么该进程一定会 deliver 该消息。
  • termination2：如果一个进程 deliver 了一个消息 m，那么所有 non-faulty 进程一定会 deliver 该消息。

我们可以根据上述条件轻而易举的推断出：所有 non-faulty 进程都会 deliver 一个相同的消息集合，该集合包含所有 non-faulty 进程 broadcast 的消息。而每个 faulty 进程会 deliver 该集合的任意一个子集。

基于一个 Reliable Channel，我们可以轻易的给出如下伪代码：

func urb_broadcast(m):
    send(m) to p_i (itself)

when receive(m) from p_k:
    if first time receive m:
        send(m) to p_j for each j in {1, ..., n}\{i, k}
        urb_deliver(m)

增加服务

FIFO-URB Broadcast：FIFO-URB Broadcast 是 URB Broadcast 增加了 FIFO 特性的版本，其中 FIFO 特性如下：

  • FIFO message delivery：如果一个进程先 broadcast 了消息 m1，随后 broadcast 了消息 m2，那么所有进程一定会先 deliver m1，随后 deliver m2。

为了实现 FIFO-URB，我们需要两个本地变量，$ msg\_ set_i $被用作记录已经被 urb-deliver 但还没有被 fifo-deliver 的消息集合。$ next_i[1..n] $中$ next_i[j] $记录了下一个将要被 fifo-deliver 的来自进程 j 的消息序号（进程第一个 broadcast 的序号为1，随后递增）。伪代码如下：

func fifo_broadcast(m):
    m.sender = i
    m.seq = next_i[i]
    urb_broadcast(m)

when MSG m is urb_delivered:
    let j = m.sender
    if m.seq == next_i[j]:
        fifo_deliver(m)
        next_i[j] = next_i[j] + 1
        while have m' in msg_set_i such that m'.sender == j and m'.seq == next_i[j]:
            fifo_deliver(m')
            next_i[j] = next_i[j] + 1
            msg_set_i.remove(m')
    else:
        msg_set_i.add(m)

Reliable Broadcast in the Presence of Process Crashes and Unreliable Channels

上述的 URB 和 FIFO-URB 都是在$ CAMP[\emptyset] $模型下实现的，即，通信链路是可靠的，现在我们考虑在不可靠的通信链路下如何实现可靠的广播。

Fair Channel(FC)：Fair Channel 是一种不可靠的通信链路，它有两个基本操作send(m)和receive(m)。Fair Channel 的性质如下：

  • validity：如果一个进程 receive 了一个消息 m，那么这个消息一定是由某个进程 send 的。
  • integrity：对于任意的消息 msg，如果 $p_j$ receive 了从 $p_i$ 发送的 msg 无数次，那么 $p_j$ 一定 receive 了 msg 无数次。
  • termination：对于任意的消息 msg，如果 $p_i$向 $ p_j $ send 了 msg 无数次，且 $p_j$ 一直执行 receive 操作，那么 $p_j$ 一定 receive 了 msg 无数次。

注意 Fair Channel 的属性，他只保证了在无数次条件下，进程可以 receive 无数次，没有保证进程在有限次 send 中一定能够 receive。

我们主要根据重发操作来防止 Fair Channel 造成的信息丢失，由于 FC 的属性，我们知道我们一定要发送每个消息无数次。此外，我们只能实现在$ CAMP_{n,t}[-FC, t < n/2] $模型下的可靠广播，因为在$ CAMP_{n,t}[-FC, t \geq n/2] $模型下，此问题是无解的。

我们主要依靠本地变量$ rec\_by_i $来实现可靠广播，其中$ rec\_by_i[m] $为进程$ p_i $已知的所有 receive 消息 m 的进程集合。此外，|rec_by_i[m]| >= t+1保证了至少有一个 non-faulty 进程 receive 了消息 m。伪代码如下：

func broadcast(m):
    send(m) to p_i (itself)

when receive(m) from p_k:
    if first time receive m:
        allocate rec_by_i[m]
        rec_by_i[m].add(k, i)
        acticate task Diffuse(m)
    else:
        rec_by_i[m].add(k)

task Diffuse(m):
    while forever:
        send(m) to all processes

when |rec_by_i[m]| >= t+1 AND p_i has not deliver m:
    deliver(m)

注意到 Diffuse 任务始终在后台运行，当 $ p_i $在 $ p_j $ broadcast 之前崩溃时，$ p_j $会一直向 $ p_i $发送消息 m，所以如果我们知道关于进程错误的相关消息，我们就可以阻止这些无用的无止境的重发，这便是 Quiescent uniform reliable broadcast(QURB)的思想。不过，我们首先需要知道进程错误的信息，所以让我们先介绍一下 Failure Detector。

Failure Detector

Failure Detector 可以看作是由多个模块组成的，可以向进程提供关于进程错误知识的，一种根据属性被划分为不同类的抽象。Failure Detector 描述了在某个 Failure Pattern 下，进程的错误情况。关于 Failure Detector 的一些定义如下：

  • $ F(\tau) $：在时间点 $ \tau $，崩溃的进程集合。
  • $ Faulty(F) $：$ F(\tau_{max})，\tau_{max} = +\infty $，即，最终崩溃的进程集合。
  • $ Correct(F) $：$ \{1, ..., n\} - Faulty(F) $，即，最终没有崩溃的进程集合。

一些常见的 Failure Detector 如下：

  • $ \Theta $：每个进程被提供了本地变量 $ trusted_i^\tau $，Accuracy 保证了在任何时间，$ trusted_i^\tau $总至少含有一个正确的进程，而 Liveness 保证了在某个时间以后，任何 non-faulty 的进程的 $ trusted_i^\tau $都只包含 non-faulty 进程。

    • Accuracy：$ \forall \tau, \forall i: (trusted_i^\tau \cap Correct(F)) \neq \emptyset $
    • Liveness: $ \exists \tau, \forall \tau' \geq \tau: \forall i \in Correct(F): trusted_i^{\tau'} \subseteq Correct(F) $

  • $ P $(Perfect failure detectors)：每个进程被提供了本地变量 $ suspected_i^\tau $，Completeness 保证了在某个时间以后，任何 non-faulty 的进程的 $ suspected_i^\tau $都只包含 faulty 进程，而 Strong Accuracy 保证了在任何时间，$ suspected_i^\tau $一定不含有正确的进程。

    • Completeness：$ \exists \tau: \forall \tau' \geq \tau: \forall i \in Correct(F), \forall j \in Faulty(F): j \in suspected_i^{\tau'} $
    • Strong Accuracy：$ \forall \tau, \forall i,j \in Alive(\tau): j \notin suspected_i^{\tau}, Alive(\tau)=\Pi-F(\tau) $

  • $ \Diamond P $(Eventually Perfect failure detectors)：与 $ P $ 类似，但是 Strong Accuracy 被替换为 Eventual Strong Accuracy。

    • Completeness：$ \exists \tau: \forall \tau' \geq \tau: \forall i \in Correct(F), \forall j \in Faulty(F): j \in suspected_i^{\tau'} $
    • Eventual strong accuracy：$ \exists \tau: \forall \tau' \geq \tau: \forall i, j \in Alive(\tau'): j \notin suspected_i^{\tau'} $

Quiescent Uniform Reliable Broadcast

Quiescent Uniform Reliable Broadcast(QURB)是一种可靠的广播，它的 quiescence 属性被定义为：如果一个进程对它需要传递给其他进程的所有消息都只需要发送有限次，那么该进程是 quiescence 的。一个在 $ CAMP_{n,t}[\Theta,P] $ 模型下的 QURB 算法如下：

func broadcast(m):
    send(m) to p_i (itself)

when receive(m) from p_k:
    if first time receive m:
        allocate rec_by_i[m]
        rec_by_i[m].add(k, i)
        acticate task Diffuse(m)
    else:
        rec_by_i[m].add(k)
    send(ack(m)) to p_k

when receive(ack(m)) from p_k:
    rec_by_i[m].add(k)

when trusted_i include in rec_by_i[m] AND p_i has not deliver m:
    deliver(m)

task Diffuse(m):
    repeat:
        for each j in {1, ..., n}\rec_by_i[m]:
            if j not in suspected_i:
                send(m) to p_j
    until rec_by_i[m] union suspected_i = {1, ..., n}

实际上，该算法不仅是 quiescent 的，还是 terminating。而 terminating 是一个比 quiescent 远严格的属性。这是因为我们选取的 Failure Detector 是 $ P $，而如果我们选取$ \diamond P $，由于最终 accuracy，我们可以知道算法是 quiescent 的，但不是 terminating 的。

Last modification：August 31, 2023
© Allow specification reprint