REVIEW 3 major objections 4 minor 1 cited by
Dynamic Stale Synchronous Parallel Distributed Training for Deep Learning
T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read A dynamic staleness threshold, chosen per iteration from a user-supplied range, lets distributed deep learning reduce synchronization waits and converge earlier while keeping SSP's convergence guarantee.
desk verdict A promising dynamic staleness-threshold idea that currently overclaims its controller's optimality; the big heterogeneous speedup is plausible but rests on a flawed wait-time proxy. 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 central mechanism is a server-side synchronization controller. It keeps the two most recent push timestamps from each worker, computes each worker's latest iteration interval, and then treats future push times as arithmetic sequences: if the fastest worker's latest interval is $I_p$, its next pushes are predicted at $\mathrm{Sim}_p[0] + i \cdot I_p$, and similarly for the slowest worker. It searches the allowance range $[0, r_{\max}]$ for the index $r^*$ that minimizes the simulated waiting time, expressed as $|\mathrm{Sim}_{slowest}[k] - \mathrm{Sim}_p[r]|$ over all $k$. That one quantity carries the argument: the claimed speedup comes entirely from choosing where the fastest worker will pause, and the arithmetic extrapolation makes the choice cheap enough to run online.
What would settle it
Run DSSP with two workers on a shared cluster, inject random network delays so the slowest worker's iteration interval changes unpredictably from one step to the next, and compare the fastest worker's actual waiting time against the controller's predicted minimum; if the chosen allowance repeatedly produces longer waits than a fixed threshold would, the claimed waiting-time reduction fails.
Extended reading notes
Core claim
On its own terms, the paper's discovery is that the staleness threshold in SSP does not have to be fixed: synchronization points can become a per-worker, per-iteration decision without losing the convergence guarantee. DSSP takes a range $[s_L, s_U]$ instead of one value. When the fastest worker exceeds $s_L$, the server's synchronization controller extrapolates the next $r_{\max}$ push times of that worker and of the slowest worker from their latest iteration intervals, and picks the allowance $r^* \in [0, r_{\max}]$ whose simulated wait is smallest. That $r^*$ is a credit the worker spends in later iterations, so different workers can have different allowances at the same moment and the effective threshold tracks the cluster's changing speeds. The paper shows DSSP inherits SSP's $O(\sqrt{T})$ regret bound — a guarantee that average loss approaches the optimum as $T$ grows — and reports that DSSP converges earlier than fixed-threshold SSP, most clearly on a heterogeneous GPU cluster.
Load-bearing premise
The load-bearing premise — stated as an assumption in Section III.B and left as future work in the conclusion — is that a worker's iteration intervals stay similar over short periods, so the next few intervals can be predicted from the most recent one; when compute or network speeds fluctuate, the chosen pause point can increase waiting time instead of reducing it.
Editorial extensions
If this is right
- Users can stop searching for a single best staleness threshold; giving a plausible range is enough, and the server adapts the effective threshold during training.
- In clusters with mixed GPU models, DSSP reaches a target accuracy much earlier than fixed-threshold SSP or BSP while avoiding the divergence risk of fully asynchronous training.
- Because the effective threshold is always bounded by the user's upper limit, DSSP keeps SSP's $O(\sqrt{T})$ regret bound and therefore converges in expectation for large $T$ under SSP's convexity and Lipschitz conditions.
- Different workers can hold different thresholds at the same time, and each worker's threshold can change across iterations, letting the system track run-time changes in the cluster.
Reading between the lines
- The paper's arithmetic extrapolation is the fragile link; replacing it with a smoother predictor such as an exponential moving average of recent intervals would be a natural test of whether the method still helps when network delays vary.
- The paper explains that stale updates can act like the noise used in image-distortion augmentation for convolutional networks; that suggests a testable corollary that on very deep convolutional models a moderate dynamic threshold may improve final accuracy, not just time-to-accuracy.
- The user-supplied range is still a hyperparameter; an extension the paper does not explore is making the range itself shrink near convergence, where stale gradients hurt more, and widen during early training.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes Dynamic Stale Synchronous Parallel (DSSP), an adaptive variant of SSP for parameter-server distributed training. DSSP takes a user-specified staleness range [sL, sU] and, at run time, uses a server-side controller to decide how many extra iterations the fastest worker may run beyond sL before being forced to synchronize. The decision is based on estimated future push times derived from each worker's two most recent iteration intervals. The authors provide a regret-bound argument and compare DSSP with BSP, ASP, and SSP by training AlexNet, ResNet-50, and ResNet-110 on CIFAR-10/100 in homogeneous and heterogeneous GPU environments. The main claims are that DSSP reduces synchronous waiting time and converges faster than fixed-threshold SSP, with a particularly large improvement in the heterogeneous two-worker setup.
Significance. If the controller worked as intended, DSSP would address a real practical problem: choosing the SSP staleness threshold, which is typically done by trial and error. The paper has some genuine strengths: it compares DSSP against 13 individual SSP thresholds rather than a single baseline, and it reports wall-clock time-to-accuracy, which is the right metric for a systems contribution. The heterogeneous-cluster result is suggestive and relevant to real deployments. However, the core waiting-time minimization heuristic is not validated analytically, the convergence proof does not apply to the algorithm as written, and the experimental basis is a median-of-three on a single two-container heterogeneous configuration with no variance reporting and no released code. The idea is plausible, but the supporting evidence is not yet at the level of the paper's claims.
major comments (3)
- [Section III.C, Algorithm 2] The objective in Algorithm 2, line 8, is not the waiting time that worker p will actually experience. If the controller returns r, the server decrements rp for each of the next r pushes and sends OK immediately; it is only on the following push, at time approximately Simp[r+1], that worker p faces the staleness check and may wait. The wait ends only when the slowest worker's push count satisfies tp - tslowest <= sL. Line 8 instead minimizes |Simslowest[k] - Simp[r]| over all k and r, which ignores the extra push, ignores the sL-gap condition, and can select a pair in which the slowest push occurs before p's relevant push. Even under the constant-interval assumption of Section III.B, the returned r* need not minimize the actual waiting time. Because this controller is the central mechanism of DSSP, the claimed waiting-time reduction is not established.
- [Section IV, Theorem 2 and Algorithm 1] The proof of Theorem 2 is a reduction to SSP with threshold sL + r, where r is the maximum of R, but Algorithm 1 does not enforce the corresponding bound on global staleness. The server sends OK whenever rp > 0 (Algorithm 1, lines 3-5) without checking tp - tslowest, and a worker that remains the fastest can have rp replenished by the controller on every subsequent push. Thus tp - tslowest can grow beyond sL + rmax, and the system is not an instance of SSP with threshold sU. The O(sqrt(T)) regret bound therefore does not follow from the stated argument. The authors need either to add an explicit cap on the global gap and modify the algorithm accordingly, or to provide a convergence analysis that accounts for the adaptive replenishment of rp.
- [Section V.A.4 and V.D, Table I] The empirical support for the central speedup claim is thin. Each experiment was run three times and only the median was selected, with no variance or per-run results reported. The headline heterogeneous result is a single two-worker Docker configuration with one GTX1060 and one GTX1080 Ti, and no code is released. In Table I, DSSP reaches 0.67 accuracy in 3016.4 s while ASP reaches it in 2993.1 s, so DSSP is not faster than ASP at that accuracy; the claimed advantage is over SSP. The DSSP-vs-SSP gap is large, but without error bars or confidence intervals its statistical significance cannot be assessed. I would like to see per-run results or confidence intervals and preferably more than one heterogeneous configuration.
minor comments (4)
- [Section III.A and Theorem 2] The notation r is overloaded: it is used both as a generic element of R and as the maximum element in the statement of Theorem 2 ('let r ∈ R and r ≥ ∀r′ ∈ R'). The proof should state explicitly that it uses rmax = sU - sL as the effective threshold.
- [Section V.A.4] The text says 'chose the medium result' where it means 'chose the median result'; please correct this wording, along with 'speedups' in the abstract and 'staled' throughout.
- [Section V.B] Comparing DSSP against 'Average SSP s=3 to 15' is not a representative baseline for the user-facing claim, because a user of SSP would select one threshold, not average over all thresholds. The individual SSP curves in Figures 3b, 3d, and 3f are the appropriate comparison and should be the primary basis for the claim.
- [Section VI] The future-work statement that DSSP has not been adapted to fluctuating network conditions is directly relevant to the constant-interval assumption in Section III.B and should be presented as a limitation earlier in the paper, not only as future work.
Circularity Check
No significant circularity: DSSP's regret bound is an external SSP bound applied at the maximum threshold, and the speedup claim is empirical.
full rationale
The paper's only formal derivation, Theorem 2, reduces DSSP to fixed-threshold SSP at the largest value in the allowed range and then applies the external regret bound from reference [18], which is not authored by the present authors and does not assume the dynamic mechanism's optimality. That reduction may be coarse, but it is not circular. The claim that DSSP reduces waiting time and converges faster is established empirically through comparisons with BSP, ASP, and fixed-threshold SSP; it is not derived from the fitted values or from a self-citation. Algorithm 2's extrapolation heuristic could be fragile under fluctuating intervals, but that is a robustness concern, not a definitional or self-referential circularity. No load-bearing self-citation, no imported uniqueness theorem, and no fitted parameter renamed as a prediction were found. The paper's own caveat about unstable network environments further confirms that its assumptions are stated rather than smuggled in. Therefore, the appropriate finding is no significant circularity.
Assumptions & free parameters
free parameters (1)
- Staleness threshold range (sL, R) =
sL=3, R=[0,12] in reported experiments
assumptions (4)
- domain assumption Iteration intervals of a worker in contiguous iterations over a short period are very similar
- domain assumption The regret bound for SSP with fixed threshold sU applies to DSSP because DSSP's actual staleness never exceeds sU
- standard math SGD convergence theory requiring convex loss functions applies
- domain assumption Error tolerance of iterative-convergent methods covers prediction mistakes
Cite this review
Pith. "Pith review of Dynamic Stale Synchronous Parallel Distributed Training for Deep Learning." pith.science (2026). https://pith.science/paper/HSDODPZU
@misc{pith2026190811848,
author = {Pith},
title = {Pith review of: Dynamic Stale Synchronous Parallel Distributed Training for Deep Learning},
year = {2026},
howpublished = {\url{https://pith.science/paper/HSDODPZU}},
note = {Machine review of arXiv:1908.11848}
}
read the original abstract
Deep learning is a popular machine learning technique and has been applied to many real-world problems. However, training a deep neural network is very time-consuming, especially on big data. It has become difficult for a single machine to train a large model over large datasets. A popular solution is to distribute and parallelize the training process across multiple machines using the parameter server framework. In this paper, we present a distributed paradigm on the parameter server framework called Dynamic Stale Synchronous Parallel (DSSP) which improves the state-of-the-art Stale Synchronous Parallel (SSP) paradigm by dynamically determining the staleness threshold at the run time. Conventionally to run distributed training in SSP, the user needs to specify a particular staleness threshold as a hyper-parameter. However, a user does not usually know how to set the threshold and thus often finds a threshold value through trial and error, which is time-consuming. Based on workers' recent processing time, our approach DSSP adaptively adjusts the threshold per iteration at running time to reduce the waiting time of faster workers for synchronization of the globally shared parameters, and consequently increases the frequency of parameters updates (increases iteration throughput), which speedups the convergence rate. We compare DSSP with other paradigms such as Bulk Synchronous Parallel (BSP), Asynchronous Parallel (ASP), and SSP by running deep neural networks (DNN) models over GPU clusters in both homogeneous and heterogeneous environments. The results show that in a heterogeneous environment where the cluster consists of mixed models of GPUs, DSSP converges to a higher accuracy much earlier than SSP and BSP and performs similarly to ASP. In a homogeneous distributed cluster, DSSP has more stable and slightly better performance than SSP and ASP, and converges much faster than BSP.
Figures
Forward citations
Cited by 1 Pith paper
-
Distributed Training under Packet Loss
The paper proposes unbiased gradient renormalization and stale-parameter broadcasts to keep distributed training convergent under random packet loss, with bounded inter-worker drift.
Reference graph
Works this paper leans on
-
[1]
Large scale distributed deep networks,
J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin, M. Mao, A. Senior, P. Tucker, K. Yang, Q. V . Le et al., “Large scale distributed deep networks,” inAdvances in neural information processing systems, 2012, pp. 1223–1231
work page 2012
-
[2]
Mxnet: A flexible and ef- ficient machine learning library for heterogeneous distributed systems,
T. Chen, M. Li, Y . Li, M. Lin, N. Wang, M. Wang, T. Xiao, B. Xu, C. Zhang, and Z. Zhang, “Mxnet: A flexible and ef- ficient machine learning library for heterogeneous distributed systems,” arXiv preprint arXiv:1512.01274 , 2015
arXiv 2015
-
[3]
Imagenet classification with deep convolutional neural networks,
A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in Advances in neural information processing systems, 2012, pp. 1097–1105
work page 2012
-
[4]
Rethinking the inception architecture for computer vision,
C. Szegedy, V . Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna, “Rethinking the inception architecture for computer vision,” in The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016
work page 2016
-
[5]
Very deep convolutional networks for large-scale image recognition,
K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” arXiv preprint arXiv:1409.1556, 2014
arXiv 2014
-
[6]
Microsoft coco: Com- mon objects in context,
T.-Y . Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ra- manan, P. Doll ´ar, and C. L. Zitnick, “Microsoft coco: Com- mon objects in context,” in European conference on computer vision. Springer, 2014, pp. 740–755
work page 2014
-
[7]
Project adam: Building an efficient and scalable deep learn- ing training system
T. M. Chilimbi, Y . Suzue, J. Apacible, and K. Kalyanaraman, “Project adam: Building an efficient and scalable deep learn- ing training system.” in OSDI, vol. 14, 2014, pp. 571–582
work page 2014
-
[8]
Scaling distributed machine learning with the parameter server,
M. Li, D. G. Andersen, J. W. Park, A. J. Smola, A. Ahmed, V . Josifovski, J. Long, E. J. Shekita, and B.-Y . Su, “Scaling distributed machine learning with the parameter server,” in 11th {USENIX} Symposium on Operating Systems Design and Implementation ( {OSDI} 14), 2014, pp. 583–598
work page 2014
Show all 38 references
-
[9]
Petuum: A new platform for distributed machine learning on big data,
E. P. Xing, Q. Ho, W. Dai, J. K. Kim, J. Wei, S. Lee, X. Zheng, P. Xie, A. Kumar, and Y . Yu, “Petuum: A new platform for distributed machine learning on big data,” IEEE Transactions on Big Data , vol. 1, no. 2, pp. 49–67, 2015
2015
-
[10]
A survey of open source tools for machine learning with big data in the hadoop ecosystem,
S. Landset, T. M. Khoshgoftaar, A. N. Richter, and T. Hasanin, “A survey of open source tools for machine learning with big data in the hadoop ecosystem,” Journal of Big Data, vol. 2, no. 1, p. 24, 2015
2015
-
[11]
Mllib: Machine learning in apache spark,
X. Meng, J. Bradley, B. Yavuz, E. Sparks, S. Venkataraman, D. Liu, J. Freeman, D. Tsai, M. Amde, S. Owen et al., “Mllib: Machine learning in apache spark,” The Journal of Machine Learning Research, vol. 17, no. 1, pp. 1235–1241, 2016
2016
-
[12]
Deep captioning with multimodal recurrent neural networks (m-rnn),
J. Mao, W. Xu, Y . Yang, J. Wang, Z. Huang, and A. Yuille, “Deep captioning with multimodal recurrent neural networks (m-rnn),” arXiv preprint arXiv:1412.6632 , 2014
2014 arXiv
-
[13]
Kunpeng: Parameter server based distributed learning systems and its applications in alibaba and ant financial,
J. Zhou, X. Li, P. Zhao, C. Chen, L. Li, X. Yang, Q. Cui, J. Yu, X. Chen, Y . Ding et al. , “Kunpeng: Parameter server based distributed learning systems and its applications in alibaba and ant financial,” in Proceedings of the 23rd ACM SIGKDD International Conference on Knowle...
2017
-
[14]
On model parallelization and scheduling strategies for distributed machine learning,
S. Lee, J. K. Kim, X. Zheng, Q. Ho, G. A. Gibson, and E. P. Xing, “On model parallelization and scheduling strategies for distributed machine learning,” in Advances in neural information processing systems , 2014, pp. 2834–2842
2014
-
[15]
On convergence of model parallel proximal gradient algorithm for stale synchronous parallel system,
Y . Zhou, Y . Yu, W. Dai, Y . Liang, and E. Xing, “On convergence of model parallel proximal gradient algorithm for stale synchronous parallel system,” in Artificial Intelligence and Statistics, 2016, pp. 713–722
2016
-
[16]
Strategies and principles of distributed machine learning on big data,
E. P. Xing, Q. Ho, P. Xie, and D. Wei, “Strategies and principles of distributed machine learning on big data,” En- gineering, vol. 2, no. 2, pp. 179–195, 2016
2016
-
[17]
Direct bulk- synchronous parallel algorithms,
A. V . Gerbessiotis and L. G. Valiant, “Direct bulk- synchronous parallel algorithms,” Journal of parallel and distributed computing, vol. 22, no. 2, pp. 251–267, 1994
1994
-
[18]
More effective dis- tributed ml via a stale synchronous parallel parameter server,
Q. Ho, J. Cipar, H. Cui, S. Lee, J. K. Kim, P. B. Gibbons, G. A. Gibson, G. Ganger, and E. P. Xing, “More effective dis- tributed ml via a stale synchronous parallel parameter server,” in Advances in neural information processing systems , 2013, pp. 1223–1231
2013
-
[19]
Exploiting bounded staleness to speed up big data analytics
H. Cui, J. Cipar, Q. Ho, J. K. Kim, S. Lee, A. Kumar, J. Wei, W. Dai, G. R. Ganger, P. B. Gibbons et al. , “Exploiting bounded staleness to speed up big data analytics.” in USENIX Annual Technical Conference, 2014, pp. 37–48
2014
-
[20]
Hogwild: A lock- free approach to parallelizing stochastic gradient descent,
B. Recht, C. Re, S. Wright, and F. Niu, “Hogwild: A lock- free approach to parallelizing stochastic gradient descent,” in Advances in neural information processing systems, 2011, pp. 693–701
2011
-
[21]
Paral- lelized stochastic gradient descent,
M. Zinkevich, M. Weimer, L. Li, and A. J. Smola, “Paral- lelized stochastic gradient descent,” in Advances in neural information processing systems , 2010, pp. 2595–2603
2010
-
[22]
Accelerating deep neural network training with inconsistent stochastic gradient descent,
L. Wang, Y . Yang, R. Min, and S. Chakradhar, “Accelerating deep neural network training with inconsistent stochastic gradient descent,” Neural Networks , vol. 93, pp. 219–229, 2017
2017
-
[23]
High-performance distributed ml at scale through parameter server consistency models,
W. Dai, A. Kumar, J. Wei, Q. Ho, G. Gibson, and E. P. Xing, “High-performance distributed ml at scale through parameter server consistency models,” inTwenty-Ninth AAAI Conference on Artificial Intelligence , 2015
2015
-
[24]
Managed communication and consistency for fast data-parallel iterative analytics,
J. Wei, W. Dai, A. Qiao, Q. Ho, H. Cui, G. R. Ganger, P. B. Gibbons, G. A. Gibson, and E. P. Xing, “Managed communication and consistency for fast data-parallel iterative analytics,” in Proceedings of the Sixth ACM Symposium on Cloud Computing. ACM, 2015, pp. 381–394
2015
-
[25]
Communica- tion efficient distributed machine learning with the parameter server,
M. Li, D. G. Andersen, A. J. Smola, and K. Yu, “Communica- tion efficient distributed machine learning with the parameter server,” in Advances in Neural Information Processing Sys- tems, 2014, pp. 19–27
2014
-
[26]
Revisiting distributed synchronous sgd,
J. Chen, X. Pan, R. Monga, S. Bengio, and R. Jozefow- icz, “Revisiting distributed synchronous sgd,” arXiv preprint arXiv:1604.00981, 2016
2016 arXiv
-
[27]
Omnivore: An optimizer for multi-device deep learning on cpus and gpus,
S. Hadjis, C. Zhang, I. Mitliagkas, D. Iter, and C. R ´e, “Omnivore: An optimizer for multi-device deep learning on cpus and gpus,” arXiv preprint arXiv:1606.04487 , 2016
2016 arXiv
-
[28]
Asynchronous distributed admm for consensus optimization,
R. Zhang and J. Kwok, “Asynchronous distributed admm for consensus optimization,” in International Conference on Machine Learning, 2014, pp. 1701–1709
2014
-
[29]
SOSCIP GPU,
“SOSCIP GPU,” accessed 2018-08-01. [Online]. Available: https://docs.scinet.utoronto.ca/index.php/SOSCIP GPU
2018
-
[30]
Learning multiple layers of features from tiny images,
A. Krizhevsky and G. Hinton, “Learning multiple layers of features from tiny images,” Citeseer, Tech. Rep., 2009
2009
-
[31]
Deep residual learning for image recognition,
K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” inProceedings of the IEEE conference on computer vision and pattern recognition , 2016, pp. 770– 778
2016
-
[32]
Efficient object localization using convolutional networks,
J. Tompson, R. Goroshin, A. Jain, Y . LeCun, and C. Bregler, “Efficient object localization using convolutional networks,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2015, pp. 648–656
2015
-
[33]
One weird trick for parallelizing convo- lutional neural networks,
A. Krizhevsky, “One weird trick for parallelizing convo- lutional neural networks,” arXiv preprint arXiv:1404.5997 , 2014
2014 arXiv
-
[34]
Dropout: a simple way to prevent neural networks from overfitting,
N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov, “Dropout: a simple way to prevent neural networks from overfitting,” The Journal of Machine Learning Research, vol. 15, no. 1, pp. 1929–1958, 2014
1929
-
[35]
The effectiveness of data augmen- tation in image classification using deep learning,
L. Perez and J. Wang, “The effectiveness of data augmen- tation in image classification using deep learning,” arXiv preprint arXiv:1712.04621, 2017
2017 arXiv
-
[36]
Scale- invariant convolutional neural networks,
Y . Xu, T. Xiao, J. Zhang, K. Yang, and Z. Zhang, “Scale- invariant convolutional neural networks,” arXiv preprint arXiv:1411.6369, 2014
2014 arXiv
-
[37]
Simultaneous estimation of image quality and distortion via multi-task convolutional neural networks,
L. Kang, P. Ye, Y . Li, and D. Doermann, “Simultaneous estimation of image quality and distortion via multi-task convolutional neural networks,” in Image Processing (ICIP), 2015 IEEE International Conference on . IEEE, 2015, pp. 2791–2795
2015
-
[38]
Adding gradient noise im- proves learning for very deep networks,
A. Neelakantan, L. Vilnis, Q. V . Le, I. Sutskever, L. Kaiser, K. Kurach, and J. Martens, “Adding gradient noise im- proves learning for very deep networks,” arXiv preprint arXiv:1511.06807, 2015
2015 arXiv
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.