算法理论

$$ t_B(x) \approx \bar{t}_A(n) + s(n) $$ 这里$t_B(x)$是算法B在实例x上的期望值，s(n)是概率算法B为了取得均匀性所付出的成本。

虽然算法B的执行时间也可能偶然地在某一个实例x上$»\bar{t}_A(n) + s(n)$，但这种偶然性行为只是由于算法所做的概率选择引起的，与实例x本身没有关系。因此，不再有最坏情况的实例，但有最坏的执行时间。

Sherwood 一般方法是：

1. 将被解的实例变换到一个随机实例。// 预处理  
2. 用确定算法解此随机实例，得到一个解。  
3. 将此解变换为对原实例的解。 // 后处理 

Las Vegas算法

特点： 可能不时地要冒着找不到解的风险，算法要么返回正确的解，要么随机决策导致一个僵局。若算法陷入僵局，则使用同一实例运行同一算法，有独立的机会求出解。成功的概率随着执行时间的增加而增加。

首先我们来看看LV算法与Sherwood算法的比较：

• Sherwood算法不算很优，因为它只改进确定性算法的最坏情况，所以平均执行时间与确定性算法相差无几。为了提高平均执行时间，就采用Las Vegas算法。
• Sherwood算法能够计算出一个给定实例的执行时间上界，因为它总是能够正确运行，所以每次都有一定的执行时间，取最大值就是上界。Las Vegas的时间上界可能不存在，因为它可能找不到解陷入死循环。

算法的一般形式：

LV(x, y, success) —— x 是输入的实例，y 是返回的参数，success是布尔值， true 表示成功，false 表示失败

$p(x)$ —— 对于实例x，算法成功的概率

$s(x)$ —— 算法成功时的期望时间

$e(x)$ —— 算法失败时的期望时间

设$t(x)$是算法找到一个正确解的期望时间，易得 $t(x)=p(x)s(x)+(1-p(x))(e(x)+t(x))$

解得 $t(x) = s(x) + \frac{1 - p(x)}{p(x)} e(x)$

Monte Carlo算法

特点： MC算法偶然会犯错，但它无论对何实例均能以高概率找到正确解。当算法出错时，没有警告信息。

定义1：设p是一个实数，且1/2<p<1，若一个MC算法以不小于p的概率返回一个正确的解，则该MC算法称为p-正确，算法的优势（advantage）是 p-1/2.

定义2：若一个MC算法对同一实例决不给出两个不同的正确解，则该算法称是相容的（consistent）或一致的。

定义3：(偏真算法)为简单起见，设MC(x)是解某个判定问题，对任何x，若当MC(x)返回true时解总是正确的，仅当它返回false时才有可能产生错误的解，则称此算法为偏真的(true-biased)。

定义4：(偏$y_0$算法)更一般的情况不再限定是判定问题，一个MC是偏$y_0$的($y_0$是某个特定解)，如果存在问题实例的子集$X$使得：

若被解实例$x\notin X$，则算法MC(x)返回的解总是正确的(无论返回$y_0$还是非$y_0$)；若$\forall x \in X$，正确解是$y_0$ ，但MC并非对所有这样的实例$x$都返回正确解。

$\implies$ 若返回$y_0$，解一定正确。

设MC是一个一致的、$p$-correct和偏 $y_0$ 的蒙特卡洛算法，$x$ 是一个实例，$y$ 是MC(x)返回的解，可分为如下2种情形讨论：

case1: $y=y_0$

若$x\notin X$，则算法MC总是返回正确解，因此 $y_0$ 确实是正确的。

若$x\in X$，算法返回的正确解必定是 $y_0$。这两种情况均可得到结论：$y_0$ 是一个正确解。

case2: $y \ne y_0$

若$x\notin X$，则 $y$ 是正确解。

若$x\in X$，因为正确解是 $y_0$，故 $y$ 是错误解，此出错概率不超过 $1-p$。

例： 重复调用一个一致的，$p$-正确的，偏真的MC算法$k$次，可以得到一个出错概率是多少的算法？

由单个算法出错概率为$(1-p)$得， 得出全错概率为全错：$(1-p)^k$

分布式算法

分布式计算和并行计算区别：

