分布式算法_ch36(New)1

分布式算法_ch36(New)1 分布式系统计算模型的复杂性是指系统由并发执行部件构成，系统中无全局时钟，必须捕捉系统部件可能的失效，对策因果关系（Causality）一致。分布式算法是指在分布式系统中为了实现某种功能或解决某种问题所采用的算法。 分布式系统计算模型的复杂性主要体现在以下几个方面： 1. 系统由并发执行部件构成：分布式系统由多个处理器或节点组成，每个节点都可以并发执行任务，从而提高系统的整体性能。 2. 系统中无全局时钟：由于分布式系统的节点之间可能存在网络延迟、时钟漂移等问题，使得系统中无法确定一个全局的时钟。 3. 必须捕捉系统部件可能的失效：分布式系统的节点可能会出现故障或失效，因此需要设计机制来捕捉和处理这些失效。 对策因果关系（Causality）一致是指分布式系统中的节点之间需要保持因果关系的一致性，以确保系统的正确性和可靠性。 协议（Protocol）是分布式系统中节点之间用于通信的规则和标准。协议中的控制语句包括Send和Receive，Send语句用于发送消息，Receive语句用于接收消息。 Send语句的格式为：Send（destination, action; parameters），其中destination是处理器的抽象，action是控制消息，parameters是参数集合。例如，Send（P, A1; parameters）表示发送一个消息给处理器P，希望P执行动作A1。 Receive语句的格式为：Receive（source, action; parameters），其中source是消息的来源，action是控制消息，parameters是参数集合。例如，Receive（P, A1; parameters）表示接收一个来自处理器P的消息，希望执行动作A1。 超时机制是分布式系统中用于检测远程处理器失效的机制。当怀疑远程处理器失效时，可以通过超时检测来判定。例如，waiting until P sends (event; parameters), timeout=T表示等待处理器P发送一个事件event，超时时间为T秒。 因果关系（Causality）是分布式系统中节点之间的因果关系。分布式系统缺乏全局的系统状态是因为非即时通信、相对性影响和中断等原因。为了解决这些问题，需要找到某种可以依赖的性质，例如时间回溯和因果相关。 Happens-before关系（<H）是节点次序和消息传递次序的传递闭包。该关系有三个规则：规则1：若e1<pe2，则e1<He2；规则2：若e1<me2，则e1<He2；规则3：若e1<He2，且e2<H则e1<H。 分布式算法_ch36(New)1介绍了分布式系统计算模型的复杂性，协议、超时机制和因果关系等概念，并讨论了分布式系统缺乏全局系统状态的原因和解决方法。