# Pipelining vs. Combining in Aggregation Tasks

DevFeed: [Pipelining vs. Combining in Aggregation Tasks](<https://devfeed.tech/articles/pipelining-vs-combining-in-aggregation-tasks-97312.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2610.31383>)

Author: Gabriel Marques Domingues, Claire Mathieu, Boaz Patt-Shamir

Published: 2026-10-23T04:00:00Z

Content type: article

Language: en

Sources: [arXiv: Distributed Computing](<https://devfeed.tech/sources/arxiv-distributed-computing.md>)

Topics: [To-Do](<https://devfeed.tech/topics/todo.md>)

Tags: [abstract](<https://devfeed.tech/tags/abstract.md>), [aggregate](<https://devfeed.tech/tags/aggregate.md>), [aggregation](<https://devfeed.tech/tags/aggregation.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [all](<https://devfeed.tech/tags/all.md>), [also](<https://devfeed.tech/tags/also.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [architectures](<https://devfeed.tech/tags/architectures.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [bipartite-graphs](<https://devfeed.tech/tags/bipartite-graphs.md>), [complete](<https://devfeed.tech/tags/complete.md>), [computing](<https://devfeed.tech/tags/computing.md>), [cs-dc](<https://devfeed.tech/tags/cs-dc.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [general](<https://devfeed.tech/tags/general.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [hypercube](<https://devfeed.tech/tags/hypercube.md>), [input](<https://devfeed.tech/tags/input.md>), [lower-bounds](<https://devfeed.tech/tags/lower-bounds.md>), [pipelining](<https://devfeed.tech/tags/pipelining.md>), [tasks](<https://devfeed.tech/tags/tasks.md>), [vs](<https://devfeed.tech/tags/vs.md>)

## AI overview

The paper studies convergecast when each node's value is larger than one message and aggregation is commutative, associative, and length-preserving. Values travel in pipelined message trains, which must be stopped to combine them; the objective is to minimize total completion time. It gives general lower bounds, optimal algorithms for hypercubes and complete bipartite graphs under both splittable and unsplittable flow models, and an O(log n) approximation for general graphs in the unsplittable model. The supplied excerpt does not describe the algorithms or lower-bound formulas.

## Source excerpt

arXiv:2610.31383v1 Announce Type: new Abstract: 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.