## 3 Proposed Algorithm for the Generalized Local \(I_{i}\)-Mutual Inclusion
Hence, by Co-\(\mathcal{A}^{\mathcal{L}}_{(l_{i},k_{i})}\), at least \(l_{i}\) and at most \(k_{i}\) processes among each process and its neighbors are out of the CS. That is, at least \(|N_{i}|+1-k_{i}\) and at most \(|N_{i}|+1-l_{i}\) processes among each process and its neighbors are in the CS. By Theorem 2, Co-(\(l_{i}\)-LMUTIN) is an algorithm for the generalized local \((0,k_{i})\)-CS problem where \(k_{i}=|N_{i}|+1-l_{i}\). We call it \(k_{i}\)-LMUTEX. ## 5 Proposed Algorithm for the Generalized Local CS Problem

In this section, we propose an algorithm LKCSfor the generalized local \((l_{i},k_{i})\)-CS problem for arbitrary \((l_{i},k_{i})\), where \(0\leq l_{i}<k_{i}\leq|N_{i}|+1\) for each process \(P_{i}\). We assume that, the initial configuration \(C_{0}\) is safe. Before we explain the technical details of LKCS, we explain the basic idea behind it. ### Idea

The main strategy in LKCS is the composition of two algorithms, \(l_{i}\)-LMUTIN and \(k_{i}\)-LMUTEX. In the following description, we simply call these algorithms LMUTIN and LMUTEX, respectively. The idea of the composition in LKCS is as follows. **Exit-Sequence:**:

Exit-Sequence for LMUTIN;

Exit-Sequence for LMUTEX;

**Entry-Sequence:**:

Entry-Sequence for LMUTEX;

Entry-Sequence for LMUTIN;

This idea does not violate the safety by the following observation. * Exit-sequence keeps the safety because invocation of exit-sequence for LMUTIN keeps the safety, and invocation of exit-sequence for LMUTEX trivially keeps the safety. * Similarly, entry-sequence keeps the safety because invocation of entry-sequence for LMUTEX keeps the safety, and invocation of entry-sequence for LMUTIN trivially keeps the safety. Because invocations of exit-sequence for LMUTIN in exit-sequence and entry-sequence for LMUTEX in entry-sequence may block a process forever, i.e., deadlocks and starvations, we need some mechanism to such situation which makes the proposed algorithm non-trivial. A problem in the above idea is the possibility of deadlocks in the following situation. There is a process \(P_{u}\) with \(state_{u}=\ln\)CS such that \(|\mathcal{CS}_{u}(C)|=l_{u}\) or \(P_{u}\) has a neighbor \(P_{v}\in N_{u}\) with \(|\mathcal{CS}_{v}(C)|=l_{v}\). Then, \(P_{u}\) cannot change its state by exit-sequence until at least one of its neighbors \(P_{w}\in N_{u}\) with \(state_{w}=\mathsf{OutCS}\) changes \(P_{w}\)'s state by entry-sequence. If \(|\mathcal{CS}_{w}(C)|=k_{w}\) or \(P_{w}\) has a neighbor \(P_{x}\in N_{w}\) with \(|\mathcal{CS}_{x}(C)|=k_{x}\), \(P_{w}\) cannot change its state by entry-sequence until at least one of its neighbors \(P_{y}\in N_{w}\) with \(state_{y}=\mathsf{InCS}\) changes \(P_{y}\)'s state by exit-sequence. In the network, if every process is in such situation, a deadlock occurs. To avoid such a deadlock, we introduce a mechanism \"sidetrack\", meaning that some processes reserve some grants, which are used only when the system is suspected to be a deadlock. Hence, in a normal situation, i.e., not suspected to be a deadlock, the number of processes in the CS is limited. In this sense, LKCS is a partial solution to the \((l_{i},k_{i})\)-CS problem unfortunately. Currently, a full solution to the problem is not known and left as a future task. The idea of the \"sidetrack\" in LKCS is explained as follows. We select a process, say \(P_{LDR}\), with \(|N_{LDR}|\geq 4\) as a \"leader\", and each process \(P_{q}\) within two hops from the leader may allow at least \(l_{q}+1\) and at most \(k_{q}-1\) processes to be in the CSs locally in a normal situation. We assume that \(k_{q}-l_{q}\geq 3\), because \(k_{q}-1-(l_{q}+1)\geq 1\). Other processes \(P_{i}\) may allow at least \(l_{i}\) and at most \(k_{i}\) processes to be in the CSs locally in any situation and \(k_{i}-l_{i}\geq 1\). The leader observes the number of neighbor processes that may be blocked, and when the leader itself and all of the neighbors can be blocked, the leader suspects that the system is in a deadlock situation.