# QuoTa: An Online Quality-Aware Incentive Mechanism for Fast Federated Learning
## 3 System Model and Problem Formulation
### Computing Capability Model  
In consideration of high computing capability of the server, the model convergence time usually depends on the data owner with the lowest computing capability in the FL system. In order to quantify each data owner's training speed, computing capability \(C_{i}\) is defined as the estimated CPU frequency \(f_{i}\) divided by the data amount \(d_{i}\) in Formula (1):  
\[C_{i}=\frac{f_{i}}{d_{i}}. \tag{1}\]  
In order to ensure acceptable convergence time of the FL system, we restrict data owners with slower training speeds from participating in model training. Specifically, we set a computing capability threshold below which data owners will not be selected, in order to prevent them from slowing down model convergence time. Assuming that most data owners in the FL system have fair computing capability, the threshold can be set by a heuristic approach. For example, we sort all data owners' computing capability values in the decreasing order then take the \(k\)-th value in the sequence as the threshold: \(C_{low}\).  
The real CPU frequency for model training may fluctuate in a long period due to several factors, which cannot usually reach the claimed rated value. The possible reason is a too high CPU temperature or other concurrent program process. Thus, how to predict the real CPU frequency is one important problem. In consideration of low privacy sensitivity of CPU frequency, in this paper, a CPU cycle meter is implanted on each data owner's device, in order to detect their real required number of CPU cycle for training one local data sample [7], which is denoted as \(cycle_{i}\). Thus, the required training time for all local training data are represented as \(T\_loc_{i}=(cycle_{i}*d_{i})/\hat{f_{i}}\), where \(d_{i}\) is local data volume, and \(\hat{f_{i}}\) is their actual CPU frequency. Thus, once the data owner \(i\) completes model training at round \(t\), the least number of CPU cycles \(cycle_{i}^{t}\) and local training time \(T^{t}\_loc_{i}\) at round \(t\) can be measured. Then, their real CPU frequency at this round is computed as:  
\[\hat{f_{i}}^{t}=\frac{cycle_{i}^{t}*d_{i}}{T^{t}\_loc_{i}}. \tag{2}\]  
However, according to the above Equation (2), we can only compute the value \(\hat{f_{i}}^{t}\) until the round \(t\) ends, which cannot thus be predicted in advance. Consequently, we first use the average CPU frequency \(\hat{f_{i}}^{t}\) in the previous \(t\) rounds to reflect the expected CPU frequency after the round \(t\) ends. Thus, the estimated CPU frequency \(f_{i}^{t}\) at round \(t\) is computed as:  
\[f_{i}^{t}=\hat{f_{i}}^{t}=\frac{\sum_{\tau=0}^{t}\hat{f_{i}^{\tau}}*x_{i}^{\tau }}{n_{i}^{t}} \tag{3}\]  
\[n_{i}^{t}=\sum_{\tau=0}^{t}x_{i}^{t}, \tag{4}\]  
where \(n_{i}^{t}\) represents the number of times the data owner \(i\) was selected in the previous \(t\) rounds. By exploiting the above expected CPU frequency, we measure each data owner's computing capability as an important indicator of data owner selection in order to achieve faster model convergence. Although the claimed CPU frequency in bidding information is no longer used for a selection indicator once the real CPU frequency is computed after several rounds, it plays a part in winner selection at first. More details will be shown in Section 4.2.