此文尚未完工，可能还会有重大改动或者被废弃

基础

  • 定义：算法是 良定义的 有输入输出的 计算过程 (procedure)
  • 正确性：liveness （有限时间），safety （答案正确）
    • 分析：伪代码，正确性，复杂度
    • loop invariant, maintenance
  • 串行 (sequential) 算法
    • 技巧：分治，动态规划，贪心
    • 分治：“分”即分解为同构的、小规模的问题；“治”即递归解决。治后还需合并小问题结果。例如归并排序
    • 图算法：最小生成树，单源最短路
    • NP: 旅行商
  • 分布式 (distributed) 算法：多节点 (core, processor, machine, cluster) 互相通信
    • examples: C/S, 区块链
    • 基础抽象：时序 (timing) 假设，故障 (fault) 检测，广播（可靠，因果），Leader 选举，共识

算法复杂度

执行时间即指令数：假定所有指令（算术，访存，控制）都会耗等时，串行。

朴素计算方式：逐指令计数；考虑最佳/最坏/平均

增长量级 Order of growth：Θ (tight) 𝑂 (upper) Ω (lower) ；$f(n)=\Theta(g(n))$ 定义： $$ \exists n_0 \in \mathbb{N}, c_1,c_2>0, \forall n>n_0, 0\le c_1g(n)\le f(n) \le c_2g(n) $$

我们需要计算一些递归算法的复杂度，其具有 $T(n) =aT\left(\frac{n}{b}\right) + f(n)$ 的形式。有三种算法：代入法，递归树，主定理。

首先是报答案的主定理：$p=\log_b a, \epsilon>0$，则

  • $f(n)<\Theta(n^p)$ ($f(n)=\text{O}(n^{p-\epsilon})$): $T(n)=\Theta(n^p)$
  • $f(n)>\Theta(n^p)$ ($f(n)=\Omega(n^{p+\epsilon})$): $T(n)=\Theta(f(n))$
  • $f(n)=\Theta(n^p\log^k n)$: $T(n)=\Theta(n^p \log^{k+1}n)$

其次是精确而繁琐的递归树（手动计数）：

  • 每行 $a^k$ 个 $c_2 f(\frac{n}{b^k})$ 为合并时间
  • $0\le k\lt \log_b n$ 为递归深度，共 $\log_b n$ 行
  • 最下方 $a^{\log_b n}=n^{\log_b a}$ 个 $c_1$ 为 leaf 时间

幂函数和指数函数较为好算，其他形式就自求多福吧…

最后是不太可靠的的代入法（数学归纳法）：

  1. 猜测最终形式（此处均上界；下界直接丢掉额外项即可）
    1. case 1 $T(n)\le c_1 n^p - c_2 n^{p-\epsilon}$
    2. case 2 $T(n)\le c_1 n^p\log^{k+1} n - c_2 n^p\log^k n$
    3. case 3 直接代，$c^{-1}\le 1-\frac{af(n/b)}{f(n)}$ 恒成立
  2. 找到合适的 c 和起始 n

关于 NPC 问题，一图说明：

NPC Graph

  • P: 可以多项式时间内解决的
  • NP: 可以多项式时间内验证的；如 Hamilton 环，旅行商问题
  • NP-hard: 解决时间 >= 所有 NP
  • NP-complete: 既是 NP 也是 NP-hard

如何证明一个问题是 NPC 呢？

  • 若是决策问题 -> 用 reduction 转换为优化问题
  • 用多项式时间 reduction 转换为已知的 NPC 问题

一些 NPC:

  • 电路可满足性问题
  • 团问题 (clique) 与顶点覆盖 (vertex-cover) 问题

动态规划

动态规划通常用于优化问题，类似分治会分解为小问题；不同的是子问题会重叠、会共享依赖。动态规划的核心性质是最优子结构 + 重叠子问题

动态规划有两种等价形式：有记忆 (@functools.cache) 的 top-down，或是 bottom-up。通常先构造最优解结构，写出递归式，然后就可以写出算法，最好 bottom-up。

要使用动态规划，最优解结构通常长成：从子问题最优解的组合中做选择，就能得出父问题的最优解。同时，子问题空间不能太大（最好多项式），否则需要考虑更多优化了。

割绳子问题：$f(n)=t(f(1), f(2)…f(n-1))=max{p(n), f(i)+f(n-i)}$

  • 小优化：令 r[0]=0
  • store cut point: 只需额外 n 空间，存 p(i), p(n-i) 分割点；其他点可以回溯得到

