基于有限递归的最短长度循环请求集生成算法

如何在最短的时间内生成长度最短的对称循环请求集,是当前分布式计算乃至云计算必须解决的问题。提出了一种基于有限递归的最短长度对称循环请求集生成算法。该算法通过减少每一个递归层次的递归次数,在不增加请求集长度的情况下,能够有效地减少请求集生成过程中节点尝试的次数,从而有效地降低算法的时间复杂度,具有较高的实用价值。     

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

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

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

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

一种高效的基于可复制资源的分布式负载均衡策略

为了克服传统负载均衡策略的缺陷,本文提出了一种高效的基于可复制资源的分布式负载均衡策略.在传统负载均衡策略基础上,本文提出了将节点的资源负载分为内部、外部和转发负载,并且分别进行处理的策略;同时给出了该策略的模型.此外,本文提出了负载的方向性概念,并将它应用于负载均衡策略中.最后,分析及仿真结果证明,该策略能够有效的均衡负载,减小内部通信量,同时能够有效的抑制系统负载抖动.     

ADLE:一种Ad hoc网络分布式领导者选取算法

Ad hoc网络的动态拓扑结构和节点自组织给分布式算法的实现带来了诸多困难.Ad hoc网络分布式领导者选举算法:ADL.该算法基于广播机制,采用逻辑时戳保证消息的时序性,避免了节点饿死.同时,它通过缩小算法执行范围降低了消息复杂度,而且不需要节点了解系统中所有节点的信息,因而能够适应Ad hoc网络的动态拓扑结构和节点频繁出入.分析与仿真结果表明该算法具有较低的消息复杂度、小响应延迟和公平性.     

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

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

基于角边特征的纸质碎片自动拼接复原算法

针对人工复原纸质文物碎片存在尝试次数多、拼接速度慢、复原准确性与完成度低等问题，提出一种依据碎片角度与边长特征进行纸质文物碎片自动拼接复原的算法。首先，将碎片图像进行预处理并根据碎片的角度值进行粗匹配，得到角度值相等的碎片图像；然后，在粗匹配的基础上，利用碎片的角边长进行细匹配减少重叠情况，得到碎片图像的基本匹配结果；最后，利用凹凸函数对方向相对的碎片图像情况进行遗漏弥补，并运用震荡函数对最终匹配图像进行缝隙弥补得到完整拼接结果。理论分析和碎片拼接仿真实验结果表明，与特征点、近似多边形拟合、角序列匹配等碎片自动拼接算法相比，所提算法的拼接准确率、拼接完成度与拼接耗时分别至少提高了12个百分点、11个百分点与10个百分点。所提基于角边特征的碎片拼接算法减少了繁琐的图像计算步骤，精确了碎片匹配结果，使得在实际文物修复等工程中能够实现非规则碎片高效、高精准的匹配。     

任意拓扑结构Ad hoc网络的分布式一致性算法

为了解决Ad hoc网络中的分布式一致性问题,在对其特性分析的基础上,提出了新的Ad hoc模型以及新的Ad hoc分布式一致性算法ADC (Ad hoc Distributed Consensus)。这种算法基于传统的令牌查询,使用广播在任意拓扑结构的网络中查找令牌,同时,该算法使用带有Lamport时戳的请求消息和动态队列。较之传统算法,它能够较好的适应Ad hoc网络中节点频繁出入的情况。仿真与分析结果表明：该算法具有较低的消息复杂度、较小的空间复杂度和较短的响应延迟。     

频繁项集挖掘算法

在松弛循环差集的基础上,依据局部贪心策略对可纳入节点以局部求优的方式来生成请求集的算法,使算法的时间复杂度降低一个数量级,同时所生成的请求集长度仍然保持在2N2N,从而更有利于在通信中推广使用。     

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

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