# QuoTa: An Online Quality-Aware Incentive Mechanism for Fast Federated Learning
## 4 Design of QuoTa
### Data Owner Selection and Payment  
As mentioned above, when making data owner selection, we should fully consider the possible existence of malicious data owners in the system, as well as the problem of CPUfrequency fluctuations in reality. In each communication round, we will first conduct model quality detection on the uploaded local model, update each data owner's reputation value based on quality detection value, and further punish data owners with poor performance. In addition, we then update each data owner's estimated CPU frequency in the next round according to the UCB algorithm. Combined with the above two components, we design an efficient data owner selection algorithm to achieve a better global model accuracy with less model training time. First, we reformulate our optimization problem as follows:  
max \[\sum_{i=1}^{n}(d_{i}^{t}*Rep_{i}^{t-1})*x_{i}^{t}\] (16) s.t. \[(5a)(5b)\] (16a) \[Rep_{i}^{t-1}*x_{i}^{t}\geq Rep_{low},\forall i\in\mathcal{N}\] (16b) \[\tilde{C}_{i}^{t}*x_{i}^{t}\geq\tilde{C}_{low},\forall i\in \mathcal{N}\] (16c)  
where we use \(d_{i}^{t}*Rep_{i}^{t-1}\) to replace the previous objective function \(d_{i}^{t}\) in formula (5), and \(Rep_{i}^{t-1}\) is a weighted factor. In (16b), for data owners with too low reputation values, we will restrict their participation in model training by setting a threshold \(Rep_{low}\) (we adopt a similar heuristic approach to determine \(Rep_{low}\) with \(C_{low}\) in Section 3.3). By (16c), we use the computing capability value estimated by the UCB algorithm to limit the data owner with low computing capability. As is similar to the problem reformulation (6) in Section 3.4, the server selects winning data owners that guarantee both global model accuracy and convergence time within the limited budget as follows:  
min \[\sum_{i=1}^{n}x_{i}^{t}\] (17) s.t. \[(5a)(5b)(16b)(16c)\] (17a) \[\sum_{i=1}^{n}(d_{i}^{t}*Rep_{i}^{t-1})*x_{i}^{t}\geq Q_{i}^{t}\] (17b)  
where the constraint (17b) sets the threshold value \(Q_{i}^{t}\) as the lower upper of the objective function (16). We get the optimal data owner selection scheme by solving the above optimization problem according to the OPT tool. Algorithm 1 describes the running process of the QuoTa mechanism. In each round of communication, the platform server first computes the optimal data owner set to participate in model training by the objective functions (16) and (17). After receiving the local model parameter uploaded by each winner \(i\in\mathcal{S}^{t}\), the server first performs model quality detection to compute their quality detection value \(v_{i}^{t}\) and then calculates their direct reputation value \(rep_{i}^{t}\) based on \(v_{i}^{t}\). After that, their comprehensive reputation value \(Rep_{i}^{t}\) is updated by their direct reputation and selection according to line 9-11 before round \(t\) ends. In addition, the server predicts each data owner's computing capability \(\tilde{C}_{i}^{t}\) based on their average CPU frequency \(\tilde{T}_{i}^{t}\) by online exploration-exploitation algorithm in lines 13-15. After that, the global model parameter is aggregated by line 16. Moreover, each data owner is paid a critical payment, \(p_{i}\)[24]. For each winning data owner \(i\in\mathcal{S}^{t}\), the server first excludes them from the whole candidate data owners \(\mathcal{N}\), then tries to find an alternative one \(i^{*}\) based on \(\mathcal{N}^{{}^{\prime}}\), and finally uses the claimed cost of \(i^{*}\) to make a critical payment to them. ```
Input: Budget \(B^{t}\) at each round \(t\), set of candidate data owners \(\mathcal{N}\), each data owner's bid profile \(\mathcal{B}_{i}=\{b_{i},d_{i},fre_{i}\}\), initially estimated CPU frequency \(\tilde{f}_{i}^{0}\), initial comprehensive reputation value \(Rep_{i}^{0}\), initial global model \(w^{0}\). Output: Set \(\mathbf{S}=\{\mathcal{S}^{1},\mathcal{S}^{2},\ldots\}\) of selected data owners at each round, their payment vector \(\mathbf{p}\).