## 3 Proposed Algorithm for the Generalized Local \(I_{i}\)-Mutual Inclusion
Then, \(P_{j}\) eventually sends a \(\langle\mathsf{Grant}\rangle\) message to \(P_{i}\), and \(P_{i}\) eventually sends a \(\langle\mathsf{Grant}\rangle\) message to itself. * Suppose that \(P_{j}\) does not change into the \(\mathsf{InCS}\) and \(\mathsf{OutCS}\) states alternately infinitely often. Because the timestamp of \(P_{i}\) is smaller than that of \(P_{j}\), by assumption, \(P_{j}\)'s permission is preempted, and a \(\langle\mathsf{Grant}\rangle\) message is sent from \(P_{j}\) to \(P_{i}\). In addition, \(P_{i}\) sends a \(\langle\mathsf{Grant}\rangle\) message to itself. Therefore, \(P_{i}\) eventually receives a \(\langle\mathsf{Grant}\rangle\) message from each process in \(N_{i}\cup\{P_{i}\}\), and the wait until statement in the exit-sequence does not block \(P_{i}\) forever. ### Performance Analysis

**Lemma 3**. : _The message complexity of \(l_{i}\)-LMUTINfor \(P_{i}\in V\) is \(3(|N_{i}|+1)\) in the best case and \(6(|N_{i}|+1)\) in the worst case._

Proof. : First, let us consider the best case. In exit-sequence, for \(P_{i}\)'s exiting the CS, \(P_{i}\) sends a \(\langle\mathsf{Request},ts_{i},P_{i}\rangle\) message to each process in \(N_{i}\cup\{P_{i}\}\); each process in \(N_{i}\cup\{P_{i}\}\) sends a \(\langle\mathsf{Grant}\rangle\) message to \(P_{i}\). In entry-sequence, after \(P_{i}\)'s entering the CS, \(P_{i}\) sends a \(\langle\mathsf{Release},P_{i}\rangle\) message to each process in \(N_{i}\cup\{P_{i}\}\). Thus, \(3(|N_{i}|+1)\) messages are exchanged. Next, let us consider the worst case. For \(P_{i}\)'s exiting the CS, \(P_{i}\) sends a \(\langle\mathsf{Request},ts_{i},P_{i}\rangle\) message to each process \(P_{i}\) in \(N_{i}\cup\{P_{i}\}\). Then, \(P_{i}\) sends a \(\langle\mathsf{Preempt},P_{i}\rangle\) message to the process \(P_{m}\) to which \(P_{j}\) sends a \(\langle\mathsf{Grant}\rangle\) message, \(P_{m}\) sends a \(\langle\mathsf{Relinquish},P_{m}\rangle\) message back to \(P_{j}\) and \(P_{j}\) sends a \(\langle\mathsf{Grant}\rangle\) message to \(P_{i}\). After \(P_{i}\)'s entering the CS, \(P_{i}\) sends a \(\langle\mathsf{Release},P_{i}\rangle\) message to each process \(P_{j}\) in \(N_{i}\cup\{P_{i}\}\). Then, \(P_{j}\) sends a \(\langle\mathsf{Grant}\rangle\) message to return a grant to \(P_{m}\) or grant to some process with the highest priority in \(\mathit{pendingReq}_{j}\). Thus, \(6(|N_{i}|+1)\) messages are exchanged. **Theorem 1**. : \(l_{i}\)_-LMUTIN solves the generalized local \((l_{i},|N_{i}|+1)\)-critical section problem with a message complexity of \(O(\Delta)\), where \(\Delta\) is the maximum degree of a network._

## 4 The Generalized Local Complementary Theorem

In this section, we discuss the relationship between the generalized local CS problems. Let \(\mathcal{A}^{\mathcal{G}}_{(l_{k})}\) be an algorithm for the global \((l_{i},k)\)-CS problem, and \(\mathcal{A}^{\mathcal{L}}_{(l_{i},k_{i})}\) be an algorithm for the generalized local \((l_{i},k_{i})\)-CS problem. By Co-\(\mathcal{A}^{\mathcal{G}}_{(l,k)}\)(resp., Co-\(\mathcal{A}^{\mathcal{L}}_{(l_{i},k_{i})}\)), we denote a complement algorithm of \(\mathcal{A}^{\mathcal{G}}_{(l,k)}\)(resp., \(\mathcal{A}^{\mathcal{L}}_{(l_{i},k_{i})}\)), which is obtained by swapping the process states, InCS and OutCS. In [12], it is shown that the complement of \(\mathcal{A}^{\mathcal{G}}_{(l,k)}\) is a solution to the global \((n-k,n-l)\)-CS problem. We call this relation the complementary theorem. Now, we show the generalization of the complementary theorem for the settings of local CS problems. Theorem 2: _For each process \(P_{i}\), a pair of numbers \(l_{i}\) and \(k_{i}\)\((0\leq l_{i}<k_{i}\leq|N_{i}|+1)\) is given. Then, Co-\(\mathcal{A}^{\mathcal{L}}_{(l_{i},k_{i})}\) is an algorithm for the generalized local \((|N_{i}|+1-k_{i},|N_{i}|+1-l_{i})\)-CS problem._

Proof: By \(\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 in the CS.