Paper details

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

CODECHECK details

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

Loading citation…
Copied!