Coterie for Generalized Mutual Exclusion Problem

概要

論文の詳細を見る
This paper discusses the generalized mutual exclusion problem defined by H. Kakugawa and M. Yamashita. A set of processes shares a set of resources of an identical type. Each resource must be accessed by at most one process at any time. Each process may have different accessible resources. If two processes have no common accessible resource, it is reasonable to ensure a condition in resource allocation, which is called allocation independence in this paper, i,e., resource allocation to those processes must be performed without any interference. In this paper, we define a new structure, sharing structure coterie. By using a sharing structure coterie, the resource allocation algorithm proposed by H. Kakugawa and M. Yamashita ensures the above condition. We show a necessary and sufficient condition of the existence of a sharing structure coterie. The decision of the existence of a sharing structure coterie for an arbitrary distributed system is NP-complete. Furthermore, we show a resource allocation algorithm which guarantees the above requirement for distributed systems whose sharing structure coteries do not exist or are difficult to obtain.
社団法人電子情報通信学会の論文
1999-05-25