# ZenoPS: A Distributed Learning System Integrating Communication Efficiency and Security
## 3 Preliminaries
### Byzantine Failures  
Byzantine failure, first introduced in [22], is a well-studied problem in the field of distributed systems. In general, Byzantine failures assume a threat model where the failed agents behave arbitrarily in a traditional distributed system. Such a threat model assumes the worse cases of failures and attacks in the distributed systems. Many failures and attacks can be viewed as special cases of Byzantine failures. For example, the authors of [44] describe the vulnerability to bit-flipping attacks in the wireless transmission technology, where the servers can receive data via such vulnerable communication media, even if the messages are encrypted. As a result, an arbitrary fraction of the received values are corrupted. Furthermore, federated learning can be vulnerable to  
Figure 1: Parameter-server architecture. data poisoning attacks, where the users feed compromised or fabricated data such as fake reviews [45] to the learning systems. A recent work [46] argues that data poisoning attacks are equivalent to Byzantine failures under certain assumptions. The authors of [47] introduced Byzantine failures to distributed synchronous SGD, with some modifications to make the threat model fit the machine-learning scenario, in which the Byzantine failures only happen on the worker nodes. In summary, workers with Byzantine failures send arbitrary messages to other processes. We define the threat model as follows. **Definition 1** (Threat Model). : _Additional to the \(n\) honest workers, there are \(q\) Byzantine workers that send out arbitrary messages during communication. Furthermore, we assume that the workers are anonymous to the other processes._  
The existence of Byzantine workers prevents the distributed SGD from converging or decreasing the loss value on the training data. We formally define the Byzantine failures for synchronous training and asynchronous training as follows. **Definition 2** (Threat model for synchronous SGD). : _We assume that there are \(n\) honest workers and \(q\) Byzantine workers. When the server receives a gradient estimator \(\tilde{g}_{i,t}\) from the \(i\)th worker in the \(t\)th iteration, it is either correct or Byzantine. If sent by a Byzantine worker, \(\tilde{g}_{i,t}\) is assigned arbitrary values. If sent by an honest worker, the correct gradient is \(\
abla f(x_{t-1};z_{i,t}),\forall i\in[n],t\in[T]\). Thus, we have_  
\[\tilde{g}_{i,t}= \begin{cases}\text{arbitrary value},&\text{if worker $i$ is Byzantine, i.e., $i\in[n+1,n+q]$},\\ g_{i,t}=\
abla f(x_{t-1};z_{i,t}\sim\mathcal{D}_{i}),&\text{otherwise, i.e., $i\in[n]$}.\end{cases} \]  
**Definition 3** (Threat model for asynchronous SGD). : _We assume that there are \(n\) honest workers and \(q\) Byzantine workers. When the server receives a gradient estimator \(\tilde{g}_{t}\) from the \(i\)th worker in the \(t\)th iteration, it is either correct or Byzantine. If sent by a Byzantine worker, \(\tilde{g}_{t}\) is assigned arbitrary values. If sent by an honest worker, the correct gradient is \(\
abla f(x_{t^{\prime}};z_{i,t^{\prime}}),\forall i\in[n],t^{\prime}\leq t-1\). Thus, we have_  
\[\tilde{g}_{t}= \begin{cases}\text{arbitrary value},&\text{if worker $i$ is Byzantine, i.e., $i\in[n+1,n+q]$},\\ g_{t}=\
abla f(x_{t^{\prime}};z_{i,t^{\prime}}\sim\mathcal{D}_{i},t^{\prime} \leq t-1),&\text{otherwise, i.e., $i\in[n]$}.\end{cases} \]  
Based on the definition of Byzantine failures above, we formally define the general Byzantine tolerance for both synchronous and asynchronous SGD in the IID settings. **Definition 4** (SGD Byzantine Tolerance). : _Without a loss of generality, suppose that, in any iteration \(t\) on the server, the global model parameters are updated by \(x_{t}=x_{t-1}-yu_{t}\), where \(u_{t}\) is the update vector (gradient estimator) produced by different approaches.