| 具有O(n)时间复杂度的分布式请求集生成算法 |
| |
| 引用本文： | 武鹏,李美安.具有O(n)时间复杂度的分布式请求集生成算法[J].计算机应用,2013,33(2):323-360. |
| |
| 作者姓名： | 武鹏 李美安 |
| |
| 作者单位： | 1. 山西工程职业技术学院 计算机工程系，太原 0300092. 内蒙古农业大学 计算机与信息工程学院，呼和浩特 010018 |
| |
| 摘 要： | 在大规模完全分布式系统的互斥问题上，快速生成请求集是必要的。在基于松弛差集的相关原理上，引入了二次松弛差集的概念。经分析相关概念及定理，将原本“求差”的过程变为“求和”的过程;进而利用 “求和”步骤间的递推关系，大大减少了求和步骤，使整个算法的时间复杂度控制在O(n)。与时间复杂度同为O(n^2)的其他经典算法相比，生成的请求集长度仍保持在2n^(1/2)的数量级。
|
| 关 键 词： | 分布式互斥 请求集 松弛差集 时间复杂度 |
| 收稿时间： | 2012-08-29 |
| 修稿时间： | 2012-10-22 |
Quorum generation algorithm with time complexity of O(n) |
| |
| WU Peng
,
LI Meian.Quorum generation algorithm with time complexity of O(n)[J].journal of Computer Applications,2013,33(2):323-360. |
| |
| Authors: | WU Peng LI Meian |
| |
| Affiliation: | 1. Department of Computer Engineering, Shanxi Engineering Vocational College, Taiyuan Shanxi 030009, China2. College of Computer and Information Engineering, Inner Mongolia Agriculture University, Hohhot Inner Mongolia 010018, China |
| |
| Abstract: | It is necessary to generate the quorums as soon as possible in large-scale fully distributed system for its mutual exclusion problem. Based on the theory of relaxed cyclic difference set, the definition of second relaxed cyclic difference set was proposed. After researching the new concepts, the subtraction steps in previously classical methods can be changed into summation steps. Furthermore, a lot of summation steps can be cut down by the recurrence relation deduced from the summation steps. The time complexity of this algorithm is just only O(n) and the size of the symmetric quorums is still close to 2n^(1/2). |
| |
| Keywords: | distributed mutual exclusion quorum relaxed cyclic difference time complexity |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用》浏览原始摘要信息 |
|
点击此处可从《计算机应用》下载全文 |
