基于贪心策略的高效能分布式请求集生成算法

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

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

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

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

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

基于差集的高效能分布式请求集生成算法

在折半循环编码算法的基础上,提出了一种增加算法初始化节点数量和松弛正向差集的对称分布式互斥请求集生成算法,使算法的时间复杂度大幅度降低,而所生成的请求集长度仍然保持(2N)^(1/2)～2N^(1/2)之间。