基于局部递归的动态多点初始化请求集生成算法

如何在保证请求集长度不显著增加的情况下使时间复杂度尽量减小,是对称分布式互斥请求集生成算法研究者必须解决的问题。通过动态增加初始化节点的方法,采用局部递归的方式设计了一种新的对称分布式互斥请求集生成算法。该算法能够保证请求集长度与其长度下限比较不会显著增加,而时间复杂度比WK算法及全局递归算法有显著下降。因此,通过对请求集本身特性的研究,能够部分解决请求集长度与请求集生成算法时间复杂度之间的矛盾。     

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

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

一种高效能的分布式请求集生成算法

分布式互斥请求集的长度、对称性和生成的难易程度以及生成算法占用的空间及耗费的时间直接影响着基于该请求集的分布式互斥算法的消息复杂度、对称性和算法的应用规模。本文在折半循环编码算法的基础上,提出了一种增加算法初始化节点数量和引入松弛差集的对称分布式互斥请求集生成算法,使算法的时间复杂度和消息复杂度大幅度降低。     

频繁项集挖掘算法

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

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

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

基于重复数的最短循环请求集生成算法

在分布式循环请求集长度最短时,针对请求集生成算法的时间复杂度和空间复杂度过高问题,提出了一种基于重复数的最短循环请求集生成算法。算法在基于循环松弛差集的思想上,以当前请求集差集允许的最大重复数作为判断条件,依次向请求集中添加元素。实验结果表明,系统节点数为70到90时,该算法在保证请求集长度最短,且空间复杂度为O(2N)的前提下,使得时间复杂度是穷搜方法的3.6E-03到6.8E-07,降低了最短循环请求集生成算法的时间复杂度。     

一种贪心策略的更高效的请求集生成算法

在折半循环编码算法的基础上,依据贪心策略对可纳入节点进行局部求最优的方式来生成请求集的算法,从而使算法的请求集长度下降了一个数量级,接近姨N。     

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

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

递归与循环算法分析

程序设计中没有用到循环或递归算法，很难解决一些实际问题。本文以斐波那契（Fibonacci）数列为例对递归与循环算法的时间复杂度作了比较、分析。     

递归与循环算法分析

程序设计中没有用到循环或递归算法,很难解决一些实际问题。本文以斐波那契(Fibonacci)数列为例对递归与循环算法的时间复杂度作了比较、分析。     

Quorum-based algorithms for group mutual exclusion

We propose a quorum system, which we referred to as the surficial quorum system, for group mutual exclusion. The surficial quorum system is geometrically evident and is easy to construct. It also has a nice structure based on which a truly distributed algorithm for group mutual exclusion can be obtained and processed loads can be minimized. When used with Maekawa's algorithm, the surficial quorum system allows up to /spl radic/2n/m(m-l) processes to access a resource simultaneously, where n is the total number of processes and m is the total number of groups. We also present two modifications of Maekawa's algorithm so that the number of processes that can access a resource at a time is not limited to the structure of the underlying quorum system, but to the number that the problem definition allows.     

移动自组网的访问控制技术研究

网络资源的共享与保护是移动自组网需要解决的关键问题之一。运用Voronoi图模型和quorum系统的思想,提出了一种移动自组网的动态路径quorum系统,设计了动态路径quorum的生成算法。基于移动自组网的动态路径quorum系统,提出了基于quorum系统的移动自组网的分布式访问控制机制,详细描述了节点的身份认证、网络资源的访问控制和权限管理协议。与传统的基于单个节点自身的访问控制机制相比,该访问控制机制具有较强的抗攻击能力和较高的可靠性,能够有效地提高移动自组网的资源共享与保护水平。     

Optimizing vote and quorum assignments for reading and writingreplicated data

In the weighted voting protocol which is used to maintain the consistency of replicated data, the availability of the data to ready and write operations not only depends on the availability of the nodes storing the data but also on the vote and quorum assignments used. The authors consider the problem of determining the vote and quorum assignments that yield the best performance in a distributed system where node availabilities can be different and the mix of the read and write operations is arbitrary. The optimal vote and quorum assignments depend not only on the system parameters, such as node availability and operation mix, but also on the performance measure. The authors present an enumeration algorithm that can be used to find the vote and quorum assignments that need to be considered for achieving optimal performance. When the performance measure is data availability, an analytical method is derived to evaluate it for any vote and quorum assignment. This method and the enumeration algorithm are used to find the optimal vote and quorum assignment for several systems. The enumeration algorithm can also be used to obtain the optimal performance when other measures are considered     

具有O(n)时间复杂度的分布式请求集生成算法

在大规模完全分布式系统的互斥问题上,快速生成请求集是必要的。在基于松弛差集的相关原理上,引入了二次松弛差集的概念。经分析相关概念及定理,将原本“求差”的过程变为“求和”的过程;进而利用 “求和”步骤间的递推关系,大大减少了求和步骤,使整个算法的时间复杂度控制在O(n)。与时间复杂度同为O(n^2)的其他经典算法相比,生成的请求集长度仍保持在2n^(1/2)的数量级。