Asynchronous message-passing distributed algorithm for the global critical section problem

• Kamei Sayaka

  Hiroshima University

• Kakugawa Hirotsugu

  Ryukoku University

抄録

This paper considers the global (l,k)-critical section problem which is the problem of controlling a system in such a way that at least l and at most k processes must be in the critical section at any time in the network, while each process alternates between in the critical section and out of the critical section. In this paper, first, a distributed solution for l-mutual inclusion is proposed in the asynchronous message-passing model. The proposed algorithm uses an ordinary quorum system and all processes play the same role, unlike existing algorithms for k-mutual exclusion. After that, using the proposed algorithm for l-mutual inclusion, we propose a distributed solution for the global (l, k)-critical section problem. The proposed approach is a versatile composition of algorithms for $l$-mutual inclusion and k-mutual exclusion. Its message complexity is typically O(√n), where n is the size of the network.

収録刊行物

• International Journal of Networking and Computing

  International Journal of Networking and Computing 9 (2), 147-160, 2019

  IJNC編集委員会

キーワード

• Distributed algorithm
• Mutual exclusion
• Mutual inclusion
• Process synchronization

詳細情報

• CRID: 1390001288153538560
• NII論文ID: 130007680118
• DOI: 10.15803/ijnc.9.2_147
• ISSN: 21852847
• ISSN: 21852839
• Web Site: https://www.jstage.jst.go.jp/article/ijnc/9/2/9_147/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可