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

An Improved High Efficiency Distributed Mutual Exclusion Quorum Generation Algorithm

作　　者：申二威[1] 李美安[1] 裴喜春[1] 武鹏[1] 

机构地区：[1]内蒙古农业大学计算机与信息工程学院,内蒙古呼和浩特010018

出　　处：《微计算机信息》2010年第18期205-207,共3页Control & Automation

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

关 键 词：松弛循环差集 三角形网格 请求集 分布式 互斥 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]