• 分布式计算的任务通常是相互独立的且实时性要求不高，这样哪怕一台机器出故障，也不影响其他机器，只需要重新启动一个机器去执行；
• 并行计算是实时性高，且任务之间相关性强。

分布式系统的难点在于：

• 缺乏全局时间（无法保证所有机器的绝对时间和相对时间都确定）

• 缺乏全局状态信息（不存在全知全能的上帝）

• 缺乏统一模式

  • 输入不同
  • 消息顺序不同
  • 执行速率不同
  • 故障不同

分布式模型：

• 异步共享存储模型：用于紧耦合机器，通常情况下各处理机的时钟信号不是来源于同一信号源
• 异步msg传递模型：用于松散耦合机器及广域网
• 同步msg传递模型：这是一个理想的msg传递系统。该系统中，某些计时信息（如msg延迟上界)是已知的，系统的执行划分为轮执行，是异步系统的一种特例。

异步共享存储模型主要是同步计算考虑的模型，我们主要需要考虑的是异步msg传递模型，因为这是现实中最最常见的一种情况。

至于同步msg传递模型，显示中是不可能存在的，因为时钟是漂移的，没有全局时间，同步是不可能在现实中完美存在的。但是这种理想模型是有价值的，由于存在延迟上届，因此超过这个时间我们可以认为一定会接受到消息，因此我们就可以在超过这个时间再做下一件事情，也就是把系统变成按轮来同步执行了。而这个特性就会非常方便我们先在这个简单的环境条件下设计算法，然后再将其推广到实际情况中。以及这种标准的简单环境条件，方便我们去定量评价一个系统的好坏。

错误的种类：

• 初始死进程：指在局部算法中没有执行过一步
• 崩溃错误(损毁模型)：指处理机没有任何警告而在某点上停止操作
• 拜占庭错误：一个出错可引起任意的动作,即执行了与局部算法不一致的任意步。拜占庭错误的进程发送的消息可能包含任意内容

拜占庭错误是恶性故障，因为他会影响到系统的其他。前两种属于良性故障。

消息传递系统中的基本算法

形式化模型

首先我们给出msg传递系统这样一个形式化模型定义：

我们给出 $G(V,E)$ 这样一个无向图的概念，处理机节点集合 $V= \lbrace p_0,p_1,\dots,p_{n-1} \rbrace$，$\exists p_ip_j$表示在处理机$P_i$和$p_j$之间存在一条双向信道$E_k$（这里我们统一假设信道都是双向了，下面遵循这个约定）

分布式算法是由所有处理机节点上的分布式程序统一构成的，是一个总和的概念。

由于是同步msg传递模型，所以处理机会在理论上的msg延迟上界时候后才会去取消息，因此每个处理机都需要有buf缓冲区来预存提前到的消息，因此我们在每条双向信道 $E_k$ 的处理机 $p_i$ 处都设计一个 $outbuf_i$ 和 $inbuf_i$，分别用来缓存接受到的消息和发送的消息。

因此对于每个处理机 $p_i$ 来说，都会有两个msg集合，$outbuf_i$[] 和 $inbuf_i$[]

• $outbuf_i[l]$： $p_i$ 经第$l$条关联的信道发送给邻居，但尚未传到邻居的msg。
• $inbuf_i[l]$： 在 $p_i$ 的第$l$条关联的信道上已传递到 $p_i$，但尚未经过 $p_i$ 内部计算步骤处理的msg。

我们假设有一个上帝，在第0秒给 $outbuf_i$[] 和 $inbuf_i$[] 照了个相，内容就是两个msg集合里的内容，我们记为状态 $q_{i0}$,同理，第1秒状态为 $q_{i1}$，第j秒状态就为 $q_{ij}$,这一连串的状态所构成的状态集我们就叫做 $Q_i$，因此每个处理器 $p_i$ 可以模型化为一个具有状态集 $Q_i$ 的状态机。

进一步，在第0秒时，状态机 $q_i$ 的状态为 $q_{i0}$, 状态机 $q_j$ 的状态为 $q_{j0}$,这时候我们已经不满足于只对单个状态机进行照相了，我们在第 $t$ 秒时，对所有状态机的状态 $q_{0t}，q_{1t},\dots,q_{it}$,统一照了张相，我们把它叫做配置。

