Distributed consensus and optimization under communication delays

Abstract

We study the effects of communication delays in distributed consensus and optimization algorithms. We propose two ways to model delays. First, assuming each edge of a communication network has a fixed delay, we characterize the consensus value exactly as a function of the delays and edge weights and obtain convergence rate bounds using results from non-reversible Markov chains. Second, we propose a novel way to model random delays per edge. Our model allows the reception of multiple delayed messages from the same sender in the same time slot, a situation that can happen in practice. Both models admit a description of the consensus updates in the presence of delays via linear equations. Finally, we briefly discuss how to apply our delay models to analyze distributed optimization algorithms in the presence of delayed information.