分布式算法习题解答.ppt

《分布式算法习题解答.ppt》由会员分享，可在线阅读，更多相关《分布式算法习题解答.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、分布式算法习题解答 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望1.1.分析在同步和异步模型下汇集算法的复杂性。分析在同步和异步模型下汇集算法的复杂性。分析在同步和异步模型下汇集算法的复杂性。分析在同步和异步模型下汇集算法的复杂性。解：与广播算法分析时间复杂性的步骤一致，一两句的说明解：与广播算法分析时间复杂性的步骤一致，一两句的说明解：与广播算法分析时间复杂性的步骤一致，一两句的说明解：与广播算法分析时间复杂性的步骤一致，一两句的说明不是分析。不是分析。不是分

2、析。不是分析。同步模型同步模型同步模型同步模型 引理：在汇集算法的每个容许执行里，树中每个高为引理：在汇集算法的每个容许执行里，树中每个高为引理：在汇集算法的每个容许执行里，树中每个高为引理：在汇集算法的每个容许执行里，树中每个高为 t t 子树根结点在第子树根结点在第子树根结点在第子树根结点在第 t t 轮里收到所有孩子的轮里收到所有孩子的轮里收到所有孩子的轮里收到所有孩子的msgmsg。归纳证明。归纳证明。归纳证明。归纳证明。定理：当生成树高为定理：当生成树高为定理：当生成树高为定理：当生成树高为 d d 时，存在一个时间复杂度为时，存在一个时间复杂度为时，存在一个时间复杂度为时，存在一个

3、时间复杂度为O(d)O(d)的的的的 同步汇集算法。同步汇集算法。同步汇集算法。同步汇集算法。异步模型异步模型异步模型异步模型 引理：在汇集算法的每个容许的执行里，树中每个高为引理：在汇集算法的每个容许的执行里，树中每个高为引理：在汇集算法的每个容许的执行里，树中每个高为引理：在汇集算法的每个容许的执行里，树中每个高为 t t 的子树根结点在时刻的子树根结点在时刻的子树根结点在时刻的子树根结点在时刻 t t 收到所有孩子的收到所有孩子的收到所有孩子的收到所有孩子的msgmsg。归纳证明。归纳证明。归纳证明。归纳证明。定理：当生成树高为定理：当生成树高为定理：当生成树高为定理：当生成树高为 d

4、d 时，存在一个时间复杂度为时，存在一个时间复杂度为时，存在一个时间复杂度为时，存在一个时间复杂度为O(d)O(d)的的的的 异步汇集算法。异步汇集算法。异步汇集算法。异步汇集算法。2.2.证明在引理证明在引理证明在引理证明在引理2.62.6中，一个处理器在图中，一个处理器在图中，一个处理器在图中，一个处理器在图GG中是从中是从中是从中是从PrPr可可可可达的，当且仅当它的达的，当且仅当它的达的，当且仅当它的达的，当且仅当它的parentparent变量曾被赋过值。变量曾被赋过值。变量曾被赋过值。变量曾被赋过值。解：解：引理引理2.62.6：在异步模型的每个容许执行中，算法：在异步模型的每个容

5、许执行中，算法2.22.2构造一棵构造一棵以以prpr为根的生成树。为根的生成树。两个方向证明题目：依据是算法两个方向证明题目：依据是算法2.22.2和题目条件（异步模型的和题目条件（异步模型的每个容许执行中），不是空口讨论。方法不一，原则是有理每个容许执行中），不是空口讨论。方法不一，原则是有理有据，逻辑清楚。有据，逻辑清楚。=pr=pr可达，（因为图可达，（因为图GG是由是由parentparent与与childrenchildren确定的静确定的静止图）收到止图）收到mm才会加入图中，所以可达结点收到过才会加入图中，所以可达结点收到过mm，执行，执行了了alg2.2alg2.2第第5 5

6、行。由于是容许执行，第行。由于是容许执行，第7 7行，即行，即parentparent：=j=j也也会执行。也就是被赋值。会执行。也就是被赋值。=当第当第7 7行执行过，由于是容许执行，第行执行过，由于是容许执行，第5 5行也执行过，行也执行过，即收到过即收到过mm，而，而mm是由是由prpr发出的，所以可达。发出的，所以可达。3.3.证明证明证明证明Alg2.3Alg2.3构造一颗以构造一颗以构造一颗以构造一颗以PrPr为根的为根的为根的为根的DFSDFS树。树。树。树。解：类似引理解：类似引理2.62.6的证明过程。先证连通，再证无环（反的证明过程。先证连通，再证无环（反证），再证证），再

