## 3 Proposed Algorithm for the Generalized Local \(I_{i}\)-Mutual Inclusion
The deleted element \((*,P_{q})\) is a request that \(P_{r}\) or other neighbors of \(P_{q}\) kept it waiting if the system is in a deadlock, and the inserted element \((0,P_{q})\) cannot be preempted because it has the maximum priority. We explain the technical details how the leader \(P_{LDR}\) suspects that the system is in a deadlock. When \(\mathit{Waiting}_{LDR}=|N_{LDR}|+1\), then \(|\mathit{pendingReq}_{LDR}[\mathsf{MUTIN}]|+|\mathit{pendingReq}_{LDR}[\mathsf{ MUTEX}]|+|\mathit{Grant}_{LDR}|=|N_{LDR}|+1\). Because a request is not sent if a previous one is kept waiting, two pending lists \(\mathit{pendingReq}_{LDR}[\mathsf{MUTIN}]\) and \(\mathit{pendingReq}_{LDR}[\mathsf{MUTEX}]\) are disjoint. Thus, if there is a neighbor \(P_{q}\in N_{LDR}\), which is not in these pending lists, then \(P_{q}\)'s request is granted by \(P_{LDR}\), but is kept waiting by other neighbor than \(P_{LDR}\) in the deadlock configuration. That is, \(P_{q}\)'s request is in both of _grantedTo_LDR. To the suspicion possible, we assume that, at the leader process, \((k_{LDR}-1)-(l_{LDR}+1)\geq 1\) holds, i.e., \(k_{LDR}-l_{LDR}\geq 3\). The underlying LMUTIN (resp., LMUTEX) algorithm sends at most \(|N_{LDR}|+1-(l_{LDR}+1)\) (resp., \(k_{LDR}-1\)) grants; the total number of grants of the two underlying algorithms is at most \(|N_{LDR}|-l_{LDR}+k_{LDR}-1\). Because \(k_{LDR}-l_{LDR}\geq 3\), \(|N_{LDR}|-l_{LDR}+k_{LDR}-1\geq|N_{LDR}|+2>|N_{LDR}|+1=|N_{LDR}\cup\{P_{LDR}\}|\) holds. This implies that there exists at least a process \(P_{q}\in(N_{LDR}\cup\{P_{LDR}\})\) that receives both grants of LMUTIN and LMUTEX from \(P_{LDR}\). ```
On receipt of a \(\langle\mathsf{Request},at,ts_{j},P_{j}\rangle\) message: \(\mathit{pendingReq}_{i}[at]:=\mathit{pendingReq}_{i}[at]\cup\{(ts_{j},P_{j})\}\); if\((\mathit{Cond}_{i})\{\) \((ts_{h},P_{h}):=deleteMin(\mathit{pendingReq}_{i}[at])\); \(\mathit{grantedTo}_{i}[at]:=\mathit{grantedTo}_{i}[at]\cup\{(ts_{h},P_{h})\}\); send\(\langle\mathsf{Grant},at,P_{i}\rangle\) to \(P_{h}\); } elseif\((\mathit{preemptingNow}_{i}[at]=\mathbf{nil})\{\) \((ts_{h},P_{h}):=max(\mathit{grantedTo}_{i}[at])\); if\(((ts_{j},P_{j})<(ts_{h},P_{h}))\{\) \(\mathit{preemptingNow}_{i}[at]:=(ts_{h},P_{h})\); send\(\langle\mathsf{Preempt},at,P_{i}\rangle\) to \(P_{h}\); } }
```

**On receipt of a \(\langle\mathsf{Grant},at,P_{j}\rangle\) message: if\((P_{j}\
ot\in\mathit{nGrants}_{i}[at])\{\) \(nGrants_{i}[at]:=\mathit{nGrants}_{i}[at]\cup\{P_{j}\}\); } On receipt of a \(\langle\mathsf{Release},at,P_{j}\rangle\) message: if\(((*,P_{j})=\mathit{preemptingNow}_{i}[at])\mathit{preemptingNow}_{i}[at]:= \mathbf{nil}\);  Delete\((*,P_{j})\) from \(\mathit{grantedTo}_{i}[at]\); if\((\mathit{pendingReq}_{i}[at]\
eq\emptyset)\{\) \((ts_{h},P_{h}):=deleteMin(\mathit{pendingReq}_{i}[at])\); \(\mathit{grantedTo}_{i}[at]:=\mathit{grantedTo}_{i}[at]\cup\{(ts_{h},P_{h})\}\); send\(\langle\mathsf{Grant},at,P_{i}\rangle\) to \(P_{h}\); } ```
**On receipt of a \(\langle\mathsf{Preempt},at,P_{j}\rangle\) message: if\(((at=\mathsf{MUTEX}\wedge state_{i}=\mathsf{OutCS})\vee(at=\mathsf{MUTIN}\wedge state_{i}=\mathsf{InCS}))\{\)  Delete\(P_{j}\) from \(\mathit{nGrants}_{i}[at]\); send\(\langle\mathsf{Relinquish},at,P_{i}\rangle\) to \(P_{j}\); } On receipt of a \(\langle\mathsf{Relinquish},at,P_{j}\rangle\) message: \(\mathit{preemptingNow}_{i}[at]:=\mathbf{nil}\);  Delete\((*,P_{j})\) from \(\mathit{grantedTo}_{i}[at]\), and let \((ts_{j},P_{j})\) be the deleted item; \(\mathit{pendingReq}_{i}[at]:=\mathit{pendingReq}_{i}[at]\cup\{(ts_{j},P_{j})\}\); \((ts_{h},P_{h}):=deleteMin(\mathit{pendingReq}_{i}[at])\); \(\mathit{grantedTo}_{i}[at]:=\mathit{grantedTo}_{i}[at]\cup\{(ts_{h},P_{h})\}\); send\(\langle\mathsf{Grant},at,P_{i}\rangle\) to \(P_{h}\);
```  
**Algorithm 5** Algorithm LKCS: message handlers (1). \(\bullet\) If the system is in a deadlock, \(P_{q}\) is definitely involved in the deadlock. Giving special grants by the sidetrack resolves the deadlock.