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