## 4 The DecantFed Algorithm
### Client Clustering and Bandwidth Allocation  
Assume that each client trains only the minimum number of samples \(D_{i}^{min}\) from its local dataset, i.e., for all \(i\) in \(\mathbf{\mathcal{I}}\), \(d_{i}=D^{min}\), then \(\mathbf{P0}\) can be transformed into the following. \[\mathbf{P1}: \operatorname*{arg\,max}_{\mathbf{x},\mathbf{b}}\sum_{i\in\mathbf{\mathcal{ I}}}\sum_{j\in\mathbf{\mathcal{J}}}w_{j}x_{ij}, \tag{10}\] \[\text{s.t.}\quad\text{Constraints (\ref{eq:D1}), (\ref{eq:D2}), and (\ref{eq:D3}).}\]  
Solving \(\mathbf{P1}\) remains challenging due to the unknown waiting time \(t_{ij}^{wait}\) specified in (5), which becomes known only after clients have been grouped into tiers. However, for optimizing the objective function in \(\mathbf{P1}\), it is preferable to assign clients to lower tiers that have a larger \(w_{j}\), while still meeting the tier's deadline constraints as outlined Constraint (5). Motivated by this insight for solving \(\mathbf{P1}\), we design the heuristic LEAD algorithm (joint client clustEring and bAnDwidth allocation), summarized in Algorithm 1. Specifically,  
1. Each client's uploading time is determined by its tier. Additionally, tier bandwidth is determined by the number of clients in the corresponding tier, i.e., \(b_{j}=\frac{\sum\limits_{i\in\mathbf{\mathcal{I}}}x_{ij}}{|\mathbf{\mathcal{I}}|}\times B\). Then, \[t_{ij}^{upload}=\frac{|\mathbf{\mathcal{I}}|}{B}\frac{|\mathbf{\mathcal{I}}|}{\sum \limits_{i\in\mathbf{\mathcal{I}}}x_{ij}}\frac{s}{\log_{2}\Bigl{(}1+\frac{\mu_{i} \otimes\mu}{N_{0}}\Bigr{)}}.\] (11)
2. In the \(j^{th}\) iteration, we intend to assign as many clients as possible to the \(j^{th}\) tier, while satisfying Constraint (5). Let \(\mathbf{\tilde{\mathcal{I}}}\) denote the set of clients who have not been clustered into any tier yet, i.e., \(\mathbf{\tilde{\mathcal{I}}}=\left\{\forall i\ \in\mathbf{\mathcal{I}}\Bigl{|}\sum_{j\in\mathbf{\mathcal{J}}}x_{ij}=0\right\}\). We sort the clients in \(\mathbf{\tilde{\mathcal{I}}}\) in descending order based on their computing latency. Let \(\mathbf{\mathcal{I}}_{j}\) denote the set of these sorted clients, i.e., \(\mathbf{\mathcal{I}}_{j}=\left\{\forall i^{\prime}\in\mathbf{\mathcal{I}}\Bigl{|}t_{i ^{\prime}+1}^{comp}\leq t_{i^{\prime}}^{comp}\right\}\), where \(i^{\prime}\) is the index of the clients in \(\mathbf{\mathcal{I}}_{j}\). Assume that all the clients in \(\mathbf{\mathcal{I}}_{j}\) can be assigned in tier \(j\), i.e., \(\forall i^{\prime}\in\mathbf{\mathcal{I}}_{j}\), \(x_{ij}=1\). We then iteratively check the feasibility of all the clients in tier \(j\) starting from the first client, i.e., whether each client in tier \(j\) can really be assigned to tier \(j\) to meet Constraint (5) or not. If a client currently in tier \(j\) cannot meet Constraint (5), this client will be removed from tier \(j\), i.e., \(x_{i^{\prime}j}=0\). Note that removing a client reduces the bandwidth \(b_{j}\) allocated to tier \(j\) in Step 13, which may lead to the clients, who were previously feasible to be assigned to tier \(j\) to meet Constraint (5), no longer feasible because of the decreasing of \(b_{j}\). As a result, we have to go back and check the feasibility of all the clients in tier \(j\) starting from the first client again, i.e., \(i^{\prime}=1\) in Step 14. 3. Once the client clustering in tier \(j\) is finished, we start to assign clients to tier \(j+1\) by following the same procedure in Steps 5-19. The client clustering ends when all clients have been assigned to the existing tiers, i.e., \(\mathbf{\tilde{\mathcal{I}}}\
eq\emptyset\). ```
1\(\forall i\in\mathbf{\mathcal{I}},d_{i}=D_{i}^{min}\), calculate \(t_{i}^{comp}\) based on Equation (2). 2\(\forall i\in\mathbf{\mathcal{I}},\forall j\in\mathbf{\mathcal{J}}\), initialize \(x_{ij}=0\). 3 Initialize \(j=1\) and \(\mathbf{\tilde{\mathcal{I}}}:=\mathbf{\mathcal{I}}\).