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

書誌事項

タイトル別名
  • Experimental Evaluation on the Time Complexity for Mutual Exclusion Algorithm

この論文をさがす

説明

分散, 協調システムにおいては,様々な局面において排他制御を実施する必要が生じる.従来多くの排他制御アルゴリズムが提案されその有効性に関する議論が行われてきた.有効性を判断する基準としては,メッセージ複雑度と時間複雑度が存在する.メッセージ複雑度(一回の排他制御に必要とされる通信の回数)に関しては,前川の√N>アルゴリズムの有効性が良く知られている.本研究では,良く知られるRicart-Argrawalaアルゴリズム(RA)と前川アルゴリズム(MA)を分散システム上に実装し,これらの時間複雑度(一回の排他制御に必要とされる遅延時間)を測定する.測定の結果,排他制御要求の頻度が増加するに伴って,MAのRAに対する遅延時間に関する優位が逆転する領域が存在する事が分った.

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1570572702399544448
  • NII論文ID
    110003191702
  • NII書誌ID
    AN10013152
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