分布式互斥算法的研究与改进

在几种基于令牌算法的基础上,提出了一个对网络逻辑结构无要求的分布式互斥算法。算法不但能够在逻辑结构无要求的计算机网络中通过发送消息和传递令牌来同步对临界资源的访问,而且可以很好地解决请求丢失、令牌丢失等问题。通过对算法的性能进行分析验证了该算法是高效的,并给出了正确性证明。     

一种分布式操作系统中k个资源的互斥算法

本文针对分布式操作系统中k个资源提出一个互斥算法,给出了算法的步骤.最后用实验进行了验证.     

一种广域网中的分布式互斥算法

广域网可简单地看作由多个局域网通过远程通信线路互连组成。为了适应广域网环境的特点,文章提出了一种两层结构的分布式互斥算法模型,把广域网系统组织成由局部进程组成的局部网络的由每个局部网络中的协调进程组成的全局两层。为了互斥地访问共享资源,局部进程必须首先获得局部令牌,然后再向本地协调进程申请全局令牌,只有获得了局部和全避令牌的局部进程才能进入临界区。还讨论了对该算法可能的扩展。     

一种基于令牌的新的互斥算法分析与设计

在对现有典型分布式系统中互斥算法研究的基础上, 本文依据令牌技术, 提出了一种分布式系统中解决互斥问题的新算法.文中对算法的设计思想及实现过程进行了详细描述, 同时对其性能进行了严格的理论证明和分析, 该算法能有效地提高系统的通信效率.     

一种基于消息槽的K资源互斥算法

在银行系统等有多个实体同时活跃的分布式应用中,必须妥善解决不同实体对资源的需求,即同步与互斥。本文基于令牌的K资源互斥算法,提出了基于消息槽的K资源互斥算法,该算法能有效满足K资源分布式环境下同步与互斥的要求。     

一种高效的总线网络分布式协商算法

为了解决总线网络中的分布式数据一致性问题,提出了一种高效的分布式协商算法。该算法通过“模”运算将分布式决策问题转化为单机决策,提高了算法的效率,减少了所需的消息数。通过消息复用方式减少了算法的消息种类,缩短了响应延迟。性能分析和仿真试验表明,该算法将消息复杂度压缩至O(1)和时间复杂度压缩至(T+E)×|Cset|+2×T（其中,Cset是并发集,T是点到点通信的平均延迟;E是每次临界操作的平均延迟）。     

基于Token追踪的分布式互斥算法

本文首先提出一切合实际的互斥信件量度量方法,该方法不仅考虑请求结点所发的信息数,同时还考虑信件的存储转发次数,然后针对任一拓扑结构,在充分利用局部信息与已知信息的基础上,给出了互斥信件量为0～2(n—1)(n为结点数)的有效互斥算法,该算法不仅在互斥信件量上是目前最优的,而且充分体现了分布式算法设计的一个重要原则,充分利用一切已知信息作为未来决策的依据。     

一种新的分布式互斥请求集生成算法

分布式互斥请求集的长度、对称性和生成的难易程度以及生成算法占用的空间及耗费的时间直接影响着基于该请求集的分布式互斥算法的消息复杂度、对称性和算法的应用规模。本文在基于循环编码的分布式互斥请求集生成算法的基础上,提出了一种增加算法初始化节点数量的对称分布式互斥请求集生成算法。其生成的请求集长度小于2N0.5,其时间复杂度也比基于循环编码的分布式互斥请求集生成算法小。因此,该算法较已有的分布式互斥请求集生成算法在性能上具有较大提高。     

非稳定环境下基于竞争消息复杂度的分布式互斥节点容错算法

目前人们已经提出了很多分布式互斥算法。为简化问题,这些算法多数要求假设系统的节点与通信均可靠,因此不存在容错处理问题。部分在先假定节点与通信可靠的基础上讨论的算法,为达到其结论的逻辑严密性,补充了节点与通信不可靠时的容错处理,但这些容错处理方式都是作为其分布式互斥算法的补充提出来的,有较大程度的理想化成分,基本上没用进行充分的性能分析。本文根据分布式互斥算法节点容错处理方式的不同,将其分为两类并对其对消息复杂度的影响进行详细讨论。在此基础上,提出一种混合的分布式互斥节点容错处理方法,以降低非稳定环境下分布式互斥算法的平均消息复杂度。     

非稳定环境下基于竞争消息复杂度的分布式互斥节点容错算法