7、证DFSDFS树。依据是算法树。依据是算法2.32.3与与DFSDFS的定义。的定义。可以证明：在有子结点与兄弟结点未访问时，子结点总是先可以证明：在有子结点与兄弟结点未访问时，子结点总是先加入树中。根据加入树中。根据alg2.3 alg2.3 的的xxxxxx步证明这一点。步证明这一点。4.4.证明证明证明证明Alg2.3Alg2.3时间复杂度为时间复杂度为时间复杂度为时间复杂度为O(m)O(m)。解：解：同步模型：每一轮中，根据算法，有且只有一个消息同步模型：每一轮中，根据算法，有且只有一个消息(M M or or Parent Parent or or RejectReject)在传输，

8、从算法的第在传输，从算法的第6 6、1414、1616、2020、2525行发送消息的语句中可以发现：消息只发往一个处理器行发送消息的语句中可以发现：消息只发往一个处理器结点，除根结点外，所有的处理器都是收到消息后才被激结点，除根结点外，所有的处理器都是收到消息后才被激活，所以，不存在多个处理器在同一轮发送消息的情况，活，所以，不存在多个处理器在同一轮发送消息的情况，所以时间复杂度与消息复杂度一致。所以时间复杂度与消息复杂度一致。异步模型：在一个时刻内至多有一个消息在传输，因异步模型：在一个时刻内至多有一个消息在传输，因 此，时间复杂度也与消息复杂度一致。消息复杂度：对任此，时间复杂度也与消息

9、复杂度一致。消息复杂度：对任一边，可能传输的消息最多有一边，可能传输的消息最多有4 4个，即个，即2 2个个MM，2 2个相应个相应MM的消息（的消息（Parent Parent or or RejectReject），所以消息复杂度为），所以消息复杂度为O(m)O(m)。综上，该算法的时间复杂度为综上，该算法的时间复杂度为O(m)O(m)。5.5.修改修改修改修改Alg2.3Alg2.3，使其时间复杂度为，使其时间复杂度为，使其时间复杂度为，使其时间复杂度为O(n)O(n)。解：两种考虑方式：解：两种考虑方式：在每个处理器中维护一本地变量，同时添加一在每个处理器中维护一本地变量，同时添加一消

10、息类型，在处理器消息类型，在处理器PiPi转发转发MM时，发送消息时，发送消息N N通知通知其余的未访问过的邻居，这样其邻居在转发其余的未访问过的邻居，这样其邻居在转发MM时时便不会向便不会向PiPi转发。转发。在消息在消息MM和和中维护一发送数组，记录中维护一发送数组，记录已经转发过已经转发过MM的处理器名称。的处理器名称。两种方式都是避免向已转发过两种方式都是避免向已转发过MM的处理器发送消息的处理器发送消息MM，这样，这样DFSDFS树外的边不再耗时，时间复杂度也降树外的边不再耗时，时间复杂度也降为为O(n)O(n)。6.证明同步环上不存在匿名的、一致性的证明同步环上不存在匿名的、一致性

11、的证明同步环上不存在匿名的、一致性的证明同步环上不存在匿名的、一致性的LeaderLeader选举算法。选举算法。选举算法。选举算法。解：由解：由Lemma3.1Lemma3.1可得。可得。假设假设R R是大小为是大小为n1n1的环（非均匀），的环（非均匀），A A是其上的一是其上的一个匿名算法，它选中某处理器为个匿名算法，它选中某处理器为leaderleader。因为环是。因为环是同步的且只有一种初始配置，故在同步的且只有一种初始配置，故在R R上上A A只有唯一的只有唯一的合法执行。合法执行。Lemma3.1Lemma3.1：在环在环R R上算法上算法A A的容许执行里，对于每的容许执行里

12、，对于每轮轮k k，所有处理器的状态在第，所有处理器的状态在第k k轮结束时是相同的。轮结束时是相同的。NoteNote：每个处理器同时宣布自己是：每个处理器同时宣布自己是LeaderLeader！7.7.证明异步环系统中不存在匿名的证明异步环系统中不存在匿名的证明异步环系统中不存在匿名的证明异步环系统中不存在匿名的LeaderLeader选举选举选举选举算法。算法。算法。算法。解：解：每个处理器的初始状态相同，状态机相同，接收的消每个处理器的初始状态相同，状态机相同，接收的消息序列也相同（只有接收消息的时间可能不同），故息序列也相同（只有接收消息的时间可能不同），故最终处理器的状态一致。由于

