  The paper addresses large-scale, convex optimization problems that need to be
solved in a distributed way by agents communicating according to a random
time-varying graph. Specifically, the goal of the network is to minimize the
sum of local costs, while satisfying local and coupling constraints. Agents
communicate according to a time-varying model in which edges of an underlying
connected graph are active at each iteration with certain non-uniform
probabilities. By relying on a primal decomposition scheme applied to an
equivalent problem reformulation, we propose a novel distributed algorithm in
which agents negotiate a local allocation of the total resource only with
neighbors with active communication links. The algorithm is studied as a
subgradient method with block-wise updates, in which blocks correspond to the
graph edges that are active at each iteration. Thanks to this analysis
approach, we show almost sure convergence to the optimal cost of the original
problem and almost sure asymptotic primal recovery without resorting to
averaging mechanisms typically employed in dual decomposition schemes. Explicit
sublinear convergence rates are provided under the assumption of diminishing
and constant step-sizes. Finally, an extensive numerical study on a plug-in
electric vehicle charging problem corroborates the theoretical results.