目前人们已经提出了很多分布式互斥算法.为简化问题,这些算法多数要求假设系统的节点与通信均可靠,因此不存在容错处理问题.部分在先假定节点与通信可靠的基础上讨论的算法,为达到其结论的逻辑严密性,补充了节点与通信不可靠时的容错处理,但这些容错处理方式都是作为其分布式互斥算法的补充提出来的,有较大程度的理想化成分,基本上没用进行充分的性能分析.本文根据分布式互斥算法节点容错处理方式的不同,将其分为两类并对其时消息复杂度的影响进行详细讨论.在此基础上,提出一种混合的分布式互斥节点容错处理方法,以降低非稳定环境下分布式互斥算法的平均消息复杂度.     

一种基于消息槽的K资源互斥算法

在分布式操作系统等一些有多个进程同时活跃的应用中,必须妥善解决不同进程对资源的需求,即同步与互斥问题.文章提出了一种基于消息槽的K资源互斥算法,介绍了该算法的原理,详细描述了该算法的运作过程,并进行了深入的分析.分析结果表明,该算法能够有效地满足K资源分布式环境下同步与互斥的要求.     

基于半环仲裁集的环网分布式互斥算法

分布式互斥是环网分布式系统的重要问题.根据此类系统的特点,提出了新型的分布式互斥算法.该算法以请求者自身为中心,基于半环生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"探测"消息进行系统的容错处理.分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能.     

基于树拓扑网络的分布式互斥算法

分布式互斥是分布式系统的重要问题.根据树拓扑网络的特点,提出了新型的分布式互斥算法TNDME.算法的运行范围限制在根节点到请求节点之间,采用循径方法生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"最大残存树"探测方法进行系统的容错处理.描述了算法的模型、主要思想、数据结构、消息结构以及伪代码,并证明了算法的正确性.理论性能分析与仿真对比证明,算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能.     

多副本访问控制的分层结构分布式互斥算法

提出了一种用于分布式系统中多副本对象访问控制的分层结构分布式互斥实现方法,可以显著降低分布式系统中互斥访问算法的消息复杂度,并提高了系统和算法的容错能力和稳定性,为构建超大规模分布式系统,保证分布式系统中的多副本对象的互斥和一致访问提供了实现手段。     

基于优先级组的分布式互斥算法的改进

主要介绍了一种分布式互斥算法的改进方案，首先简要介绍了基于权标的常规算法，然后提出了优先级组算法的另一种方案，并详细阐述算法的设计思想及其数据结构，本算法最主要的特点是在分布式互斥中引入了优先级和树的概念，从而将Raymond和Ricart_Agrawala互斥算法较好地结合了起来。     

改进的分布式互斥请求集生成算法

在分布式系统中,各节点必须互斥地访问临界区.节点的请求集的长度决定了系统的效率、性能.虽然最优请求集的节点数最少(大约n),但已有的解决方案该类问题算法类似于穷举法,随着节点的增加,该方法变得不可计算.提出了一种快速的请求集生成算法,该算法以循环差集请求集生成算法的理论和贪心算法的基本思想为基础,在每次迭代的过程中,选出一个当前条件下最优的节点加入请求集.与其他的方法相比较,该方法能对任意给定的整数快速、有效地生成对称的请求集.本算法时间复杂度为O(n2),生成的请求集长度为n～2n.     

基于直径仲裁集的网格网络分布式互斥算法

分布式互斥是网格分布式系统的重要问题。根据网格系统的特点,提出了新型的分布式互斥算法。该算法基于网格网络的直径生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用“探测”消息进行系统的容错处理。分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能。     

一种改进的双令牌互斥算法

互斥是解决分布式系统中资源申请的相互冲突、实现资源共享的一种有效方法.文中对目前的一些互斥算法进行了介绍,并对集中式互斥算法和分布式互斥算法进行了讨论,并分析了其特点.在简要介绍令牌环算法和双令牌算法的思想和步骤后,提出一种改进的双令牌算法.详细叙述了改进算法的设计思想和实现步骤,对性能进行了分析并给出算法示例.讨论结果表明,与原有的双令牌算法相比,新算法可以以更高效率有效检测令牌丢失并实现令牌重构.     

自适应Ad hoc分布式互斥算法

Ad hoc网络的动态拓扑结构和节点自组织给分布式算法的实现带来了诸多困难.针对Ad hoc分布式互斥算法研究滞后的现状,提出了一种自适应的Ad hoc分布式算法ADMUTEX. ADMUTEX算法基于令牌查询方法,它采用Lamport逻辑时戳保证消息的时序性,避免了节点饿死.同时,它在消息复杂度与同步延迟之间作了折衷,而且它不需要节点了解系统的全局信息,能够适应Ad hoc网络的动态拓扑结构和节点频繁出入的情况.分析与仿真结果表明该算法具有较低的消息复杂度、小响应延迟和公平性.