共查询到18条相似文献,搜索用时 109 毫秒
1.
非稳定环境下基于竞争消息复杂度的分布式互斥节点容错算法 总被引:1,自引:0,他引:1
目前人们已经提出了很多分布式互斥算法。为简化问题,这些算法多数要求假设系统的节点与通信均可靠,因此不存在容错处理问题。部分在先假定节点与通信可靠的基础上讨论的算法,为达到其结论的逻辑严密性,补充了节点与通信不可靠时的容错处理,但这些容错处理方式都是作为其分布式互斥算法的补充提出来的,有较大程度的理想化成分,基本上没用进行充分的性能分析。本文根据分布式互斥算法节点容错处理方式的不同,将其分为两类并对其对消息复杂度的影响进行详细讨论。在此基础上,提出一种混合的分布式互斥节点容错处理方法,以降低非稳定环境下分布式互斥算法的平均消息复杂度。 相似文献
2.
本文首先提出一切合实际的互斥信件量度量方法,该方法不仅考虑请求结点所发的信息数,同时还考虑信件的存储转发次数,然后针对任一拓扑结构,在充分利用局部信息与已知信息的基础上,给出了互斥信件量为0~2(n—1)(n为结点数)的有效互斥算法,该算法不仅在互斥信件量上是目前最优的,而且充分体现了分布式算法设计的一个重要原则,充分利用一切已知信息作为未来决策的依据。 相似文献
3.
4.
5.
6.
在分布式系统中,各节点必须互斥地访问临界区.节点的请求集的长度决定了系统的效率、性能.虽然最优请求集的节点数最少(大约n),但已有的解决方案该类问题算法类似于穷举法,随着节点的增加,该方法变得不可计算.提出了一种快速的请求集生成算法,该算法以循环差集请求集生成算法的理论和贪心算法的基本思想为基础,在每次迭代的过程中,选出一个当前条件下最优的节点加入请求集.与其他的方法相比较,该方法能对任意给定的整数快速、有效地生成对称的请求集.本算法时间复杂度为O(n2),生成的请求集长度为n~2n. 相似文献
7.
分布式双环网络的容错算法 总被引:1,自引:0,他引:1
敖志刚 《计算机工程与应用》1992,(1):23-28
本文提供的算法包括:在双环网络硬故障的条件下,算法能用各种信号指示出网络故障的性质和位置,正确地对网络进行修复和连接,自动地形成子回路,实现对网络的重构,保证每个子环只有一个循环令牌,建立和维持最佳的工作状态。当网络发生拓扑变化时,算法能动态地适应这种变化,达到最佳的连接。另外还对网络安全工作的方式作了一些介绍。 相似文献
8.
在几种基于令牌算法的基础上,提出了一个对网络逻辑结构无要求的分布式互斥算法。算法不但能够在逻辑结构无要求的计算机网络中通过发送消息和传递令牌来同步对临界资源的访问,而且可以很好地解决请求丢失、令牌丢失等问题。通过对算法的性能进行分析验证了该算法是高效的,并给出了正确性证明。 相似文献
9.
10.
自适应Ad hoc分布式互斥算法 总被引:1,自引:0,他引:1
Ad hoc网络的动态拓扑结构和节点自组织给分布式算法的实现带来了诸多困难.针对Ad hoc分布式互斥算法研究滞后的现状,提出了一种自适应的Ad hoc分布式算法ADMUTEX. ADMUTEX算法基于令牌查询方法,它采用Lamport逻辑时戳保证消息的时序性,避免了节点饿死.同时,它在消息复杂度与同步延迟之间作了折衷,而且它不需要节点了解系统的全局信息,能够适应Ad hoc网络的动态拓扑结构和节点频繁出入的情况.分析与仿真结果表明该算法具有较低的消息复杂度、小响应延迟和公平性. 相似文献
11.
Ye-In Chang 《Journal of Parallel and Distributed Computing》1996,33(2):107
In the problem of mutual exclusion, concurrent access to a shared resource using a structural program abstraction called acritical section(CS) must be synchronized such that at any time only one process can enter the CS. In a distributed system, due to the lack of both a shared memory and a global clock, and due to unpredictable message delay, the design of a distributed mutual exclusion algorithm that is free from deadlock and starvation is much more complex than that in a centralized system. Based on different assumptions about communication topologies and a widely varying amount of information maintained by each site about other sites, several distributed mutual exclusion algorithms have been proposed. In this paper, we suvrey and analyze several well-known distributed mutual exclusion algorithms according to their related characteristics. We also compare the performance of these algorithms by a simulation study. Finally, we present a comparative analysis of these algorithms. 相似文献
12.
在对现有典型分布式系统中互斥算法研究的基础上, 本文依据令牌技术, 提出了一种分布式系统中解决互斥问题的新算法.文中对算法的设计思想及实现过程进行了详细描述, 同时对其性能进行了严格的理论证明和分析, 该算法能有效地提高系统的通信效率. 相似文献
13.
分布式互斥是网格分布式系统的重要问题。根据网格系统的特点,提出了新型的分布式互斥算法。该算法基于网格网络的直径生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用“探测”消息进行系统的容错处理。分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能。 相似文献
14.
分布式互斥是分布式系统的重要问题.根据树拓扑网络的特点,提出了新型的分布式互斥算法TNDME.算法的运行范围限制在根节点到请求节点之间,采用循径方法生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"最大残存树"探测方法进行系统的容错处理.描述了算法的模型、主要思想、数据结构、消息结构以及伪代码,并证明了算法的正确性.理论性能分析与仿真对比证明,算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能. 相似文献
15.
In this paper, we propose a token-based distributed mutual exclusion algorithm that is resilient to site and communication failures. The protocol uses the notion of logical time to detect the loss of the token and to recover the state of the lost token. Unlike other approaches, this results in the integration of token recovery due to failures with the protocol itself. Thus, we eliminate the need for expensive election protocols that are generally used in token-based algorithms to regenerate lost tokens. We also introduce the notion of weakly consistent replicated queues that are used to ensure freedom from starvation. 相似文献
16.
17.
分布式互斥是环网分布式系统的重要问题.根据此类系统的特点,提出了新型的分布式互斥算法.该算法以请求者自身为中心,基于半环生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"探测"消息进行系统的容错处理.分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能. 相似文献
18.
分布式互斥是网格分布式系统的重要问题.根据网格系统的特点,提出了新型的分布式互斥算法.该算法基于网格网络的行列生成分布式互斥十字仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"探测"消息进行系统的容错处理.分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能. 相似文献