最短公共子序列 (LCS) 问题：$n^2$ 子问题，c[i,j] 为 a.substr(0,i) 和 b.substr(0,j) 的 LCS 长度

def lcs(x: Sequence, y: Sequence) -> np.ndarray:
  m, n = len(x), len(y)
  # substr(0,0) lcs is always 0
  c = np.zeros((m+1,n+1), dtype=np.int64)
  for i in range(m):
    for j in range(n):
      # update on [1,m]x[1,n]
      if x[i]==y[j]:
        # can advance
        c[i+1,j+1] = c[i,j] + 1
      else:
        # inherit last optimal
        c[i+1,j+1] = max(c[i+1,j], c[i,j+1])
  return c

可以通过 c 回溯得到真正 LCS

def traceback_lcs(x: Sequence, y: Sequence, c: np.ndarray) -> list:
    lcs_sequence = []
    i, j = len(x), len(y)

    while i > 0 and j > 0:
        if x[i-1] == y[j-1]:
            # This element is part of the LCS
            lcs_sequence.append(x[i-1])
            i, j = i-1, j-1
        elif c[i-1, j] >= c[i, j-1]:
            i -= 1 # Move up
        else:
            j -= 1 # Move left
    lcs_sequence.reverse()
    return lcs_sequence

最优二叉搜索树 (Optimal BST)：把带 weight 的 leaf-node 交替出现的线段按某种方式成完全二叉树（前序遍历顺序同线段），使得 depth 加权和最小。

定义 e[i,j] 为 i 到 j 线段构成的 OBST cost，w[i,j] 为权重和（可用前缀和优化空间）。有 e[i,j]=min(e[i,r-1]+e[r+1,j]+w[i,j] for r in range(i, j+1)))。

def optimal_bst(w: ndarray) -> ndarray:
  """输入预计算的 w，输出 e"""
  n = w.shape[0]
  e = w * np.eye(n) # 对角线 = w[i,i]，其余为 0

  for l in range(2, n+1):
    for i in range(n-l+1):
      j = i+l-1
      e_ij = np.inf
      for r in range(i,j+1):
        left = e[i,r-1] if r>i else 0 # may out of bound
        right = e[r+1,j] if r<j else 0
        e_ij = min(e_ij, left + right)
      e[i,j] = w[i,j] + e_ij
  return e
当然也可以在过程中算 root 和 w （标准算法） 
def optimal_bst(p: list[float], q: list[float]) -> tuple[np.ndarray, np.ndarray]:
  """
  构造最优二叉搜索树（Optimal Binary Search Tree）。

  使用动态规划算法计算最优BST的期望搜索成本和结构。

  参数:
      p: list[float] - 长度为n的列表，p[i]表示搜索键k_i的概率 (i=1..n)
          注意：p[0]不使用，为了索引方便可以设为0
      q: list[float] - 长度为n+1的列表，q[i]表示虚拟键d_i的概率 (i=0..n)
          d_i表示在k_i和k_(i+1)之间的搜索失败

  返回:
      tuple[np.ndarray, np.ndarray]:
          - e: (n+2) x (n+2)数组，e[i,j]表示包含键k_i..k_j的子树的最小期望成本
          - root: (n+2) x (n+2)数组，root[i,j]表示最优子树的根节点索引

  示例:
      >>> p = [0.00, 0.15, 0.10, 0.05, 0.10, 0.20]
      >>> q = [0.05, 0.10, 0.05, 0.05, 0.05, 0.10]
      >>> e, root = optimal_bst(p, q)
  """
  n = len(p) - 1
  e = np.zeros((n + 2, n + 2))
  w = np.zeros((n + 2, n + 2))
  root = np.zeros((n + 1, n + 1), dtype=int)

  # 初始化 l = 1
  for i in range(1, n + 2):
    e[i, i - 1] = q[i - 1]
    w[i, i - 1] = q[i - 1]

  # 按子问题规模递增计算
  for l in range(1, n + 1):  # l是子树包含的键数量
    for i in range(1, n - l + 2):
      j = i + l - 1
      e[i, j] = np.inf
      w[i, j] = w[i, j - 1] + p[j] + q[j]
      for r in range(i, j + 1):
        cost = e[i, r - 1] + e[r + 1, j] + w[i, j]
        if cost < e[i, j]:
          e[i, j] = cost
          root[i, j] = r

  return e, root

