算法设计与分析--考试真题

根据考试范围找相应题目做。

分布式算法试题汇总

选择题

1. 下述说法错误的是___
   A 异步系统中的消息延迟是不确定的
   B 分布式算法的消息复杂性是指在所有合法的执行上发送消息总数的最大值
   C 在一个异步算法中，如果不存在错误，则算法的执行只取决于初始配置
   D 分布式系统终止是指系统中所有结点处于终止状态，且没有消息在传输

2. 已知有三个阻碍分布式了解全局状态，与全局状态无关的是 （）
   A. 非及时的通信
   B. 相关性影响
   C. 中断
   D. 算法的正确性

在分布式系统中，有三个主要的阻碍了解全局状态的因素，分别是：

• 非及时的通信：由于网络延迟，消息的传递可能不是按照发送的顺序到达接收方，导致事件的顺序不一致，从而影响全局状态的判断。
• 相关性影响：由于分布式系统中的组件之间存在依赖关系，一个组件的状态可能会影响另一个组件的状态，从而影响全局状态的判断。
• 中断：由于分布式系统中的组件可能会发生故障或恢复，导致系统的可用性和一致性受到影响，从而影响全局状态的判断。

因此，与全局状态无关的是算法的正确性。算法的正确性是指算法能够按照预期的功能和性能执行，不受外部因素的干扰。算法的正确性是分布式系统设计和实现的基础，而不是了解全局状态的障碍。

3. 设正整数d1,d2,…,dn是n个结点的标识符集合，x = min(d1,d2,…,dn),y =max(d1,d2,…,dn)，则同步环上非均匀的leader选举算法的时间复杂性是
   A. O(n)
   B. O(xn)
   C. (yn)
   D. O(nlogn)

4. 在异步环上，一个O(n^2)的leader选举算法按顺时针单向发送消息，假设只有最大的标识符节点可以当选为leader,则当环上标识符次序为__时该算法发送的消息数量最多。
   A. 0,1, … , n-1 随机
   B. 逆时针 n-1,n-2,…,0
   C. 顺时序 0,1，…, n-1
   D. 顺时针 n-1,n-2,…,0

简答题

1. 已知事件 e1,e2,e3 和 e4 的向量时戳分别为（2,3,0,0），（1,2,0,0），（0,0,1,1），（3,6,4,2），请找出所有因果关系的事件对。

（1,2,0,0）<v （2,3,0,0），e2 在因果序上先于 e1
（2,3,0,0）<v （3,6,4,2），e1 在因果序上先于 e4
（1,2,0,0）<v （3,6,4,2），e2 在因果序上先于 e4
（0,0,1,1）<v （3,6,4,2），e3 在因果序上先于 e4

如果事件e1在事件e2之前发生，或者事件e1导致事件e2发生，那么事件e1因果先于事件e2，记为e1 -> e2。向量时戳的一个重要性质是，如果 $e1{<}_{v}e2$，那么e1的向量时戳的每个元素都小于或等于e2的向量时戳的对应元素。

2. 分布式算法中，bit复杂性和消息链复杂性分别属于通信复杂性和时间复杂性中的哪一种？

bit 复杂性属于通信复杂性，消息链复杂性属于时间复杂性；若在一个分布式算法中每个 msg信息的 bit 数目相同，则 msg 的个数就等于 bit 的总数除以一个 msg 的 bit 数目，则 bit 复杂性可以等价为 msg 复杂性；消息链复杂性是最长消息链的长度，在同步系统中它就是最大轮数，异步系统中假定任何执行的 msg 延迟至多是一个单位时间，它就是计算直到终止时间的最大运行时间，在同，异步系统中皆为时间复杂性。

• 通信复杂性可以进一步分为两种：bit复杂性和消息复杂性。bit复杂性是指算法在执行过程中所传输的比特数，它反映了算法的通信量。消息复杂性是指算法在执行过程中所传输的消息数，它反映了算法的通信次数。
• 时间复杂性也可以进一步分为两种：同步时间复杂性和异步时间复杂性。同步时间复杂性是指算法在同步模型下的执行时间，它反映了算法的同步性能。异步时间复杂性是指算法在异步模型下的执行时间，它反映了算法的异步性能。
  因此，bit复杂性属于通信复杂性中的一种，而消息链复杂性属于时间复杂性中的一种。消息链复杂性是指算法在异步模型下的最长消息链的长度，它反映了算法的最坏情况下的延迟。
  消息复杂性和消息链复杂性的区别：
  消息复杂性和消息链复杂性是两种不同的时间复杂性的指标，它们分别反映了算法在通信次数和延迟方面的性能。
• 消息复杂性是指算法在执行过程中所传输的消息数，它反映了算法的通信次数。消息复杂性越小，说明算法的通信开销越低。
• 消息链复杂性是指算法在异步模型下的最长消息链的长度，它反映了算法的延迟。消息链复杂性越小，说明算法的响应时间越快。

3. 构造一个 16 节点的环，使其高度对称，并给出所有序等价的连续片段。

