一种基于松弛循环差集的对称分布式互斥算法

为在全分布系统中实现对称的分布式互斥,需要设计出对称的分布式互斥算法。通过证明循环请求集与松弛循环差集的等价性,将求取包含任意数量节点的分布式系统对称请求集的问题转化为求取任意数量节点集合的松弛差集问题,并在此基础上提出了一种基于循环松弛差集的对称分布式互斥请求集生成算法。在请求集生成算法的基础上,引入了转移应答消息和请求集重构消息,重新定义应答消息的结构以使其能够携带更多的信息,重新设计了分布式互斥算法的相关过程,从而改进了Makawa类分布式互斥算法的性能。该算法具有较高的时间效率和空间效率,其求取的请求集尺寸较小,使分布式互斥算法的消息复杂度降为O(2N),同步时间降为T,节点容错能力达到N-1。基于松弛循环差集的分布式互斥算法克服了以往分布式算法必须牺牲一种性能指标以提高另一种性能指标的缺点,具有很高的应用价值。

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

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

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

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

基于请求集与动态令牌的一种对称分布式互斥算法

提出了一种新的分布式互斥算法。该算法通过在基于竞争或请求集的分布式互斥算法中引入动态令牌的概念以及改变某些消息例如应答(reply)、释放(release)等消息的传送方向以及增加各类型消息的信息量将Makawa类算法的消息复杂度从O(3K～5K)降低到O(2K～4K),同时将算法的同步延迟从2T降低至T,并将算法的节点容错能力提高到N?2并保持算法无饥饿,无死锁。通过实际运行和对比,具有较高的使用价值。

一种分布式系统的进程同步与互斥算法

所介绍的算法以Goscinski算法[1]为基础，加以修正和细化，并进行了模拟运行，使之更适合于真网络环境。该算法不但能够在逻辑结构无要求的计算机网络中通过广播请求和令牌传送来同步对一个临界资源的访问，而且可以处理真网络中因报文丢失和延时较大所造成的令牌丢失、令牌重复、请求丢失等问题。

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

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

分布式系统中进程的同步与互斥算法讨论

详细阐述了分布式系统中进程的同步与互斥问题。对几种算法进行了讨论,分析了其特点,还提出了 令牌环算法的一个改进算法。该算法解决了在真网络中可能出现的部分问题,并经过了实验验证。

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

本文分析比较了传统互斥算法,提出了一种新的基于令牌的算法,并详细阐述算法的设计思想及其数据结构。本算法最主要的特点是在分布式互斥中引入了优先级和树的概念,能有效的降低进程间的通信量,以及保证互斥和预防死锁。

分布式系统进程互斥算法的分析与改进

本文对传统的几中互斥算法进行了讨论,分析了其特点,还提出了令牌环算法的一个改进。该算法解决互斥算法中出现的部分问题,并经过了实验验证。

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

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

多机系统中互斥算法的研究与实现

网络锁保证多机系统中互斥资源的安全,它的效率是系统节点扩充的关键。为此,在分析了各种互斥算法以后,将集中式和分布式结合起来,提出了根据不同资源选择不同控制节点的算法,并且在发现节点失效时转移有效请求和删除无效请求,在节点激活时将部分请求转移给它,实现负载平衡。实验表明,这种方法具有最少的消息量和很好的容错性,直到系统剩下一个节点,它仍然可以正确运行。

一个分布式K互斥算法的概率模型检测

传统的验证方法难以保证分布式K互斥算法的有效性和安全性。为解决这一问题,给出了进一步的研究,提出一种基于概率模型检测器PRISM的方法,对Kerry Raymond的分布式K互斥算法进行形式化建模与分析验证。通过设置算法中各个进程进入临界区的时间而得出的结果中发现,改变临界区的数目K,对于某一进程进入临界区的平均及时时间的影响并不大。如果某一进程的执行时间比其他进程大很多,则K的增加可以提高运行效率。最后证明了这一结论。

分布式系统中进程互斥算法的研究

文章通过对几种互斥算法的研究,认识到集中式算法的性能瓶颈以及非基于令牌的分布式算法的不健壮性,得到了改进后的基于令牌的分布式算法;通过对该算法的性能分析,并与前几种算法进行比较,验证了该算法是高效的,并给出正确性证明。

分布式系统中互斥算法的研究

公平、健壮和易于实现的分布式互斥算法对分布式系统保证数据一致性、逻辑一致性及时序一致性至关重要,互斥问题是分布式系统中一个非常重要的内容。互斥算法是用来解决共享资源访问冲突问题,阐述了分布式系统中进程的互斥问题。对几种算法进行了讨论,分析了其特点,最后给出了一个k-互斥问题的算法,并介绍了该算法应满足的条件和实现过程。

并行算法的评析与设计

本文利用一种典型的并行随机存取计算机 (PRAM)理论模型阐述并行算法一些简单的基本概念和技术 ,给出并行算法的一些评析和设计方法。

An Interruptable Lock and Unlock Algorithm

Generally, Lock and Unlock statements are primitives that should be wholly imple- mented,i.e.,the test of lock state and the operation of locking must be executed continuously without being interrupted. Different from nmormal lock operations, the lock and Unlock algorithm Presented in this paper can be interrupted anywhere by other processes The value of the algorithm in the implementation of concurrent control and mutually-exclusive operations was elucidated with one application of the algorithm in a heterogeneous datedbase united system.