中国科学技术大学分布式算法课件研究生课程.ppt

《中国科学技术大学分布式算法课件研究生课程.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章分布式系统中的计算模型2006.12.151概述分布式系统计算模型的复杂性系统由并发执行部件构成系统中无全局时钟必须捕捉系统部件可能的失效对策因果关系（Causality）一致状态（Consistentstates）全局状态2§4.1基本知识协议（Protocol）协议中的控制语句1.Send（destination,action;parameters）destination：处理器抽象。实用中是通信实体的地址：机器名，机器的端口号(即1个socket地址)action：控制msg，希望接收者采取的动作parameters：参数集合假定：

2、msg发送是无阻塞、可靠的（语义类似于TCP套接字）；有时假定较弱的msg传递层（等价于UDP）。TCP与UDP的区别：①基于连接与无连接②对系统资源的要求（TCP较多，UDP少）③UDP程序结构较简单④流模式与数据报模式●TCP保证数据正确性，UDP可能丢包●TCP保证数据顺序，UDP不保证3§4.1基本知识2.接收msg接收msg可推广至接收事件，引起事件的原因是：外部msg、超时设定、内部中断事件在处理前，一般是在缓冲区(如事件队列)中，若一处理器想处理事件，它必须执行一个声明处理这些事件的线程。例如，一个节点通过执行下述代码等待事件A1,

3、A2,...,AnwaitingforA1,A2,...,An：//声明A1（Source;parameters）CodetohandleA1….An（Source;parameters）CodetohandleAn当p执行send(q,A1;parameters)且q执行上述代码时，q将最终处理由p发送的msg4§4.1基本知识3.超时当怀疑远程处理器失效时，可通过超时检测来判定：①当T秒后仍未收到P的类型为event的msg时，执行指定的动作waitinguntilPsends(event;parameters),timeout=Tontim

4、eouttimeoutaction②仅当收到一个响应msg时才采取动作，超时不做任何动作waitinguntilPsends(event;parameters),timeout=Tontimeout；ifnotimeoutoccurred{Successfulresponseactions}5§4.1基本知识3.超时③处理器等待响应T秒若处理器在等待开始后T秒内没响应，则等待结束，协议继续waitinguptoTsecondsfor(event;parameters)msgsEvent:6§4.2因果关系分布式系

5、统为何缺乏全局的系统状态？1.非即时通信A和B同时向对方喊话他们都认为是自己先喊话C听到两人是同时喊话结论：系统的全局状态依赖于观察点原因：传播延迟网络资源的竞争丢失msg重发ACBd1=d27§4.2因果关系2.相对性影响假设张三和李四决定使用同步时钟来观察全局状态：他们约定下午5点在某餐馆会面，张三准时到达，但李四在一个接近光速的日光系统中游览。张三在等待李四1小时后离开餐馆，而李四在自己的表到达5点时准时达到餐馆，但他认为张三未达到。因为大多数计算机的实际时钟均存在漂移，故相对速度不同，时钟同步仍然是一个问题。结论：使用时间来同步不是一个可

6、靠机制。8§4.2因果关系3.中断假设张三和李四在同一起跑线上赛跑，信号为小旗，前两个问题可以忽略，但是…即使可忽略其他影响，也不可能指望不同的机器会同时做出某些反应。因为现代计算机是一个很复杂的系统：CPU竞争、中断、页错误等，执行时间无法预料。结论：不可能在同一时刻观察一个分布式系统的全局状态必须找到某种可以依赖的性质：时间回溯因果相关9§4.2因果关系假设分布式系统构成：P＝{P1,P2,..,Pn}：处理器集合E：全体事件的集合Ep⊆E,Ep表示发生在p上的所有事件次序e1

7、件e1发生e2在之前，I为信息源定序有些E中事件很容易定序：发生在同一节点p上的事件满足全序：若e1,e2∈Ep，则e1

8、两事件不能由