0 0000 0000 0
1 0001 1000 8
2 0010 0100 4
3 0011 1100 12
4 0100 0010 2
5 0101 1010 10
6 0110 0110 6
7 0111 1110 14
8 1000 0001 1
9 1001 1001 9
10 1010 0101 5
11 1011 1101 13
12 1100 0011 3
13 1101 1011 11
14 1110 0111 7
15 1111 1111 15
长度为 1 的有序等价的连续片段:
(0)，(8), (4), (12), (2), (10), (6), (14), (1), (9), (5), (13), (3), (11), (7), (15)
长度为 2 的有序等价的连续片段:
(0, 8),(4, 12),(2, 10),(6, 14),(1, 9), (5, 13), (3, 11), (7, 15);
(8, 4), (12, 2), (10, 6), (14, 1), (9, 5), (13, 3), (11, 0)
长度为 4 的有序等价的连续片段：
0, 8, 4, 12 || 2, 10, 6, 14 || 1, 9, 5, 13 || 3, 11, 7, 15;
15 0, 8, 4 || 12, 2, 10, 6 || 14, 1, 9, 5 || 13, 3, 11, 7;
7, 15 0, 8, || 4, 12, 2, 10, || 6, 14 1, 9, || 5, 13 3, 11;
11, 7, 15 0, || 8, 4, 12, 2, || 10, 6, 14, 1, || 9, 5, 13 3;
长度为 8 的有序等价的连续片段:
0, 8, 4, 12 2, 10, 6, 14 || 1, 9, 5, 13 || 3, 11, 7, 15;
15 0, 8, 4 12, 2, 10, 6 || 14, 1, 9, 5 , 13, 3, 11, 7;
7, 15 0, 8, 4, 12, 2, 10, || 6, 14 1, 9, 5, 13 3, 11;
11, 7, 15 0, 8, 4, 12, 2, || 10, 6, 14, 1, 9, 5, 13, 3;
3, 11, 7, 15 0, 8, 4, 12, || 2 10, 6, 14, 1, 9, 5, 13 ;
13, 3 11, 7, 15 0, 8, 4, || 12, 2 10, 6, 14, 1, 9, 5;
5, 13, 3 11, 7, 15 0, 8, || 4 12, 2 10, 6, 14, 1, 9 ;
9, 5, 13, 3 11, 7, 15 0, || 8, 4 12, 2 10, 6, 14, 1;
长度为 16 的有序等价的连续片段(0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15）

4. 若将消息复杂度为 O(nlgn)的异步环选举算法（在阶段 1 向节点的 2 邻居发送 Prob 消息）修改为只向其中一个方向发送 Prob 消息，请问修改后算法的消息复杂度是多少？如何对其做进一步的修改使得消息复杂度仍然为 O(nlgn)。

算法题

设一个同步匿名的单向环有 n 个结点，每个结点均知道 n，每个节点的初始均状态相同，
每个结点上的程序相同且开始于同一时刻。
（1） 请问是否存在一个确定的算法选出一个 leader？简述理由。
（2） 试设计一个概率的 leader 选举算法。
（3） 请问你设计的概率算法属于哪一类算法？

（1） 对于同步环上的 leader 选举， 不存在非均匀的匿名算法。

• 初始状态相同：在一个匿名环中，处理器间始终保持对称，若无某种初始的非对称(如，
  标识符唯一)， 则不可能打破对称。 在匿名环算法里， 所有处理器开始于相同状态。
• 在同步系统中， 一个算法以轮的形式进行，根据引理 3.1 在环 R 上算法 A 的容许执行
  里， 对于每一轮 k，所有处理器的状态在第 k 轮结束时是相同的。
  由反证法，假设若在某轮结束时， 一个处理器宣布自己是 leader(进入选中状态)， 则其它处理器亦同样如此， 这和 A 是一个 leader 选举算法的假定矛盾！

（2）算法由若干个 phase 构成，每个 phase 包括 n 轮，可用 phase 和轮控制算法流程。每
个结点可以设置一个随机数发生器 uniform(1…m),这里 m 是局部变量，初值等于 n。
每个结点上的随机数发生器 uniform(1…m)产生随机数𝑥𝑖当作自己的 id
在第 i 阶段开始

1. 若一个结点的 id 是 i，则该结点绕环发送一个包含信息 i 的 msg；
2. 若一结点的 id 不是 i， 且它收到一个 msg， 则它转发此 msg 后变为 non-leader，变成
   non-leader 之后能转发 msg。
3. 若一个结点的 id 是 i， 同时收到一个 msg，则本地变量 count 记录收到了多少个 msg。
   id 为 i 的结点收到了 msg 数量,代表当前系统中产生了最小 id 的结点个数。此时 id 为 i 的结
   点把 Phase 变为 1，m 变成 count。重新执行以上过程，直到 id 为 i 的结点只收到一个 msg,
   此时该结点为 leader,同时绕环发送终止 msg,收到终止 msg 的 non-leader 终止运行。

（3）Las Vegas 算法。因为自己提出的算法一定能获得正确的解，但是随机算法可能会以极低的概率一直产生相同𝑥𝑖，导致不能产生最终解。

5.分布式系统中生成树构造问题：构造一棵具有 m 条边（信道总数），网络直径为 D 的生成
树，其构造方法是将 flooding 算法修改后得到的
（1）若设系统中处理器个数为 n，那么最坏情况下，异步算法完成生成树构造需要发送的
消息数是多少？
（2）基于异步算法找到该网络的一课生成树的时间复杂性、消息复杂性分别是多少？
（3）若在同步模型下进行生成树构造，其与异步算法的区别是什么？它构造的是 BFS 还是
DFS？请证明你的结果。

2013级试题

2019级试题

2021年秋

考卷