初始配置就是所有初始状态组成的配置。

而状态的变化我们就可以叫做状态转移，我们将其抽象为一个转移系统，下面我们介绍这个转移系统的形式化定义：状态按离散步骤（事件/转移）变化的系统。

定义1. 转移系统是一个三元组 $S=\lbrace C,\to,I \rbrace$

其中$C$是配置集（所有配置的集合），$I$是初始配置的一个子集（表示转移系统的开始位置，如果不是子集就不合法了），$\to$是$C$上的一个二元转移关系，$\gamma \to \delta$ 代表从配置 $\gamma$ 转移到配置 $\delta$。

定义2. 我们记转移系统 $S$ 的一次执行的最大序列 $E=(r_0,r_1,\dots)$,其中 $r_0 \in I$ 且对 $\forall i \ge 0$,都有 $r_i \to r_{i+1}$。我们定义终止配置 $\gamma$ 为不存在 $\delta$，使得 $\gamma \to \delta$。那么对于序列 $E$,如果他是无限的，或者以终止配置 $\gamma$ 结束的，我们就称这样的序列为最大的。

这里的 $r_0 \in I$ 很好理解，因为都是从初始配置开始出发的。

定义3. 如果存在序列 $\gamma \to \gamma _1 \to \gamma _2 \dots \to \gamma _k = \delta$，那么我们称 $\delta$ 是由 $\gamma$ 可达的。 如果$\delta$ 是由初始配置可达的，则称 $\delta$ 是可达的。

系统里所发生的事情均被模型化为事件，对于msg传递系统，有两种：

• comp(i)——————计算事件，代表处理器 $p_i$ 的一个计算步骤。其中，$p_i$ 的转换函数被用于当前可访问状态
• del(i,j,m)—————传递事件，表示msg $m$ 从 $p_i$ 传送到 $p_j$

系统在时间上的行为被模型化为一个执行。它是一个由配置和事件交错的序列。该序列须满足各种条件，主要分为两类：

• safety条件（安全性）：表示某个性质在每次执行中每个可到达的配置里都必须成立

• liveness条件(活跃性)：表示某个性质在每次执行中的某些可达配置里必须成立。

对特定系统，满足所有要求的安全性条件的序列称为一个执行；若一个执行也满足所有要求的活跃性条件，则成为容许执行（合法的执行）。

下面我们介绍三个衡量模型性能的方式：

1. Msg复杂度：算法在所有容许的执行上发送msg总数的最大值(同步和异步系统)

2. 时间复杂度：

   • 同步系统：最大轮数，即算法的任何容许执行直到终止的最大轮数。

   • 异步系统：假设：1.节点计算任意有限数目事件的时间为0；2.一条消息发送和接收之间的时间至多为1个时间单位。在这两条假设的前提之下，时间复杂度就是所有计时容许执行中直到终止的最大时间。（也就是说有限计算不花时间，然后如果接受和发送时间太长，我们就不让他参与这次执行中）

3. 消息复杂度：消息总数/消息中总的位数长度。请注意和Msg复杂度的不同。

生成树上的广播和敛播

在一个分布式系统中，广播和敛播是最重要的两个算法，因为msg的传递都需要靠这两个算法。

广播（Broadcast）：在分布式系统中，一个节点向所有其他节点发送同一条消息的过程。目标是让系统中所有节点（或指定组）接收消息

敛播（Gather，也称为收集、汇聚）：与广播相反，是所有节点向一个中心节点（或根）发送消息的过程，最终中心节点收集所有节点的信息。比如，子节点向根汇报状态，根汇总数据。

由于广播的特性，如果是普通图的结构，就会发生广播风暴问题，以及广播/敛播在树结构下才能达到消息复杂度最优，因此我们需要将分布式系统设计成**最小生成树(MST)**的结构。

广播算法：

• 根节点发送Msg给孩子。收到Msg的节点转发Msg给孩子。
• Msg复杂度：$O(n-1)$，因为生成树每条边有一个Msg
• 时间复杂度：$O(D)$，$D$为生成树直径

敛播算法：

