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 a t any time. Each process may have different accessible resources. If two pr ocesses have no common accessible resource, it is reasonable to ensure a co ndition 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 allo cation algorithm proposed by H. Kakugawa and M. Yamashita ensures the above condition. We show a necessary and sufficient condition of the existence o f a sharing structure coterie. The decision of the existence of a sharing s tructure coterie for an arbitrary distributed system is NP-complete. Furthe rmore, we show a resource allocation algorithm which guarantees the above r equirement for distributed systems whose sharing structure coteries do not exist or are difficult to obtain.