贪心算法

本质上它是剪枝到一条链的反向 (top-down) 动态规划（未必满足重叠子问题），永不回溯/遍历其他的状态。它状态转移的特点就是：在贪心性质保证下，选择了一个父问题的最优解，用它来约束解决子问题。

贪心算法两个核心性质：贪心性质，最优结构。

它有很多应用，如最小生成树，Dijkstra 等等。

  • 活动选择问题：选择最早结束的
  • 离线缓存策略：逐出未来最远的

see also: 分数背包，0-1 背包

最小生成树 （Minimum Spanning Tree, MST)：无向图 G(V,E) 求最小权重和的生成树

算法：Prim （选集最短边，堆 heap），Kruskal（全局最短边，堆+并查集 disjoint set）

正确性证明：

  • 一些定义
    • cut: (S, V-S)
    • edge cross cut: edge (u,v) 有一点在 S 一点在 V-S
    • cut respect 边集: 边集任意边不 cross cut
  • 边选择：A 已为 MST 子集，(S, V-S) 为任意 respect A cut, cross (S, V-S) 的 light edge (u,v) 即为所选
  • 证明：若 MST 不含任何 cross (S, V-S) 的 light edge，MST 必有一个 (u’,v’) cross (S,V-S) 且 w(u’v’) > w(u,v)；由 min 有 w(E) ≤ w(E-(u’,v’)+(u,v)) 即 w(u’v’)，矛盾

最短路 Shortest Path：有向图 G(V,E) 求 u→v 之间最短路 $\delta(u, v)$

Dijkstra：非负权边，遍历最近点 relax；正确性：出队时，点已算出最短路

Floyd–Warshall：无负环；使用 DP，第 k loop 表示 i 经过 0-k 到达 j 的最短路；kij 顺序 $f_{ij}=\min(f_{ik}+f_{kj})$。正确性显然。负环：any(dist[v,v] < 0)

分布式算法

咱也不知道为什么算法导论要有分布式算法…但更多高质量的内容总比赤更多看似合题的无用内容好！

出于篇幅考虑，本章不会记录 Algorithm 实现；感兴趣的可以看 附件

分布式计算是有限多个 Process 参与的、互相能够感知并通信的计算过程。通常一个 Process 的 eventloop 包括

  1. 广播（接收） event
  2. 根据 event 计算，更新 local state

Configuration: 一个时刻的 C = (S1, S2, … Sn)

Event: 形如 <Instance, Action | Args>

  • instance 是一个算法的实现实例
  • action 是接口名，可以由算法定义（类似于 Go interface），也可以由实现自己定义（类似于 Class method）
  • args 是接口参数；可为空

Layer: 一个代码片段，通过 Request event 触发，正常完成后会触发 Indication event 给其他 Layer（除非 crash）

  • Request (send in) – layer –> (invoke out)；我们记作 Action(args)
  • Indication (deliver out) <– layer – (receive in)；我们记作 Action() (args)

Specification 是一个算法的设计文档，包括 name, instance, request, indication, properties。

算法实现则是各种 upon event Event do 和 trigger，不需要类型变量定义。

用一个 JobHandler spec 来看看 lsy 风格的 spec 
Name: JobHandler, instance jh.

Request: < jh, Submit | job >: Requests a job to be processed.

Indication: < jh, Confirm | job >: Confirms that the given job has been (or will be) processed.

Properties:
JH1. Guaranteed response: Every submitted job is eventually confirmed.

以及实现

Algorithm: Synchronous JobHandler
Implements: JobHandler, instance jh.
Note: Get familiar with the event-driven style

upon event < jh, Submit | job > do
	process(job);
	trigger < jh, Confirm | job >;

----------------------------------------------
Algorithm: Asynchronous JobHandler
Implements: JobHandler, instance jh.

upon event < jh, Init > do
	buffer := ∅;

upon event < jh, Submit | job > do
	buffer := buffer ∪ {job};
	trigger < jh, Confirm | job >;

upon buffer ≠ ∅ do
	job := popjob(buffer);
	process(job);
	buffer := buffer \ {job};

一些应用：

  • Service-Level Agreement (SLA) ：云厂商服务保证
  • 分布式储存: Google fs, Apache HDFS, Ceph,…
    • Configuration management module（配置管理模块）；五路
    • Metadata store（元数据存储）：Ceph
    • Data store（数据存储）：三路，机架感知
  • 大型数据库系统：Google Spanner, PingCAP TiDB, WeChat PaxosStore…

