分布式计算复习题.docx
免费下载
一、 解释分布式透明性含义，给出分布式透明性的分类，并请说明
为什么最大程度地实现透明性不总是好的？
二、 在基于环的选举算法中，如果两个进程同时发现协作者进程崩
溃时，将会发生什么？设计一个算法，使其在不影响基本的选
举算法情况下删除多余的消息。
三、 试描述
Giord
表决方案的读、写团体限制条件。若一个文件
被复制在
10
个服务器上，请列出该方案允许的所有读团体和写
团体。
四、 三倍模块冗余是否能处理拜占庭故障？举例说明。
五、 证明：在引理
2.6
（对异步模型中的每一次合法执行，修改后
的洪泛算法构造一个根在
Pr
的网络生成树）中使用的断言，即
某处理器在
G
中可从
Pr
到达的条件是当且仅当它设置过自己的
parent
变量。
六、 对每个
n>=8(n
是
2
的幂
)
，试构造一个规模为
n
的环
Sn
，对
每个同步的、基于比较的领导者选举算法
A
，在
Sn
上
A
的合法
执行中发送的消息数为
Ω(nlogn),
并简要证明
exec(Sn)
中的活
跃轮数至少是
n/8
。
七、 试描述
n
个处理器的有界互斥算法，即锦标赛树算法，并证明
该算法实现了互斥。
八、 分布式算法与集中式算法有哪些不同点？
九、 简述分布式计算技术的发展历程。
十、 从实现结构的角度，试阐释虚拟化模型的分类，并给出相应的
代表产品。
十一、一个文件被复制在
10
个服务器上，请给出表决算法的条件，
并列出允许的所有读团体和写团体。。
十二、给定一个特定节点
Pi
，试构造网络深度优先搜索生成树的异步
算法。
十三、证明异步环系统中不存在匿名的领导者选举算法。
十四、证明面包店算法实现了无锁定。
十五、试给出基于仲裁团的
Maekawa
互斥算法。该算法是否会产生
死锁？若然，举例说明。
十六、请给出下图中各事件的逻辑时戳
LT
和向量时戳
VC
，并证明向
量时戳可以捕获并发性。
of 3
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
相关文档
评论