分布式系统是一组相互独立的实体的集合它们可以一起工作，解决任何单一实体无法解决的问题。 通过通信网络进行通信的自主处理器 一些特点
没有共同的物理时钟 没有共享内存 地理上的分离 自主性和异质性
图1.3:并行系统的两种标准架构。(a)统一存储器存取多处理器系统。 (b) 非统一存储器存取(NUMA)多处理器。在这两种体系结构中，处理器可以从内存中本地缓存数据。
同步的 (发送/接收) 发送方和接收方之间的握手当接收完成时，发送就完成了当数据被复制到缓冲区时，接收就完成了 异步 (发送) 当数据从用户指定的缓冲区中复制出来时，控制权返回给进程
阻断(发送/接收) 基元的处理(无论是同步还是异步) 完成后，控制权返回到调用进程 非阻塞(发送/接收) 调用后控制权立即返回到进程 发送:即使是在数据从用户缓冲区复制出来之前接收:甚至在数据可能已经从发送方到达之前就接收了
异步执行 没有处理器的同步性，对时钟的漂移率没有约束信息延迟是有限的，但不受限制对一个过程中的一个步骤的时间没有限制 同步执行 处理器是同步的;时钟漂移率受到约束信息传递发生在一个逻辑步骤/回合中在一个过程中执行一个步骤的已知的时间上限
一个分布式的程序
个分布式程序由一组n个异步进程组成，p1,p2,..., pi,..., pn。
这些进程不共享全局内存，仅通过传递信息进行通信
这些进程并不共享一个全局时钟，这些进程可以即时访问。
进程执行和消息传输是异步的。 在不丧失一般性的情况下，我们假设每个进程都在不同的处理器上运行的。
通信网络的模型 通信网络提供的服务有几种模式，即FIFO、非FIFO和因果排序
在先进先出模型中，每个通道作为一个先入先出的消息队列，因此消息排序由一个通道保存。
在非FIFO模型中，信道就像一个集合，其中发送方进程添加消息，接收方进程以随机的顺序从其中删除消息。
因果有序的消息传递意味着FIFO消息传递
过程通信的模式 进程通信有两种基本模式--同步和异步 同步通信模型是一种阻塞式的，在消息发送时，发送方进程阻塞，直到接收方进程收到消息。 发送方进程只有在得知接收方进程接受了该消息后才会恢复执行因此，发送方和接收方进程必须同步来交换信息。 另一方面，异步通信模型是一种非阻塞类型，发送方和接收方不同步地交换信息。 在发送消息后，发送方进程并不等待消息被传递给接收方进程。该消息由系统进行缓冲，并在接收方进程准备好接受该消息时交付给它
两种沟通模式都不比对方优越 异步通信提供了更高的并行性，因为发送方进程可以在消息传输到接收方的过程中执行。 然而，如果一个进程在突发中向另一个进程发送大量的信息，就可能发生缓冲区溢出。 因此，异步通信的实现需要更复杂的缓冲区管理。 此外，由于并行性和非确定性程度较高，设计、验证和实现异步通信的分布式算法要困难得多。 司步通信在处理和实现上更简单 然而，由于频繁的阻塞，它的性能可能很差，而且很可能更容易出现死锁。
R1: 该规则管理进程执行事件时如何更新本地逻辑时钟
R2: 该规则规定了进程如何更新其全局逻辑时钟，以更新其对全局时间和全局进度的看法。
2 全序
标量时钟可以用来在一个分布式系统中对事件进行完全排序
对事件完全排序的主要问题是，不同进程的两个或多个事件可能具有相同的时间戳。 例如在图3.1中，进程P1的第三个事件和进程P2的第二个事件有相同的标量时间戳
消息顺序：非FIFO.FIFO,因果顺序，同步顺序
异步执行
其因果关系是偏序的 无因果关系循环 在任何逻辑链路上，不一定是FIFO交付，例如，网络层IPV4无连接服务
所有物理链路都服从FIFO
同步执行
逻辑链路固有非FIFO 可以在传输层承担面向连接的服务， 要在非FIFO链接上实现FIFO:对每条消息使用<seq_num,conn_id>
接收器使用缓冲区对消息进行排序
因果顺序：CO
CO交替定义
如果发送事件s和s’通过因果顺序(而不是物理时间顺序)相关，则它们对应的接收事件r和r‘在所有公共目的地以相同的顺序出现。 如果s和s不存在因果关系，则CO虚满足。
CO交替定义
当同一进程发送m1、m2时，CO退化为FIFO
应用程序处理到达消息的事件称为delivery事件(而不是receive事件)。
如果 s 和 r 的过去是相同的， 我们得到了 CO 执行的一个子类， 叫做同步执行。
死锁的模型
单一资源模型：一个进程最多对资源的一个单位有一个未完成的请求
AND模型1：一个进程可以请求多个资源，并且只有请求的所有资源都被授予该进程后，才能满足请求（图中出现周期就死锁）
AND模型2：一个进程不是EFG中不是循环的一部分，也可以死锁，因为依赖其他死锁自己也死锁
OR模型：一个进程请求多个资源，任意一个资源被授予，该请求就满足（出现结死锁）
NAD-OR模型：请求可以在资源请求中指定and和or的任意组合(死锁是稳定的，可以通过重复OR模型思索检测此类死锁)
不受限制的模型
分布式死锁检测算法
Path-Pushing算法 在路径推送算法中，通过维护显式的全局WFG来检测分布式死锁
基本思想是为分布式系统的每个站点构建一个全局WFG。
在这类算法中，每当在每个站点执行死锁计算时，它都会将其本地WFG发送到所有邻近站点
在更新了每个站点的本地数据结构之后，这个更新的WFG随后被传递给其他站点，并重复这个过程，直到某个站点对全局状态有了足够完整的了解，可以宣布死锁或确定不存在死锁。
这种在全局WFG的路径周围发送的特性导致了术语路径推送算法
EdgeChasing算法 在边缘追踪算法中，通过沿着图的边缘传播称为探针的特殊消息来验证分布式图结构中是否存在循环。 这些探测消息不同于请求和应答消息 如果一个站点接收到之前由它发送的匹配探针，则可以删除周期的形成。 每当一个正在执行的进程接收到探测消息时，它就会丢弃这条消息并继续执行。 只有被阻塞的进程沿着它们的输出边缘传播探测消息 边缘追踪算法的主要优点是探针是固定大小的消息，通常非常短
基于扩散计算的算法 在基于扩散计算的分布式死锁检测算法中，死锁检测计算通过系统的WFG进行扩散。 这些算法利用回波算法来检测死锁o 这种计算叠加在底层的分布式计算上·如果此计算终止则启动器声明死锁。 为了检测死锁，进程沿着WFG中的所有传出边发送查询消息 这些查询通过WFG的边缘依次传播(即扩散)。 当被阻塞的进程接收到针对特定死锁检测发起的第一个查询消息时它不会发送回复消息，直到它收到针对它发送的每个查询的回复消息c对于这个死锁检测发起的所有后续查询，它会立即发送回复消息死锁检测的发起者在收到它发出的每个查询的回复时检测到死锁
基于全局状态检测的算法
可以在不冻结底层计算和的情况下获得分布式系统的一致快照
如果在启动快照收集之前，系统中存在一个稳定的属性，则该属性在快照中仍然保持。
因此，分布式死锁可以通过获取系统的快照并检查其死锁的条件来检测。
分布式共享内存
在共享空间中读写通信
没有接受和发送源于
发送接收由DSM管理
并发使用，没有内存访问瓶颈
大的虚拟内存空间
异步消息传递，较低效
内存一致性：read返回最近一次write的值，最近对于副本和并发是有歧义的
