• DocumentCode
    2785598
  • 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
  • fYear
    2009
  • fDate
    23-25 Oct. 2009
  • Firstpage
    97
  • Lastpage
    100
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • 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
  • Type

    conf

  • DOI
    10.1109/ICACIA.2009.5361144
  • Filename
    5361144