Geodesic
Average-Case Optimization Analysis for Distributed Consensus Algorithms on Regular Graphs
Russian journal of nonlinear dynamics, Tome 20 (2024) no. 5, pp. 907-931

Voir la notice de l'article provenant de la source Math-Net.Ru

The consensus problem in distributed computing involves a network of agents aiming to compute the average of their initial vectors through local communication, represented by an undirected graph. This paper focuses on studying this problem using an average-case analysis approach, particularly over regular graphs. Traditional algorithms for solving the consensus problem often rely on worst-case performance evaluation scenarios, which may not reflect typical performance in real-world applications. Instead, we apply average-case analysis, focusing on the expected spectral distribution of eigenvalues to obtain a more realistic view of performance. Key contributions include deriving the optimal method for consensus on regular graphs, showing its relation to the Heavy Ball method, analyzing its asymptotic convergence rate, and comparing it to various first-order methods through numerical experiments.
Keywords: consensus problem, average-case analysis, regular graph 
@article{ND_2024_20_5_a12,
     author = {N. T. Nguyen and A. V. Rogozin and A. V. Gasnikov},
     title = {Average-Case {Optimization} {Analysis} for {Distributed} {Consensus} {Algorithms} on {Regular} {Graphs}},
     journal = {Russian journal of nonlinear dynamics},
     pages = {907--931},
     publisher = {mathdoc},
     volume = {20},
     number = {5},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ND_2024_20_5_a12/}
}
TY  - JOUR
AU  - N. T. Nguyen
AU  - A. V. Rogozin
AU  - A. V. Gasnikov
TI  - Average-Case Optimization Analysis for Distributed Consensus Algorithms on Regular Graphs
JO  - Russian journal of nonlinear dynamics
PY  - 2024
SP  - 907
EP  - 931
VL  - 20
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ND_2024_20_5_a12/
LA  - en
ID  - ND_2024_20_5_a12
ER  - 
%0 Journal Article
%A N. T. Nguyen
%A A. V. Rogozin
%A A. V. Gasnikov
%T Average-Case Optimization Analysis for Distributed Consensus Algorithms on Regular Graphs
%J Russian journal of nonlinear dynamics
%D 2024
%P 907-931
%V 20
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ND_2024_20_5_a12/
%G en
%F ND_2024_20_5_a12
N. T. Nguyen; A. V. Rogozin; A. V. Gasnikov. Average-Case Optimization Analysis for Distributed Consensus Algorithms on Regular Graphs. Russian journal of nonlinear dynamics, Tome 20 (2024) no. 5, pp. 907-931. http://geodesic.mathdoc.fr/item/ND_2024_20_5_a12/