$i$.

Several such decentralized protocols exist. For example, each node may assign $$\begin{aligned}
 a_{ij}{(k)} & = & \epsilon, \qquad\qquad \mbox{ \ \ if
} (j,i)
\in \Eb(k) {\mbox{ and } i\neq j,} \\
a_{ii}{(k)} & = & 1 - \epsilon\cdot \mbox{deg}(i),\end{aligned}$$ where [deg]{}($i$) is the degree of $i$ in $\Gb(k)$. If $\epsilon$ is small enough and the graph $\Gb(k)$ is undirected [\[i.e., $(i,j)\in\Eb(k)$ if and only if $(j,i)\in\Eb(k)$\],]{} this results in a nonnegative, doubly stochastic matrix (see [@OSM04]). However, [if a node has $\ao{\Theta}(n)$ neighbors, $\eta$ will be of order $\ao{\Theta}(1/n)$, resulting in $\ao{\Theta}(n^3)$ convergence time.]{} Moreover, this argument applies to all protocols in which nodes assign equal weights to all their neighbors; see [@XB04] and [@BFT05] for more examples.

In this section, we examine whether it is possible to synthesize the weights $a_{ij}(k)$ in a decentralized manner, so that $a_{ij}(k)\geq \eta$ whenever $a_{ij}(k)\neq 0$, where $\eta$ is a positive constant independent of $n$ and $B$. We show that this is indeed possible, under the additional assumption that the graphs $\Gb(k)$ are undirected. Our algorithm is data-dependent, in that $a_{ij}(k)$ depends not only on the graph $\Gb(k)$, but also on the data vector $x(k)$. Furthermore, it is a decentralized 3-hop 