失败 Failure 是 Process 没有按实现程序正常运行下去。Falty Process 分为

  • Crash-stop: Process 程序可能停在任何位置
  • Crash-recovery: Process 程序可能暂时停止工作，但可以恢复并继续工作；实现技术包括 log, checkpoint, transaction 等等
  • Omission: 丢包，可能由于溢出/拥塞
  • Byzantine: 不受限制、任意；允许恶意行为，模拟入侵、漏洞等。（Authenticated Byzantine fault: 密码学原语不应因此失效）

通信太简单了！只要把报文包在链路上传就可以了！但有时链路由于满载/物理故障会丢包。

Link spec 如下：

  • Send(q: Process, m: Message)
  • Deliver() (p: Process, m: Message)

我们定义了三种 link，都需要实现上面的接口，但性质不同:

  • FairLossPointToPointLinks (fll)：
    1. Fair-loss: 若好 p 不停 Send(q,m)，则好 q Deliver 会收到无穷多 (p,m)
    2. Finite duplication: 若好 p 做有限个 Send(q,m)，则任意 q Deliver 会收到有限个 (p,m)
    3. No creation: 若 q Deliver 到 (p,m) 则它肯定由 p 发送过
  • StubbornPointToPointLinks (sl):
    1. Stubborn delivery: 若好 p Send(q,m) 一次，则 q Deliver 会无限次收到 (p,m)
    2. No creation
  • PerfectPointToPointLinks (pl):
    1. Reliable delivery: 若好 p Send(q,m) 一次，则 q 会收到 (p,m)
    2. No duplication: 若好 p Send(q,m) 一次，则 q 不会收到多次
    3. No creation

注：Perfect links 不保证 FIFO；本课程若无说明假定使用Perfect links

世界是随时间变化的，网络环境、程序好坏等都会变化，在实现消息传输的时候需要考虑这些问题；为了解决这些时序问题造成的消息传输问题，我们提出了一些模型

  • 同步系统：做假设，分轮
    • 传播延迟 (propagation)：消息传递所需时间存在一个已知的上限 ∆_𝑑𝑒𝑙𝑎𝑦
    • 处理时间：执行一个步骤所需的时间是有界且已知的 ∆_𝑝𝑟𝑜𝑐
    • 时钟漂移 (drift)：本地时钟与全局实时时钟之间的漂移 ∆_𝑑𝑟𝑖𝑓𝑡 是有界且已知的
    • 每轮 ∆_𝑑𝑒𝑙𝑎𝑦+ ∆_𝑝𝑟𝑜𝑐+∆_𝑑𝑟𝑖𝑓𝑡
  • 异步系统：完全不做假设
  • 最终同步系统：介于异步和同步之间
    • 存在一个未知的时间点 G（也常记作 GST, Global Stabilization Time）；
    • 对于所有 t ≥ G，以下成立：
      • 任意消息的传输延迟 ≤ ∆_delay；
      • 任意非故障进程执行本地步骤的时间 ≤ ∆_proc。
    • 注：G 和 ∆ 都不是事先已知的，协议必须在不知道它们的情况下工作
    • 意义：FLP 定理 指出，在纯异步系统中，即使只有一个进程可能崩溃，也无法保证达成共识。“最终同步”以一段不可用时间 G 的代价使我们有共识用了。
      • FLP 能被时序假设（FD，同步） / 无 failure / 随机化 解决

Failure 如何检测？

异步系统中 delta 可以为无穷大，导致无法可靠检测。同步系统中可以通过已知 ∆ 已知检测。

最终同步系统中，工程上会设置超时时间 T（经验值），∆ ≤ T 视为同步期而反之异步；T 也可以运行期自适应；更好的是，增加节点可以指数级降低因异步/无法形成 quorum 而导致系统不可用的概率。

Failure Detector spec 如下：

