Experimental Evaluation on the Time Complexity for Mutual Exclusion Algorithm

Bibliographic Information

Other Title
  • 排他制御アルゴリズムの時間複雑度の実験的評価

Search this article

Description

Mutual exclusion is necessary in various situations in distributed and cooperative systems.Many algorithms of mutual exclusion were designed so far and theirperformance has been investigated.To check the perfomance,message complexity and time complexity are the two main factors.For the message complexity,the necessary number of messages for one trial of mutual exclusion, Maekawa′s √N> algorithm is well known.In this paper,the well kno wn Ricart-Agrawala′s algorithm(RA)and Maekawa′s algorithm(M*)are implemented in a distribute system and compared by the time complexity,the necessary delay time for one trial of mutual exclusion.From our experimental results,we find that with the increasing of the mutual exclusion frequency there exists a region where RA is surperior to MA for time complexity.

Journal

Keywords

Details 詳細情報について

  • CRID
    1570572702399544448
  • NII Article ID
    110003191702
  • NII Book ID
    AN10013152
  • Text Lang
    ja
  • Data Source
    • CiNii Articles

Report a problem

Back to top