Title: Optimal Graph Stretching for Distributed Averaging
Authors: Florine W. Dekker , Zekeriya Erkin , Mauro Conti
Abstract: Obtained from OpenAlex
The performance of distributed averaging depends heavily on the underlying topology. In various fields, including compressed sensing, multi-party computation, and abstract graph theory, graphs may be expected to be free of short cycles, i.e. to have high girth. Though extensive analyses and heuristics exist for optimising the performance of distributed averaging in general networks, these studies do not consider girth. As such, it is not clear what happens to convergence time when a graph is stretched to a higher girth. In this work, we introduce the optimal graph stretching problem, wherein we are interested in finding the set of edges for a particular graph that ensures optimal convergence time under constraint of a minimal girth. We compare various methods for choosing which edges to remove, and use various convergence heuristics to speed up the searching process. We generate many graphs with varying parameters, stretch and optimise them, and measure the duration of distributed averaging. We find that stretching by itself significantly increases convergence time. This decrease can be counteracted with a subsequent repair phase, guided by a convergence time heuristic. Existing heuristics are capable, but may be suboptimal.
Work publication date: 2025-04-14
OpenAlex: https://openalex.org/W6912142737
Certificate identifier: 2025-003
Codechecker names: Aysun Urhan , Yasel Quintero
Time of check: 2025-03-25
Repository: https://github.com/codecheckers/certificate-2025-003
Full certificate: https://doi.org/10.5281/zenodo.15333601
Certificate on Wikidata: Q141269704
Type: institution
Venue: TU Delft DCC
Summary:
All figures in the manuscript were successfully reproduced, with the process requiring both an HPC cluster and a valid MATLAB license.
Cite this certificate: Citation metadata retrieved from data.crosscite.org