rather than the stronger Assumption 2. Later on, in Section \[matrixpicking\], we will exploit the sufficiency of Assumption \[weakconnect\] to [design]{} a decentralized algorithm for selecting the weights $a_{ij}(k)$, which satisfies Assumption \[weakconnect\], but not Assumption 2.

We now proceed to bound the decrease of our Lyapunov function $V(x(k))$ during the interval $[kB, (k+1) B-1]$. In what follows, we denote by $V(k)$ the sample variance $V(x(k))$ at time $k$.

\[vardiff\] Let Assumptions \[weights\] and \[weakconnect\] hold. Let $\{x(k)\}$ be generated by the update rule (\[noquant\]). Suppose that the components $x_i(kB)$ of the vector $x(kB)$ have been ordered from largest to smallest, with ties broken arbitrarily. Then, we have $$V(kB) - V((k+1)B) \geq
\frac{\eta}{2} \sum_{i=1}^{n-1} (x_{i}(kB) - x_{i+1}(kB))^2.$$

By Lemma \[vl\], we have for all $t$, $$V(t)-V(t+1) = \sum_{i<j} w_{ij}(t)
(x_i(t)-x_j(t))^2, \label{firstvdec0}$$ where $w_{ij}(t)$ is the $(i,j)$-th entry of $A(t)^T A(t)$. Summing up the variance differences $V(t)-V(t+1)$ over different values of $t$, we obtain $$V(kB) - V((k+1)B)
= \sum_{t=kB}^{(k+1)B-1} \sum_{i<j}
w_{ij}(t) (x_i(t)-x_j(t))^2. \label{firstvdec}$$

-   For all $d\in\{1,\ldots,n-1\}$, let $t_d$ be the first time larger than or equal to $kB$ (if it exists) at which there is a communication between two nodes belonging to the two sets $\{1,\ldots,d\}$ and $\{d+1,\ldots,n\}$, to be 