2026-07-24T03:34:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11750 2024-03-06T10:48:37Z ddc:004 open_access

Computation-Aware Data Aggregation Haeupler, Bernhard Hershkowitz, D. Ellis Kahng, Anson Procaccia, Ariel D. Data aggregation distributed algorithm scheduling approximation algorithms Data aggregation is a fundamental primitive in distributed computing wherein a network computes a function of every nodes' input. However, while compute time is non-negligible in modern systems, standard models of distributed computing do not take compute time into account. Rather, most distributed models of computation only explicitly consider communication time. In this paper, we introduce a model of distributed computation that considers both computation and communication so as to give a theoretical treatment of data aggregation. We study both the structure of and how to compute the fastest data aggregation schedule in this model. As our first result, we give a polynomial-time algorithm that computes the optimal schedule when the input network is a complete graph. Moreover, since one may want to aggregate data over a pre-existing network, we also study data aggregation scheduling on arbitrary graphs. We demonstrate that this problem on arbitrary graphs is hard to approximate within a multiplicative 1.5 factor. Finally, we give an O(log n ⋅ log(OPT/t_m))-approximation algorithm for this problem on arbitrary graphs, where n is the number of nodes and OPT is the length of the optimal schedule. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bernhard Haeupler and D. Ellis Hershkowitz and Anson Kahng and Ariel D. Procaccia 2020 Is Part Of LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2020.65 urn:nbn:de:0030-drops-117506 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.65 eng https://creativecommons.org/licenses/by/3.0/legalcode