  Distributed linear algebraic equation over networks, where nodes hold a part
of problem data and cooperatively solve the equation via node-to-node
communications, is a basic distributed computation task receiving an increasing
research attention. Communications over a network have a stochastic nature,
with both temporal and spatial dependence due to link failures, packet dropouts
or node recreation, etc. In this paper, we study the convergence and
convergence rate of distributed linear equation protocols over a $\ast$-mixing
random network, where the temporal and spatial dependencies between the
node-to-node communications are allowed. When the network linear equation
admits exact solutions, we prove the mean-squared exponential convergence rate
of the distributed projection consensus algorithm, while the lower and upper
bound estimations of the convergence rate are also given for independent and
identically distributed (i.i.d.) random graphs. Motivated by the randomized
Kaczmarz algorithm, we also propose a distributed randomized projection
consensus algorithm, where each node randomly selects one row of local linear
equations for projection per iteration, and establish an exponential
convergence rate. When the network linear equation admits no exact solution, we
prove that a distributed gradient-descent-like algorithm with diminishing
step-sizes can drive all nodes' states to a least-squares solution at a
sublinear rate. These results collectively illustrate that distributed
computations may overcome communication correlations if the prototype
algorithms enjoy certain contractive properties or are designed with suitable
parameters.
