Straggler-Resilient Asynchronous ADMM for Distributed Consensus Optimization

For its simplicity, well-established convergence properties, and applicability to various optimization problems, the alternating direction method of multipliers (ADMM) has been widely used in several fields. However, when applied in distributed systems, the method may encounter the challenges of stragglers (nodes with significantly longer response time than others) and single points of failure (a single node causing the failure of the entire system). To address these problems, we propose three straggler-resilient ADMM algorithms. The first one is a centralized straggler-resilient ADMM algorithm achieving straggler-resilience by allowing the nodes to proceed to the next iteration even when one or more nodes have not provided an update for one or more iterations. The second one is an extension of the first one achieving single-point-of-failure resilience and fast convergence through decentralized, asynchronous, and concurrent operations. The third one is an extension of the second one to also achieve robustness against uncertainties with the help of a time-tracking scheme. Through theoretical analyses, we establish the convergence properties of our algorithms and show that our algorithms achieve a computational complexity of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal{O}(1)$</tex-math></inline-formula> for each worker node - excluding the central node in the centralized algorithm, where the workload complexity is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal{O}(N)$</tex-math></inline-formula>. By numerical simulations with various settings, we show that our algorithms have converged significantly faster than several state-of-the-art ADMM algorithms with well-established convergence properties.