• 汇集是从所有节点收集信息至根
• Msg复杂度：$O(n-1)$，因为生成树每条边有一个Msg
• 时间复杂度：$O(D)$，$D$为生成树直径

构造生成树

上节讨论的广播和敛播都是建立在已知生成树的拓扑结构，因此我们还需要思考如何来构造生成树

指定根构造生成树

flooding（洪泛）算法

• 算法思想：设 $p_r$ 是特殊处理器。从 $p_r$ 开始，发送M到其所有邻居。当处理器 $p_i$ 第$1$次收到消息M（不妨设此msg来自于邻居$p_j$）时，$p_i$ 发送M到除 $p_j$ 外的所有邻居。
• Msg复杂度：$O(2m-(n-1))$,$m$是信道总数。我们考虑一些延迟误差，比如有3个处理器 $p_0、p_1、p_2$,$p_0$分别向$p_1$和$p_2$转发ms,然后$p_1$和$p_2$同时收到ms，那么此时$p_1$和$p_2$又会同时相互转发，所以一条信道 $E_k$ 就可能有两条ms，但是注意对于每个$p_i$，它是肯定不会对它收到的第1条M来自的邻居$p_j$发送M,因此需要减掉 $n-1$。
• 时间复杂度：$O(D)$，$D$为生成树直径。

我们可以通过改造flooding算法来设计一种构造生成树的算法：

• 算法思想：
  • 首先，$p_r$发送M给所有邻居，$p_r$为根
  • 当$p_i$从某邻居$p_j$收到的M是第1个来自邻居的msg时，$p_j$是$p_i$的双亲；若$p_i$首次收到的M同时来自多个邻居，则用一个comp事件处理自上一comp事件以来的所有已收到的msgs，故此时，$p_i$可在这些邻居中任选一个邻居$p_j$做双亲。
  • 双亲一旦选定就绝不更改。当$p_i$确定双亲是$p_j$时，发送给$p_j$，并向此后收到发来M的处理器发送msg。
  • $p_i$向那些尚未发M给$p_i$(或已发M但尚未到达$p_i$)的邻居转发M之后，等待这些邻居发回响应msg：或。那些回应的邻居是$p_i$的孩子。
  • 当$p_i$发出M的所有接收者均已回应（或)，则$p_i$终止。将parent和children边保留即为生成树。
• Msg复杂度：由于算法只是在flooding算法上增加了回应（或)，因此也就是2倍关系，所以也是$O(m)$
• 时间复杂度：$O(D)$，$D$为生成树直径。

上述讨论的算法在同步模型下，也可以工作，同时所构造的生成树一定是一棵BFS树

但是在异步模型下，构造的树就不一定是一棵BFS树了

那么自然而然我们会好奇：如何构造DFS生成树呢？

• 算法思想： *
• Msg复杂度：$O(m)$
• 时间复杂度：$O(m)$

不指定根时构造生成树

• 已知条件：个具有m条边和n个节点的网络，自发启动的节点共有p个，其中ID 值最大者的启动时间为t
• Msg 复杂度：$O(pn^2)$。最坏情况下，每个处理器均试图以自己为根构造一棵DFS树。 因此，Alg2.4 的msg复杂性至多是Alg2.3的n倍：O(m*n) 时间复杂度：
• 时间复杂度：$O(t+m)$

环上选举算法

Leader选举问题

异步环：下界$O(nlgn)$

同步环：上界$O(n)$和下界$O(nlgn)$

• 非均匀：
  • Msg 复杂度：$n·(i+1)$，i为最终Leader的id
  • 时间复杂度：$n·(i+1) $
• 均匀：
  • Msg 复杂度：$O(4n)$，
  • 时间复杂度：$O(n· 2^i)$ i为最终Leader的id

近似算法

对于一些NP hard问题，我们只能使用$2^n$数量级的时间来求取最优解，但是近似算法给了我们一条新的思路，我们可以牺牲结果的部分准确性，比如只用$n^k$次方的时间，来求得问题的次优解。这个对于很多情况来说都是非常重要的。

以及对于次优解和最优解之间的误差，我们该如何去控制，如果我们能有效控制误差，那么对于很多优化问题都非常有效。

由于课程安排，近似算法这学期并没有讲，因此只做简单了解。