中科大算法设计与分析分布式算法部分作业部分答案.ppt

算法设计与分析。解:与广播算法分析时间复杂性的步骤一致,一两句的说明不是分析。<1>同步模型引理:在汇集算法的每个容许执行里,树中每个高为t子树根结点在第t轮里收到所有孩子的msg。归纳证明。。。定理:当生成树高为d时,存在一个时间复杂度为O(d)的同步汇集算法。<2>异步模型引理:在汇集算法的每个容许的执行里,树中每个高为t的子树根结点在时刻t收到所有孩子的msg。归纳证明。。。定理:当生成树高为d时,存在一个时间复杂度为O(d)的异步汇集算法。,一个处理器在图G中是从Pr可达的,当且仅当它的parent变量曾被赋过值。解::在异步模型的每个容许执行中,。两个方向证明题目:(异步模型的每个容许执行中),不是空口讨论。方法不一,原则是有理有据,逻辑清楚。<1>=>pr可达,(因为图G是由parent与children确定的静止图)收到m才会加入图中,所以可达结点收到过m,。由于是容许执行,第7行,即parent:=j也会执行。也就是被赋值。<2><=当第7行执行过,由于是容许执行,第5行也执行过,即收到过m,而m是由pr发出的,所以可达。。解:。先证连通,再证无环(反证),再证DFS树。。可以证明:在有子结点与兄弟结点未访问时,子结点总是先加入树中。。(m)。解:<1>同步模型:每一轮中,根据算法,有且只有一个消息(MorParentorReject)在传输,从算法的第6、14、16、20、25行发送消息的语句中可以发现:消息只发往一个处理器结点,除根结点外,所有的处理器都是收到消息后才被激活,所以,不存在多个处理器在同一轮发送消息的情况,所以时间复杂度与消息复杂度一致。<2>异步模型:在一个时刻内至多有一个消息在传输,因此,时间复杂度也与消息复杂度一致。消息复杂度:对任一边,可能传输的消息最多有4个,即2个M,2个相应M的消息(ParentorReject),所以消息复杂度为O(m)。综上,该算法的时间复杂度为O(m)。,使其时间复杂度为O(n)。解:两种考虑方式:<1>在每个处理器中维护一本地变量,同时添加一消息类型,在处理器Pi转发M时,发送消息N通知其余的未访问过的邻居,这样其邻居在转发M时便不会向Pi转发。<2>在消息M和<parent>中维护一发送数组,记录已经转发过M的处理器名称。两种方式都是避免向已转发过M的处理器发送消息M,这样DFS树外的边不再耗时,时间复杂度也降为O(n)。证明同步环上不存在匿名的、一致性的Leader选举算法。解:。假设R是大小为n>1的环(非均匀),A是其上的一个匿名算法,它选中某处理器为leader。因为环是同步的且只有一种初始配置,故在R上A只有唯一的合法执行。:在环R上算法A的容许执行里,对于每轮k,所有处理器的状态在第k轮结束时是相同的。Note:每个处理器同时宣布自己是Leader!算法。解:每个处理器的初始状态相同,状态机相同,接收的消息序列也相同(只有接收消息的时间可能不同),故最终处理器的状态一致。由于处理一条消息的至多需要1时间单位,若某时刻某个处理器宣布自己是Leader(接收到m条消息),则在有限时间内(m时间单位)其他处理器也会宣布自己是Leader。所以。。。Note:每个处理器陆续宣布自己是Leader!(j为2的幂)的连续片段,则所有这些片段是次序等价的。解:。。。。附1:“表面上,1-time复杂性至少等于时间复杂性,因为T2假定下的最坏时间不会高于O2假定下的时间。但事实并非如此,而往往O1和O2假定之下的1-time复杂性是前一种时间复杂性的一个下界。”为什么one-time复杂性是时间复杂性的下界呢?解:考虑运行在环上的分布式算法的1-time时间复杂性和时间复杂性。<1>1-time时间复杂性:满足条件O2:发送和接收一个msg之间的时间恰好是一个时间单位,每个阶段节点转发消息都是同步进行,从而1-time时间复杂度仅与环直径相关,为O(D)。<2>时间复杂度:满足条件T2:一个msg的发送和接收之间的时间至多为一个时间单位,即为O(1)。节点转发消息并非同步进行,消息转发轨迹可能呈链状结构,时间复杂性与环节点个数相关,为O(n)。