REVIEW 3 major objections 3 minor 25 references
Non-Splitting Coflow Scheduling with Provable Guarantees in Heterogeneous Parallel Networks
T0 review · 3 major / 3 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read Randomized rounding of an interval-indexed LP relaxation yields a $1.5+\epsilon$ approximation for coflow makespan on heterogeneous parallel networks, improving the previous $2+\epsilon$ bound.
desk verdict The claimed 1.5-approximation is not established; the paper analyzes a t-priority schedule that the algorithm never runs, and a simple 2x2 instance refutes the central theorem. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing mechanism is a two-part construction. First, an interval-indexed LP relaxation (5) is solved; its variables $y_{ijkp\ell}$ encode, for the interval $\ell$, the fraction of flow $(i,j,k)$ that will be sent over network core $p$, with capacity constraints per port and per interval, and with completion-time lower bounds $C_{ijk}$ defined through the functions $f(i,j,k,p,\ell)$. Second, randomized rounding assigns each flow to a switch-interval pair $(p,\ell)$ with probability $s_p y_{ijkp\ell}|I_\ell|/d_{ijk}$, after which all flows assigned to core $p$ are aggregated into one demand matrix $D_p$ and transmitted by Birkhoff–von Neumann decomposition (Algorithm 1). The named identity doing the work is the Birkhoff–von Neumann theorem: every doubly stochastic matrix is a convex combination of permutation matrices, so the augmented demand matrix $\tilde D_p/\rho(D_p)$ becomes a weighted list of perfect matchings, each executed for one time slot; the schedule length on core $p$ is exactly the port load $\rho(D_p)$. The $1.5$ factor emerges because the expected completion time of the last flow is bounded by $(t+\frac12)$ plus half its transmission time, which matches the LP's lower-bound expression.
What would settle it
Run Algorithm 2 on a small heterogeneous instance, enumerate all outcomes of the random switch-time assignments, and compare $\mathbb{E}[\max_p \rho(D_p)]$, the expected makespan of the actual Birkhoff–von Neumann schedule (which on core $p$ is exactly the port load $\rho(D_p)$), against $1.5\,C^*_{\max}$ from the LP; any instance where the former exceeds the latter would refute Theorem 4.2 for the algorithm as written.
Extended reading notes
Core claim
The paper's central claim is that the makespan of preemptive coflow scheduling in heterogeneous parallel networks can be approximated within a factor of $1.5$ by a randomized rounding of the LP relaxation, and that exponential interval indexing reduces this to a polynomial-time $1.5+\epsilon$ randomized algorithm; derandomization by conditional expectations gives deterministic algorithms with ratios $1.5+\frac{1}{2\cdot LB}$ and $1.5+\frac{1}{2\cdot LB}+\epsilon$, with the $\epsilon$ term disappearing when the minimum flow is at least $(1-\eta)/\eta$. The prior best known bound was $2+\epsilon$. The construction assigns every flow to a switch-time pair according to the LP solution, bundles the flows on each core into a single demand matrix, and uses Birkhoff–von Neumann decomposition to transmit that matrix in a number of time slots equal to its maximum port load; the proof then bounds the expected completion time of the final flow by $1.5$ times the LP optimum.
Load-bearing premise
Everything rests on treating the makespan as the larger of the two port loads of an arbitrarily chosen last flow and on analyzing the schedule in LP-assigned $t$ order; the algorithm actually schedules by Birkhoff–von Neumann matchings, whose makespan is the maximum load over all ports, so if those two views diverge the $1.5$ guarantee may not apply to the real output.
Editorial extensions
If this is right
- If correct, the $1.5+\epsilon$ polynomial-time bound replaces $2+\epsilon$ as the best known guarantee for heterogeneous parallel coflow makespan.
- The deterministic variant provides the same asymptotic ratio without random bits, and its additive $1/(2\cdot LB)$ term vanishes as port loads grow, giving $1.5+\epsilon$ when the minimum flow size is at least $(1-\eta)/\eta$.
- The interval-indexed LP uses only $O(\log T)$ intervals, so the algorithms' running times are polynomial in the input size rather than in the total volume of data.
- Each core's schedule is a sequence of permutation matchings produced by Birkhoff–von Neumann decomposition, so it can be executed directly on nonblocking switch hardware.
Reading between the lines
- Beyond the paper: the proof analyzes an ordering of flows by the LP-assigned time $t$, but the implemented Birkhoff–von Neumann schedule can transmit disjoint flows in parallel; the gap between these two schedules is not quantified, so an empirical check on adversarial instances would be valuable.
- Beyond the paper: the same interval-indexed rounding scheme may extend to total weighted coflow completion time, though the paper only addresses makespan.
- Beyond the paper: because the deterministic ratio improves as flow sizes grow, practical data-center workloads with large transfers could see the stronger $1.5+\epsilon$ guarantee, while small-flow workloads would carry the additive $1/(2\cdot LB)$ term.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript studies makespan minimization for preemptive coflow scheduling across m heterogeneous network cores. It introduces a time-indexed linear programming relaxation, a randomized rounding step that assigns each flow to a single core and a time label, and then applies Birkhoff-von Neumann decomposition per core to obtain a non-splitting schedule. The paper claims a randomized 1.5-approximation in pseudo-polynomial time, a derandomized 1.5+1/(2LB) algorithm, and polynomial-time 1.5+epsilon variants, improving on the previously known 2+epsilon bound. The central technical step is Lemma 4.1, which bounds the expected makespan of the algorithm's output by analyzing a hypothetical schedule in which flows are transmitted in non-decreasing order of their sampled time labels.
Significance. If the 1.5 bound were correct, this would be a meaningful improvement over the best known 2+epsilon approximation for heterogeneous parallel coflow scheduling, and the derandomization and interval-indexed variants would be useful contributions. However, the main proof analyzes a schedule that the algorithm does not produce, and there is a concrete instance on which the claimed 1.5 bound is violated. The paper therefore does not establish its central claim, and the same flaw propagates to all four main theorems (Theorems 4.2, 5.2, 6.1, and 7.2).
major comments (3)
- [Section 4, Algorithm 2 and Lemma 4.1] The analysis in Lemma 4.1 does not bound the makespan of the schedule produced by Algorithm 2. Algorithm 2 (line 4) aggregates all flows assigned to each core p and runs Algorithm 1, whose makespan is the maximum row/column load of the aggregated demand matrix D_p. The proof of Lemma 4.1 instead bounds the expected load on a port by considering flows in non-decreasing order of their sampled time label t and using the probability that another flow receives a smaller label. These are different objects: in the BvN schedule, a flow with a large label contributes its entire volume to the port load regardless of its label, whereas in the analyzed t-order schedule it is delayed. The manuscript itself acknowledges this after Algorithm 2: 't is not directly utilized in the algorithm; it serves solely as a tool for our analysis.' That admission is precisely the problem, because the lemma's bound depends on the t-order, so the analyzed schedule is not the algorithm's output. Additionally, the proof fixes 'the last completed flow (i,j,k)' before the random choices are made, but the identity of the last flow depends on the rounding outcomes, so the conditioning is not a valid WLOG step.
- [Theorem 4.2] The claimed 1.5-approximation is false for a valid instance. Take m=2 unit-speed cores and a single coflow with demand matrix [[1,1],[1,1]] on two input and two output ports. The LP optimum is C*_max = 1, achieved by setting y_{ijkp0} = 1/2 for each of the four flows and each core p. Algorithm 2 then assigns each flow independently to core 1 or core 2 with probability 1/2. For a given assignment, the makespan is max(rho(D_1), rho(D_2)), where rho is the maximum row or column sum of the aggregate matrix on that core. This value is 1 only in the 2 of 16 equally likely assignments where the flows on each core form a permutation matrix; in the remaining 14 assignments the makespan is 2. Hence E[Cmax] = (2*1 + 14*2)/16 = 30/16 = 1.875 > 1.5 = 1.5*C*_max. This directly refutes Theorem 4.2 and, because Theorems 5.2, 6.1, and 7.2 rely on the same lemma and the same analysis, the counterexample invalidates those results as well.
- [Section 4, proof of Lemma 4.1] The inequality Ep,t[Ci] <= dijk/sp + (t+1/2) in the proof of Lemma 4.1 is derived by summing, over other flows on the same port, the product of each flow's volume and the probability that it is assigned a label smaller than t. This quantity bounds the load in a hypothetical ordered schedule, but in the actual BvN schedule the load contributed by a flow is independent of its label: every flow assigned to the core contributes its full volume to its input and output ports. Therefore the conditional expectation computed in the lemma is not an upper bound on the conditional makespan of the algorithm. This is not a minor gap but a load-bearing mismatch between the object analyzed and the object produced.
minor comments (3)
- [Section 7, Theorem 7.3] The proof of Theorem 7.3 says 'Following the same proof steps as in The proof of Theorem 7.3 yields this theorem,' which is self-referential and should instead refer to the proof of Theorem 7.2 or to the argument that precedes it.
- [Sections 5 and 7] Several formulas contain typesetting artifacts, such as '1.5 + 1 2·LB' and '1Pm p=1 sp', which make the intended expressions, likely 1.5 + 1/(2LB) and 1/(sum_p s_p), hard to read and should be corrected.
- [Section 4, definition of Pr_{p,t}] The quantity Pr_{p,t}(i',j',k') is described as a probability that another flow is scheduled before (i,j,k), but the actual algorithm does not schedule flows in this order. The notation should be clarified, or the paper should explicitly state that this is only an analysis artifact; currently the text alternates between calling it a probability and using it to bound port loads.
Circularity Check
No significant circularity: the approximation guarantee follows from the LP relaxation and external Birkhoff-von Neumann decomposition; self-citations appear as baselines and context, not as load-bearing premises.
full rationale
The derivation chain is not circular. Algorithms 2-5 round the interval-indexed LP relaxation and bound the expected makespan by comparing the rounded schedule against the LP's own constraints (1d) and (1e), then use the LP optimum only as a lower bound on the true optimum. This is a standard LP-rounding argument rather than a definitional equivalence: the claimed 1.5 ratio is not obtained by renaming a fitted parameter or by assuming the target result. The Birkhoff-von Neumann decomposition (Theorem 3.1) is cited to external work [17], and Algorithm 1 is attributed to Qiu et al. [18], not to the author's own prior results. Self-citations [4]-[9] appear in the related-work discussion and as baselines (e.g., the concluding claim of improving the previous '2 + epsilon' bound from the author's earlier paper [5]); they do not carry the proof of the new theorems. The manuscript itself flags a gap before Theorem 7.3 ('The proof of Theorem 7.2 has an overestimation of the upper bound of E[ell=0,j][Ci].'), and the passage 't is not directly utilized in the algorithm; it serves solely as a tool for our analysis' indicates a possible proof-algorithm mismatch, but these are correctness concerns, not circularity. No load-bearing step reduces by construction to its own inputs or to an unverified self-citation chain.
Assumptions & free parameters
assumptions (4)
- standard math Birkhoff-von Neumann decomposition theorem
- domain assumption Integer flow sizes and d_ijk/smax >= 1 normalization
- ad hoc to paper Pairwise independence of random switch-time assignments
- ad hoc to paper The proof's t-order schedule is equivalent to Algorithm 1's BvN schedule
Cite this review
Pith. "Pith review of Non-Splitting Coflow Scheduling with Provable Guarantees in Heterogeneous Parallel Networks." pith.science (2026). https://pith.science/paper/CTPOOIGC
@misc{pith2026250109293,
author = {Pith},
title = {Pith review of: Non-Splitting Coflow Scheduling with Provable Guarantees in Heterogeneous Parallel Networks},
year = {2026},
howpublished = {\url{https://pith.science/paper/CTPOOIGC}},
note = {Machine review of arXiv:2501.09293}
}
abstract
As a prominent network abstraction, coflow models efficiently capture communication patterns in data centers. Since coflow scheduling in large-scale data centers is $\mathcal{NP}$-hard, the existing literature has predominantly focused on limited environments with $m=2$ network cores, relying on flow splitting, which introduces substantial operational overhead. Crucially, no approximation algorithm with provable performance guarantees has been proposed for the more practical, non-splitting coflow scheduling problem, even for the $m=2$ case, let alone for general hybrid architectures. To bridge this critical gap, this paper investigates the non-splitting problem within a hybrid, heterogeneous parallel network featuring multiple network cores ($m \ge 2$) composed of Electronic Packet Switches (EPS), not-all-stop Optical Circuit Switches (OCS), and all-stop OCS. We propose three unified polynomial-time approximation algorithms that minimize the makespan and the total weighted coflow completion time across this hybrid environment without incurring any splitting overhead. Let $\tau$ denote the maximum flow degree across all ports in the network, and let $m$ be the number of network cores. To minimize the makespan, our algorithm achieves an approximation ratio of $2\min\left\{2\tau-1, m+\tau-1\right\}$ in the hybrid architecture. To minimize the total weighted coflow completion time, our algorithm achieves an approximation ratio of $16\min\left\{2\tau-1, 2m+\tau-1\right\}$ in the hybrid architecture. Moreover, we characterize the approximation ratios of our algorithm under different architectural combinations.
Reference graph
Works this paper leans on
-
[1]
Sincronia: Near-optimal network design for coflows,
S. Agarwal, S. Rajakrishnan, A. Narayan, R. Agarwal, D. Shmoys, and A. Vahdat, “Sincronia: Near-optimal network design for coflows,” in Proceedings of the 2018 ACM Conference on SIGCOMM, ser. SIGCOMM ’18. New York, NY, USA: Association for Computing Machinery, 2018, p. 16–29
2018
-
[2]
On scheduling coflows,
S. Ahmadi, S. Khuller, M. Purohit, and S. Yang, “On scheduling coflows,” Algorithmica, vol. 82, no. 12, pp. 3604–3629, 2020
2020
-
[3]
The hadoop distributed file system: Architecture and design,
D. Borthakur, “The hadoop distributed file system: Architecture and design,” Hadoop Project Website, vol. 11, no. 2007, p. 21, 2007
2007
-
[4]
Improved approximation algorithms for minimizing the total weighted completion time of coflows,
C.-Y. Chen, “Improved approximation algorithms for minimizing the total weighted completion time of coflows,” 2023. [Online]. Available: https://arxiv.org/abs/2311.11296 21
arXiv 2023
-
[5]
C.-Y. Chen, “Improved approximation coflows scheduling algorithms for minimizing the total weighted completion time and makespan in heterogeneous parallel networks,” 2023. [Online]. Available: https://arxiv.org/abs/2312.16413
arXiv 2023
-
[6]
C.-Y. Chen, “Scheduling coflows for minimizing the total weighted completion time in hetero- geneous parallel networks,” Journal of Parallel and Distributed Computing , vol. 182, p. 104752, 2023
work page 2023
-
[7]
Efficient approximation algorithms for scheduling coflows with precedence con- straints in identical parallel networks to minimize weighted completion time,
C.-Y. Chen, “Efficient approximation algorithms for scheduling coflows with precedence con- straints in identical parallel networks to minimize weighted completion time,” IEEE Transac- tions on Services Computing , 2024
2024
-
[8]
Efficient approximation algorithms for scheduling coflows with total weighted completion time in identical parallel networks,
C.-Y. Chen, “Efficient approximation algorithms for scheduling coflows with total weighted completion time in identical parallel networks,” IEEE Transactions on Cloud Computing , 2024
2024
Show all 25 references
-
[9]
Scheduling coflows for minimizing the makespan in identical parallel networks,
C.-Y. Chen and J. Chen, “Scheduling coflows for minimizing the makespan in identical parallel networks,” 2023. [Online]. Available: https://arxiv.org/abs/2302.06846
2023 arXiv
-
[10]
Coflow: A networking abstraction for cluster applications,
M. Chowdhury and I. Stoica, “Coflow: A networking abstraction for cluster applications,” in Proceedings of the 11th ACM Workshop on Hot Topics in Networks , ser. HotNets-XI. New York, NY, USA: Association for Computing Machinery, 2012, p. 31–36
2012
-
[11]
Efficient coflow scheduling without prior knowledge,
M. Chowdhury and I. Stoica, “Efficient coflow scheduling without prior knowledge,” in Pro- ceedings of the 2015 ACM Conference on SIGCOMM , ser. SIGCOMM ’15. New York, NY, USA: Association for Computing Machinery, 2015, p. 393–406
2015
-
[12]
Efficient coflow scheduling with varys,
M. Chowdhury, Y. Zhong, and I. Stoica, “Efficient coflow scheduling with varys,” inProceedings of the 2014 ACM Conference on SIGCOMM , ser. SIGCOMM ’14. New York, NY, USA: Association for Computing Machinery, 2014, p. 443–454
2014
-
[13]
Mapreduce: Simplified data processing on large clusters,
J. Dean and S. Ghemawat, “Mapreduce: Simplified data processing on large clusters,” Com- munications of the ACM , vol. 51, no. 1, p. 107–113, jan 2008
2008
-
[14]
Dryad: distributed data-parallel programs from sequential building blocks,
M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly, “Dryad: distributed data-parallel programs from sequential building blocks,” in Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007 , 2007, pp. 59–72
2007
-
[15]
Brief announcement: Improved approximation algorithms for scheduling co-flows,
S. Khuller and M. Purohit, “Brief announcement: Improved approximation algorithms for scheduling co-flows,” in Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016, pp. 239–240
2016
-
[16]
Co-scheduler: A coflow-aware data-parallel job scheduler in hybrid elec- trical/optical datacenter networks,
Z. Li and H. Shen, “Co-scheduler: A coflow-aware data-parallel job scheduler in hybrid elec- trical/optical datacenter networks,” IEEE/ACM Transactions on Networking , vol. 30, no. 4, pp. 1599–1612, 2022
2022
-
[17]
Diagonals of doubly stochastic matrices,
M. Marcus and R. Ree, “Diagonals of doubly stochastic matrices,” TheQuarterly Journal of Mathematics, vol. 10, no. 1, p. 296–302, 1959
1959
-
[18]
Minimizing the total weighted completion time of coflows in datacenter networks,
Z. Qiu, C. Stein, and Y. Zhong, “Minimizing the total weighted completion time of coflows in datacenter networks,” inProceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures, ser. SPAA ’15. New York, NY, USA: Association for Computing Machinery, 201...
2015
-
[19]
Scheduling unrelated machines by randomized rounding,
A. S. Schulz and M. Skutella, “Scheduling unrelated machines by randomized rounding,”SIAM Journal on Discrete Mathematics , vol. 15, no. 4, pp. 450–469, 2002
2002
-
[20]
An improved bound for minimizing the total weighted completion time of coflows in datacenters,
M. Shafiee and J. Ghaderi, “An improved bound for minimizing the total weighted completion time of coflows in datacenters,” IEEE/ACM Transactions on Networking , vol. 26, no. 4, pp. 1674–1687, 2018
2018
-
[21]
The hadoop distributed file system,
K. Shvachko, H. Kuang, S. Radia, and R. Chansler, “The hadoop distributed file system,” in 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST) , 2010, pp. 1–10
2010
-
[22]
Regularization-based coflow scheduling in optical circuit switches,
H. Tan, C. Zhang, C. Xu, Y. Li, Z. Han, and X.-Y. Li, “Regularization-based coflow scheduling in optical circuit switches,” IEEE/ACM Transactions on Networking, vol. 29, no. 3, pp. 1280– 1293, 2021
2021
-
[23]
Spark: Cluster com- puting with working sets,
M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica, “Spark: Cluster com- puting with working sets,” in 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 10) , 2010
2010
-
[24]
Coda: Toward auto- matically identifying and scheduling coflows in the dark,
H. Zhang, L. Chen, B. Yi, K. Chen, M. Chowdhury, and Y. Geng, “Coda: Toward auto- matically identifying and scheduling coflows in the dark,” in Proceedings of the 2016 ACM Conference on SIGCOMM, ser. SIGCOMM ’16. New York, NY, USA: Association for Com- puting Machinery, 2016, ...
2016
-
[25]
Minimizing coflow completion time in optical circuit switched networks,
T. Zhang, F. Ren, J. Bao, R. Shu, and W. Cheng, “Minimizing coflow completion time in optical circuit switched networks,” IEEE Transactions on Parallel and Distributed Systems , vol. 32, no. 2, pp. 457–469, 2021. 23 Table 1: Notation and Terminology N The number of input/outpu...
2021
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.