13、处理一条消息的至多需最终处理器的状态一致。由于处理一条消息的至多需要要1 1时间单位，若某时刻某个处理器宣布自己是时间单位，若某时刻某个处理器宣布自己是Leader Leader（接收到（接收到mm条消息），则在有限时间内（条消息），则在有限时间内（mm时间单位）时间单位）其他处理器也会宣布自己是其他处理器也会宣布自己是LeaderLeader。所以。所以。NoteNote：每个处理器陆续宣布自己是：每个处理器陆续宣布自己是LeaderLeader！8.8.若将环若将环若将环若将环RrevRrev划分为长度为划分为长度为划分为长度为划分为长度为j j（j j为为为为2 2的幂）的连续的幂）的连

14、续的幂）的连续的幂）的连续片段，则所有这些片段是次序等价的。片段，则所有这些片段是次序等价的。片段，则所有这些片段是次序等价的。片段，则所有这些片段是次序等价的。解：。附附1 1：“表面上，表面上，1-time1-time复杂性至少等于时间复杂性，复杂性至少等于时间复杂性，因为因为T2T2假定下的最坏时间不会高于假定下的最坏时间不会高于O2O2假定下的时间。假定下的时间。但事实并非如此，而往往但事实并非如此，而往往O1O1和和O2O2假定之下的假定之下的1-time1-time复杂性是前一种时间复杂性的一个下界。复杂性是前一种时间复杂性的一个下界。”为为什么什么one-timeone-time

15、复杂性是时间复杂性的下界呢？复杂性是时间复杂性的下界呢？解：考虑运行在环上的分布式算法的解：考虑运行在环上的分布式算法的1-time1-time时间复杂性和时时间复杂性和时间复杂性。间复杂性。1-time 1-time时间复杂性：时间复杂性：满足条件满足条件O2O2：发送和接收一个：发送和接收一个msgmsg之间的时间恰好是一个时之间的时间恰好是一个时间单位，每个阶段节点转发消息都是同步进行，从而间单位，每个阶段节点转发消息都是同步进行，从而1-time1-time时间复杂度仅与环直径相关，为时间复杂度仅与环直径相关，为O(D)O(D)。时间复杂度：时间复杂度：满足条件满足条件T2T2：一个：

16、一个msgmsg的发送和接收之间的时间至多为一个的发送和接收之间的时间至多为一个时间单位，即为时间单位，即为O(1)O(1)。节点转发消息并非同步进行，消息转。节点转发消息并非同步进行，消息转发轨迹可能呈链状结构，时间复杂性与环节点个数相关，为发轨迹可能呈链状结构，时间复杂性与环节点个数相关，为O(n)O(n)。例如：echo协议，即应答协议，主要用于调试和检测中，是路由也是网络中最常用的数据包，可以通过发送echo包知道当前的连接节点有哪些些路径，并且通过往返时间能得出路径长度。echo算法的实现，如果转发消息同步进行，则对应1-time时间复杂性，为O(D)；如果不同步转发消息，网络路径可

17、能呈链状结构，即对应时间复杂度O(N)。NoteNote：考虑时间复杂度，任一节点可以在：考虑时间复杂度，任一节点可以在O(d)O(d)时间时间内将询问包发送到网络上的其它节点，但却可能需内将询问包发送到网络上的其它节点，但却可能需要要O(N)O(N)的时间接收其它节点发来的响应包。的时间接收其它节点发来的响应包。附附2 2：算法：算法3.23.2（同步（同步LeaderLeader选举算法）选举算法）为何非唤醒为何非唤醒msgmsg要延迟要延迟2i-12i-1轮？轮？如何修改算法如何修改算法3.23.2来改善时间复杂性？来改善时间复杂性？解：解：降低消息复杂度（降低消息复杂度（IdId最小的

18、节点被选举为最小的节点被选举为LeaderLeader，LeaderLeader节点消息的转发速度最快）。节点消息的转发速度最快）。方案方案1 1：添加：添加RelayRelay变量，保证消息在转发节点变量，保证消息在转发节点不延迟，时间复杂度由不延迟，时间复杂度由O(n*2i)O(n*2i)降为降为O(N*2i+n-N)O(N*2i+n-N)，N N为自发唤醒的节点数。为自发唤醒的节点数。方案方案2 2：原算法延迟函数为：原算法延迟函数为f(id)=2idf(id)=2id，时间复杂度，时间复杂度为为OO（n*2in*2i）。通过重新定义延迟函数来降低时）。通过重新定义延迟函数来降低时间复杂度，如间复杂度，如f(id)=c*idf(id)=c*id等。等。消息复杂度提高？消息复杂度提高？NoteNote：思考方案：思考方案2 2中消息复杂度和时间复杂度的关中消息复杂度和时间复杂度的关系！系！祝大家考试顺利谢谢！