|
1.分布式系统简介 分布式系统的发展动因：硬件能力的提升和不断增长的需求推动了分布式系统的发展。 分布式系统的构成多样性：包括对等处理系统、基于资源共享的系统、紧耦合结构的并行处理系统等不同类型。 分布式系统的基本概念和定义：涵盖了分布式硬件、分布式控制、分布式数据，并强调对用户透明的资源分布。 分布式系统与计算机网络的区别：使用上、结构上、适应范围和标准化程度等方面。 2.分布式系统基本特性 分布式系统的基本特点：以任意方式支持连接、更紧密的应用衔接、用户的无缝感以及可缩放性。 分布式系统的透明性：包括访问透明性、位置透明性、复制透明性、并发透明性、故障透明性和持久性透明性。 分布式系统的开放性：要求系统根据一系列准则提供服务，并强调接口的规范性和系统的灵活性。 分布式系统的可缩放性：考虑规模、地域和管理方面的扩展。 3.分布式系统模型与问题 分布式系统中的基本模型：包括进程、通信系统和处理单元之间的关系。 分布式系统的基本问题和范型：包括工作目标、进程合作方案、控制方式、数据共享方案、故障解决方案等。 分布式系统的执行模型：包括乐观视角和悲观视角，分别强调系统的一致性和可用性。 4.分布式算法与同步/异步系统 分布式算法和集中式算法的区别：探讨了两种算法的不同点和使用场景。 异步和同步系统的固有矛盾：介绍了两种系统在分布式系统中的优缺点和适用场景。 CAP定理的指导下的系统选择：介绍了CAP定理的含义和指导下的系统设计原则。 分布式系统的发展动因：硬件能力的提升和不断增长的需求推动了分布式系统的发展。 分布式系统的构成多样性：包括对等处理系统、基于资源共享的系统、紧耦合结构的并行处理系统等不同类型。 分布式系统的基本概念和定义：涵盖了分布式硬件、分布式控制、分布式数据，并强调对用户透明的资源分布。 分布式系统的基本特点：包括以任意方式支持连接、更紧密的应用衔接、用户的无缝感以及可缩放性。 分布式系统的透明性：包括访问透明性、位置透明性、复制透明性、并发透明性、故障透明性和持久性透明性。 分布式系统的开放性：要求系统根据一系列准则提供服务，并强调接口的规范性和系统的灵活性。 分布式系统的可缩放性：考虑规模、地域和管理方面的扩展。 分布式系统与计算机网络的区别：使用上、结构上、适应范围和标准化程度等方面。 分布式系统中的基本模型：包括进程、通信系统和处理单元之间的关系。 分布式系统的基本问题和范型：包括工作目标、进程合作方案、控制方式、数据共享方案、故障解决方案等。 分布式系统的执行模型：包括乐观视角和悲观视角，分别强调系统的一致性和可用性。 分布式算法和集中式算法的区别：探讨了两种算法的不同点和使用场景。 异步和同步系统的固有矛盾：介绍了两种系统在分布式系统中的优缺点和适用场景。 CAP定理的指导下的系统选择：介绍了CAP定理的含义和指导下的系统设计原则。 在异步网络中生成BFS树相对于同步网络更为复杂，因为异步网络中节点之间的消息传递是非同步的，可能存在消息乱序、延迟和丢失。以下是在异步网络中生成BFS树的基本思路： 1.启动：选择一个节点作为根节点（可能需要一个外部激励），并将其标记为当前层级的0层。将根节点的邻居节点添加到当前层级的1层，并将它们标记为已访问。 2.BFS过程： -节点状态：每个节点维护一个状态，表示其在BFS树中的层级和父节点。 -消息发送：每个节点定期发送消息到其邻居，包含其当前层级和父节点信息。 -消息接收：节点接收邻居的消息，更新自身状态，然后将消息传递给其他邻居。 3.终止条件：当所有节点都完成BFS过程，即每个节点都知道其在BFS树中的层级和父节点时，算法终止。 在异步网络中，存在一些挑战，例如消息乱序和延迟，可能导致节点接收到不一致的信息。因此，需要使用一些技术来处理这些问题，例如使用时间戳或序列号来排序消息，以确保节点按照预期的顺序更新状态。 此外，为了实现终止条件，可能需要引入一些额外的机制，例如超时机制，以处理可能的消息丢失或长时间没有消息到达的情况。 总体来说，在异步网络中生成BFS树需要一些额外的技术和机制，以处理非同步环境中可能出现的问题。 这里提到的GHS（Gallager,Humblet,Spira）分布式最小生成树（MST）算法是一个经典的分布式算法，主要用于异步网络中构建最小生成树。 最小生成树： 1.用于领导者选举： -从叶子节点进行收敛，直到消息在节点或边上相遇。 -适用于任何生成树，不仅仅是最小生成树。 -消息复杂度的下限：Ω（nlogn）。 •给定一个节点数为n的无向图，通过GHSMST算法构建最小生成树，具有O（nlogn）的时间复杂度和O（nlogn+|E|）的消息复杂度。 •GHSMST算法采用了测试、接受、拒绝的协议来逐步形成最小生成树，其中包括测试两个节点是否属于同一组件，接受和拒绝的操作。 •在异步设置中，GHS算法的改进版本解决了关于出边的不准确信息和组件合并的不平衡问题，保持了O（nlogn+|E|）的消息复杂度。 •GHS算法也可以用于选择领导者，通过在形成的最小生成树上进行广播和收敛操作，时间复杂度为O（nlogn）。 •另外，文章还提到了容错系统和容错概念，包括可用性、可靠性、安全性、可维护性等方面。 •在容错系统中，容错的目标是在系统存在故障的情况下仍然能够达到其预期的能力，可以通过硬件冗余、软件冗余、信息冗余和时间冗余等手段来实现。
| 
