# ZenoPS: A Distributed Learning System Integrating Communication Efficiency and Security
## 3 Preliminaries
### Notations  
First, in Table 1, we define some important notations and terminologies that are used throughout this paper.  
\begin{table}
\begin{tabular}{l l} \hline \hline
**Notation/Term** & **Description** \\ \hline \(n\) & The number of workers \\ \hline \(k\) & The number of active workers \\ \hline \(T\), \(t\) & The number of iterations or server steps, and the current iteration \(t\in[T]\) \\ \hline \(t^{\prime}\) & Some previous iteration or server step, \(t^{\prime}\leq t-1\) \\ \hline \(\tau\) & Maximum delay, \(t-1-t^{\prime}\leq\tau\) \\ \hline \(H\) & The number of local iterations (worker steps), or synchronization interval \\ \hline \(h\) & The current local iteration (worker step), \(h\in[H]\) \\ \hline \(d\) & The number of model parameters, or the size of the model \\ \hline \([n]\) & The set of integers \(\{1,\ldots,n\}\) \\ \hline \(S_{t}\) & The set of randomly selected devices in the \(t^{\text{th}}\) iteration \\ \hline \(b\) & Parameter of the trimmed mean \\ \hline \(H_{min}\), \(H_{max}\) & Minimal/maximal number of local iterations \\ \hline \(H_{i,t}\) & The number of local iterations in the \(t\)th epoch on the \(i\)th device \\ \hline \(x_{t}\) & The initial model in the \(t\)th iteration \\ \hline \(x_{i,t,h}\) & Model updated in the \(t\)th server step and the \(h\)th worker step, \\  & on the \(i\)th device \\ \hline \(\mathcal{D}_{i}\) & The training dataset on the \(i\)th device \\ \hline \(\mathcal{D}\) & The entire training dataset \(\mathcal{D}=\mathcal{D}_{1}\cup\cdots\cup\mathcal{D}_{n}\) \\ \hline \(\mathcal{D}_{r}\) & The validation dataset on the validators \\ \hline \(z_{i,t,h}\) & Data (mini-batch) sampled in the \(t\)th server step and the \(h\)th worker step on the \(i\)th device \\ \hline \(\sigma^{2}\) & The variance of the stochastic gradient of a single sample \\ \hline \(f(x;z\sim\mathcal{D})\), & The stochastic function value and gradient on random sample \(z\), \\ \(\
abla f(x;z\sim\mathcal{D})\) & drawn from the dataset \(\mathcal{D}\) (sometimes we use \(f(x)\) and \(\
abla f(x)\) for short) \\ \hline \(F(x),\
abla F(x)\) & \(F(x)=\mathbb{E}[f(x)],\
abla F(x)=\mathbb{E}[\
abla f(x)]\), \\  & and the expectation is taken over the random samples \\ \hline \(\eta\) & Learning rate \\ \hline \(\alpha\), \(\rho\), \(\gamma\), etc. & Some positive constants or hyperparameters \\ \hline \(\delta\) & The approximation factor of the compressor \(\mathcal{C}\), \\  & where \(\|v-\mathcal{C}(v)\|^{2}\leq(1-\delta)\|v\|^{2}\) \\ \hline \(\|\cdot\|\) & All the norms in this paper are \(l_{2}\)-norms \\ \hline \(V_{1}\), \(V_{2}\), \(V_{3}\), etc. & Some constants defined in assumptions and used in theoretical analysis \\ \hline \(q,m\) & \(q\) is the number of Byzantine workers, \(m=n+q\) \\ \hline Device & Where the training data are placed \\ \hline Worker & The process that trains the model on the local datasets \\ \hline Byzantine worker & Worker with Byzantine failures \\ \hline Server & The process that maintains the global model parameters and \\  & exchanges information with the workers and validators \\ \hline Validator & The process that validates the updates sent from the worker and \\  & filters out the potentially malicious ones \\ \hline \hline \end{tabular}
\end{table}
Table 1: Notations and terminologies.