Title :
A wrong opinion about quorum generation algorithm for distributed mutual exclusion
Author :
Li, Mei-An ; Wang, Bu-Yu ; Li, Wei ; Ma, Dong
Author_Institution :
Coll. of Comput. & Inf. Eng., Inner Mongolia Agric. Univ., Huhehaote, China
Abstract :
All the quorum generation algorithms based on greedy algorithm before denotes that the number of nodes selected to insert the quorum should change from one to N0.5, and the time complexity should change from O (2N3.5) to O (N!). Based on this phenomenon, a reasonable supposition will be proposed as follow: When the number of nodes selected to insert in quorum once is belong with the natural number set of [1, N0.5], the quorum length should change in set of [N0.5, 2 N0.5]and the time complexity of the quorum generation algorithm should change in the natural number set of [O (2N3.5), O (N!)]. And along with the number of nodes selected to insert in quorum once increasing, the quorum length will change from 2 N0.5 to N0.5, and the time complexity of the quorum generation algorithm should change from O(2N3.5) to O (N!). The quorum generation algorithm with k-nodes selected based on greedy algorithm has been designed to prove the supposition. And the outcome from k-nodes quorum generation algorithm and the analysis to the algorithm denote that the supposition is wrong.
Keywords :
computational complexity; greedy algorithms; distributed mutual exclusion; greedy algorithm; k nodes quorum; quorum generation algorithm; time complexity; wrong opinion; Agricultural engineering; Agriculture; Algorithm design and analysis; Distributed computing; Educational institutions; Electronic mail; Greedy algorithms; Length measurement; Time measurement; Greedy Algorithm; Quorum Generation Algorithm; Supposition; Wrong;
Conference_Titel :
Apperceiving Computing and Intelligence Analysis, 2009. ICACIA 2009. International Conference on
Conference_Location :
Chengdu
Print_ISBN :
978-1-4244-5204-0
Electronic_ISBN :
978-1-4244-5206-4
DOI :
10.1109/ICACIA.2009.5361144