Metraipolis › archive › dc_d04dd0793bf5
Pipelining vs. Combining in Aggregation Tasks — arXiv:2610.31383
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.31383
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-23T15:23:22.442Z
- SHA-256 of the archived text
7bb4825b4c7c3103d8289cdc125660185739339c5977d9c14bc12a2c9502e0e3- Stable URL of this page
https://metraipolis.com/documento/dc_d04dd0793bf5
How to cite
Pipelining vs. Combining in Aggregation Tasks — arXiv:2610.31383 — arXiv (en), https://arxiv.org/abs/2610.31383 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d04dd0793bf5 (Metraipolis archive dc_d04dd0793bf5, sha256 7bb4825b4c7c3103d8289cdc125660185739339c5977d9c14bc12a2c9502e0e3)
BibTeX
@misc{dcd04dd0793bf5,
title = {Pipelining vs. Combining in Aggregation Tasks — arXiv:2610.31383},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.31383},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d04dd0793bf5; sha256 7bb4825b4c7c3103d8289cdc125660185739339c5977d9c14bc12a2c9502e0e3},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.31383. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the aggregation task (convergecast) in networks in the case that the values to be aggregated do not fit in a single message. We assume that every node starts with an input value, and there is an aggregation operator that is commutative, associative, and length-preserving, i.e., the result of aggregating two values has the same length as each of the input values. Since values do not fit in a message, they are transferred in a ``train'' of pipelined messages, which must be terminated whenever we want to aggregate values. The goal is to minimize the makespan time of aggregating all values. We present general lower bounds on the problem and optimal algorithms for several prevalent parallel computing architectures, including the hypercube and complete bipartite graphs, under both the splittable and unsplittable flows models. We also present an $O(\log n)$ approximation for general graphs in the unsplittable flows model. Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno). Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC) ; Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2610.31383 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-23T15:10:08.342Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).