一种改进的高效分布式互斥请求集生成算法

摘要

算法运行的高效性是衡量算法优劣的一个重要标准.分布式互斥请求集的长度、对称性以及生成的难易程度直接影响着生成该请求集的分布式扶持算法的时间复杂度、对称性和算法的应用规模.本文在松弛循环差集的基础上,依据三角形网格结构的特征,提出了一种高效的请求集生成算法,改进了已有的基于松弛循环差集的请求集生成算法.该算法通过增加请求集的初始化节点数,使算法的时间复杂度大幅度降低,同时所生成的请求集长度仍然保持在√2N到2√N之间.