## 4 Convex Minimization Problem
When \(F(\mathbf{x})=\max\limits_{i}\{\left\|\mathbf{x}_{i}\right\|_{1}\}\) one has \(r(\mathbf{z})=\left|\left|\mathbf{z}-B\mathbf{w}\right|\right|_{\infty}\). For clarity sake we collect the above results in Table 1.  
In the algorithm described below the norm is denoted just by \(\|\cdot\|\) (numerical experiments presented in Section 5 are conducted with all three norms). The monitoring algorithm we propose is the following. **Algorithm 4.1**: _Threshold monitoring algorithm. 1. Set \(i=0\). 2. Until end of stream. 3. Set \(\mathbf{v}_{j}=\mathbf{v}_{j}(t_{i})\), \(j=1,\ldots,n\) (i.e., remember \"initial\" values for the vectors). 4. Set \(\delta=\inf\limits_{\mathbf{z}\in Z_{f}}||\mathbf{z}-B\mathbf{w}(t_{i})||\) (for definition of \(\mathbf{w}\) see Equation \((\ref{eq:1})\))._ \begin{table}
\begin{tabular}{l l} \hline \(\boldsymbol{F(\mathbf{x})}\) & \(\boldsymbol{r(\mathbf{z})}\) \\ \hline \(\max\limits_{i}\{\left\|\mathbf{x}_{i}\right\|_{1}\}\) & \(\left|\left|\mathbf{z}-B\mathbf{w}\right|\right|_{1}\) \\ \(\max\limits_{i}\{\left\|\mathbf{x}_{i}\right\|_{2}\}\) & \(\left|\left|\mathbf{z}-B\mathbf{w}\right|\right|_{2}\) \\ \(\dfrac{\left\|\mathbf{x}\right\|_{\infty}=\max\limits_{i}\{\left\|\mathbf{x}_{i} \right\|_{\infty}\}}{\left\|\mathbf{z}-B\mathbf{w}\right\|_{\infty}}\) \\ \hline \end{tabular}
\end{table} 
Table 1: norm–ball radius correspondence for three different norms and fixed \(\mathbf{w}\in\mathbf{R}^{nd}\). _Algorithms_ **2012**, \(5\) _Set_ \(i=i+1\)_._
* _If_ \(\left\|\mathbf{v}_{j}-\mathbf{v}_{j}(t_{i})\right\|<\delta\) _for each_ \(j=1,\ldots,n\) _go to step 5 else_ _go to step 3_  
In what follows, we assume that transmission of a double precision real number amounts to broadcasting one message. The message computation is based on the assumption that all nodes are updated by a new text simultaneously. When mean update is required, a coordinator (root) requests and receives messages from the nodes. We next count a number of messages that should be broadcast per one iteration if the local constraint \(\delta\) is violated at least at one node. We shall denote the set of all nodes by \(\mathbf{N}\), the set of nodes complying with the constraint by \(\mathbf{N}^{C}\), and the set of nodes violating the constraint by \(\mathbf{N}^{V}\) (so that \(\mathbf{N}=\mathbf{N}^{C}\bigcup\mathbf{N}^{V}\)). The cardinality of the sets is denoted by \(\left|\mathbf{N}\right|\), \(\left|\mathbf{N}^{C}\right|\), and \(\left|\mathbf{N}^{V}\right|\) respectively, so that \(\left|\mathbf{N}\right|=\left|\mathbf{N}^{C}\right|+\left|\mathbf{N}^{V}\right|\). Assuming \(\left|\mathbf{N}^{V}\right|>0\) one has the following:  
1. \(\left|\mathbf{N}^{V}\right|\) nodes violators transmit their scalar ID and new coordinates to the root (\((d+1)\times\left|\mathbf{N}^{V}\right|\) messages). 2. the root sends scalar requests for new coordinates to the complying \(\mathbf{N}^{C}\) nodes (\(\left|\mathbf{N}^{C}\right|\) messages). 3. the \(\left|\mathbf{N}^{C}\right|\) complying nodes transmit new coordinates to the root (\(d\times\left|\mathbf{N}^{C}\right|\) messages). 4. root updates itself, computes new distance \(\delta\) to the surface, and sends \(\delta\) to each node (\(\left|\mathbf{N}\right|\) messages). This leads to total of  
\[(d+2)|\mathbf{N}|\text{ messages per mean update.} \tag{14}\]  
We conclude the section with three remarks. The first one compares conservatism of Algorithm 4.1 and the one suggested in [8]. The second one again compares the ball cover suggested in [8] and application of Algorithm 4.1 with \(l_{1}\) norm. The last one shows by an example that Equation (8) fails when \(B_{2}\) is substituted by \(B_{1}\). Significance of this negative result becomes clear in Section 5. **Remark 4.1**: _Let \(\mathbf{v}=\dfrac{1}{n}\sum_{j=1}^{n}\mathbf{v}_{j}\), and \(\mathbf{u}_{j}=\mathbf{v}+\left[\mathbf{v}_{j}(t_{i})-\mathbf{v}_{j}\right]\).