摘要
算法运行的高效性是衡量算法优劣的一个重要标准。分布式互斥请求集的长度、对称性以及生成的难易程度直接影响着生成该请求集的分布式扶持算法的时间复杂度、对称性和算法的应用规模。本文在松弛循环差集的基础上,依据三角形网格结构的特征,提出了一种高效的请求集生成算法,改进了已有的基于松弛循环差集的请求集生成算法。该算法通过增加请求集的初始化节点数,使算法的时间复杂度大幅度降低,同时所生成的请求集长度仍然保持在(2N)^(1/2)到2N^(1/2)之间。
The high running efficiency is an important standard for measuring an algorithm. The length, symmetry and generation complexity of the distributed mutual exclusion quorum will directly affect the time complexity, symmetry and system scale of these distributed mutual exclusion algorithms based on it. Based on relaxed cyclic difference set and triangle grid structure, a new genera- tion algorithm has been proposed in this paper. Through increasing the number of initialization nodes, this algorithm makes the time complexity greatly reduced, at the same time the length of the quorums which it generated is between √2N and 2√N.
出处
《微计算机信息》
2010年第18期205-207,共3页
Control & Automation
关键词
松弛循环差集
三角形网格
请求集
分布式
互斥
relaxed cyclic difference set
triangle grid
quorum
distributed
mutual exclusion
