## 3 Proposed Algorithm for the Generalized Local \(I_{i}\)-Mutual Inclusion
If \(|\mathcal{CS}_{w}(C)|=k_{w}\) holds 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 the entry-sequence until at least one of its neighbors \(P_{y}\in N_{w}\) with \(\mathit{state}_{y}=\mathsf{InCS}\) changes \(P_{y}\)'s state by the exit-sequence. By such chain relationship, it is clear that the waiting chain can be broken if at least one process on this chain changes its state. Thus, for the assumption, all processes in \(V\) are in such a chain in \(C\), that is \(V=D\). However, in such a \(C\), all of \(P_{LDR}\) and its neighbors are waiting for grant messages from their neighbors. That is, their requests are in \(\mathit{grantedTo}_{LDR}\) or \(\mathit{pendingR}_{LDR}\), and \(\mathit{Waiting}_{LDR}\) is equal to \(|N_{LDR}|+1\). Additionally, we assume that \(k_{LDR}-l_{LDR}\geq 3\) and the number of grants \(P_{LDR}\) can send with \(\mathsf{MUTIN}\) (resp., \(\mathsf{MUTEX}\)) is \(|N_{LDR}|+1-(l_{LDR}+1)\) (resp., \(k_{LDR}-1\geq l_{LDR}+2\)). Because of safety, \(|\mathit{grantedTo}_{LDR}[\mathsf{MUTIN}]|=|N_{LDR}|-l_{LDR}\) or \(|\mathit{grantedTo}_{LDR}[\mathsf{MUTEX}]|=k_{LDR}-1\) holds. Then, \(P_{LDR}\) sends a \(\langle\mathsf{Trigger},at,ts\rangle\) message to a neighbor \(P_{q}\) and \(P_{q}\) becomes a trigger if \(P_{q}\) is also waiting for grant messages. Processes \(P_{r}\) that receive \(\langle\mathsf{RequestByTrigger},at,P_{q}\rangle\) grant the request without attention to \(|\mathcal{CS}_{r}(C)|\). Then, \(P_{q}\) can change its state, and after that, \(P_{LDR}\) can change its state. Therefore, the waiting chain in \(C\) can be broken. This is a contradiction. ### Performance Analysis

**Lemma 6**: _The message complexity of LKCS for \(P_{i}\in V\) is \(6(|N_{i}|+1)\) in the best case, and \(12(|N_{i}|+1)\) in the worst case._

First, let us consider the best case. * For \(P_{i}\)'s exiting the CS, \(P_{i}\) sends a \(\langle\mathsf{Request},\mathsf{MUTIN},ts_{i},P_{i}\rangle\) message to each process in \(N_{i}\cup\{P_{i}\}\); each process \(P_{j}\) in \(N_{i}\cup\{P_{j}\}\) sends a \(\langle\mathsf{Grant},\mathsf{MUTIN},P_{j}\rangle\) message to \(P_{i}\); then \(P_{i}\) sends a \(\langle\mathsf{Release},\mathsf{MUTIN},P_{i}\rangle\) message to each process in \(N_{i}\cup\{P_{i}\}\). Thus, \(3(|N_{i}|+1)\) messages are exchanged for \(P_{i}\)'s exiting the CS. * For \(P_{i}\)'s entering the CS, \(P_{i}\) sends a \(\langle\mathsf{Request},\mathsf{MUTEX},ts_{i},P_{i}\rangle\) message to each process in \(N_{i}\cup\{P_{i}\}\); each process \(P_{j}\) in \(N_{i}\cup\{P_{i}\}\) sends a \(\langle\mathsf{Grant},\mathsf{MUTEX},P_{j}\rangle\) message to \(P_{i}\); then \(P_{i}\) sends a \(\langle\mathsf{Release},\mathsf{MUTIN},P_{i}\rangle\) message to each process in \(N_{i}\cup\{P_{i}\}\). Thus, \(3(|N_{i}|+1)\) messages are exchanged for \(P_{i}\)'s entering the CS. Thus, the message complexity is \(6(|N_{i}|+1)\) in the best case. Next, let us consider the worst case. * For \(P_{i}\)'s exiting the CS, \(P_{i}\) sends a \(\langle\mathsf{Request},\mathsf{MUTIN},ts_{i},P_{i}\rangle\) message to each process \(P_{j}\) in \(N_{i}\cup\{P_{i}\}\). Then, \(P_{j}\) sends a \(\langle\mathsf{Preempt},\mathsf{MUTIN},P_{j}\rangle\) message to the process \(P_{m}\) to which \(P_{j}\) sends a \(\langle\mathsf{Grant},\mathsf{MUTIN},P_{j}\rangle\) message; \(P_{m}\) sends a \(\langle\mathsf{Relianguish},\mathsf{MUTIN},P_{m}\rangle\) message back to \(P_{j}\); and \(P_{j}\) sends a \(\langle\mathsf{Grant},\mathsf{MUTIN},P_{j}\rangle\) message to \(P_{i}\). After \(P_{i}\) exits the CS, \(P_{i}\) sends a \(\langle\mathsf{Release},\mathsf{MUTEX},P_{i}\rangle\) message to each process \(P_{j}\) in \(N_{i}\cup\{P_{i}\}\). Then, \(P_{j}\) sends a \(\langle\mathsf{Grant},\mathsf{MUTEX},P_{j}\rangle\) message to some process with the highest priority in \(\mathit{pendingReq}_{j}[\mathsf{MUTEX}]\). Thus, \(6(|N_{i}|+1)\) messages are exchanged.