有多种 FD:

  • PerfectFailureDetector (P):
    • spec:
      • Crash() (p: Process)
    • property:
      • Strong completeness: 最终，所有挂的进程，会永久被所有正确进程检测
      • Strong accuracy: 如果收到 Crash(p) 那 p 确实挂了
    • 注：只有同步系统能实现
  • EventuallyPerfectFailureDetector (◇P)
    • spec:
      • Suspect() (p: Process)
      • Restore() (p: Process)
    • property:
      • Strong completeness
      • Eventual strong accuracy: 最终，好进程不会被任何好进程 suspect (suspect recv without restore)
    • 注：在最终同步系统上也能工作（一种实现：T 会自动探测直至 > 2∆）
  • GroupMembership (gm)
    • 注：对于错误检测器，每个节点可以自行维护可用节点表；但我们需要更强的性质，如对可用节点本身达成共识
    • spec: View() (id, M: Membership)
    • properties:
      • Monotonicity 单调性：id 严格增，新 M 不是旧 M 子集
      • Uniform Agreement: 不同节点同 id 的 View M 必相同
      • Completeness: 如果 p 挂了，最终所有进程都会收到不含 p 的 M
      • Accuracy: 如果进程收到不含 p 的 M 则 p 挂了

Leader 和选主也是分布式系统不可不尝的一部分：优点是更容易实现任务同步/协调，可以使用中心化算法；缺点是换主/单点瓶颈可能会拖慢。

  • LeaderElection (le):
    • spec: Leader() (p: Process)
    • property:
      • Eventual detection: 只要有好进程，最终会有好进程选为 leader
      • Accuracy: Leader(p) 说明，所有之前 leader 都挂过
  • EventualLeaderDetector (Ω)
    • spec: Trust() (p: Process)
    • property:
      • Eventual accuracy: 一段时间后，所有好进程都 trust 一些好进程
      • Eventual agreement: 一段时间后，所有好进程都 trust 相同好进程

Quorum 指的是参与决策所需的节点集合

  • Safety: 不脑裂 / Quorum 是 majority
  • Liveness: 存在一个 quorum 只包含好进程

因此坏节点必须小于半数，好节点必须多于半数，才能 Safe and Live。

广播看起来很简单：往所有进程 Send 就行了嘛！

  • BestEffortBroadcast (beb):
    • spec:
      • Broadcast(m: Message)
      • Deliver() (p: Process, m: Message)
    • properties:
      • Validity: 好进程 Broadcast(m)，所有好进程最终会 Deliver(p,m)
      • No duplication: Broadcast(m) 在一个进程上只会 Deliver 一次
      • No creation
    • 注：一个 Broadcast 发到一半挂了，也认为发送者非 correct
  • ReliableBroadcast (rb):
    • spec
    • properties:
      • Validity, Nodupl, Nocrea 继承 BEB
      • Agreement: 如果一些好进程 Deliver(x,m) 则所有好进程都会 Deliver(x,m)
  • UniformReliableBroadcast (urb):
    • spec
    • properties:
      • Validity, Nodupl, Nocrea 继承 BEB
      • Uniform agreement: 如果一些（无论好坏的）进程 Deliver(x,m) 则所有好进程都会 Deliver(x,m)
    • 注：需要多阶段才能实现；隐含暂时 fail 等同永久 fail。
  • Total Order Broadcast
    • spec
    • properties:
      • Validity: p 自己会 deliver
      • No duplication, No creation, (Uniform) aggreement 同前
      • Total order: 所有进程 deliver 顺序相同
    • 实现注：每一轮用单轮共识，在所有未排序消息中选择一个。

Consensus PPT 有足足 78 页！

共识是解决很多分布式问题的基础，如全序广播，状态机复制，原子提交。原始的共识模型：

  • 有一组进程，一部分可能会挂

  • 每个进程都能 propose，最终所有好进程都会 decide

  • Consensus (c)

    • spec:
      • Propose(v: Value)
      • Decide() (v: Value)
    • property:
      • Termination: 所有好进程都会 Decide 一些 v
      • Validity: No creation
      • Integrity: 一个 v 不会 Decide 两次
      • Agreement: 所有好进程 decide 相同

  • Uniform consensus (uc)

    • spec
    • properties:
      • Termnination, Validity, Integrity 同 C
      • Uniform Agreement: 所有进程 decide 相同

一些个实现

  • Consensus algorithm I: round id as leader, follower 会 deliver / 怀疑 leader；本质上是 ReliableBroadcast with round leader
  • Uniform Consensus algorithm II: N round decide current proposal

上面的 consensus 仅能实现单轮共识。工程上所说的共识是多轮共识，以支持State Machine Replication 和 Blockchain 等基础组件。Paxos 和 Raft 是两个最广为人知的多轮共识算法。

  • Uniform Consensus algorithm III:
    • with quorum 和 ◇P
    • round id as leader
    • read - gather - impose - ack - decide
    • 不阻塞：p 会到达 leader round
    • 坏 FD 会导致不会 Termination