A sufficient condition for a linear speedup in competitive parallel computing

Naoki Yonezawa

REVIEW 2 major objections 5 minor 13 references

A sufficient condition for a linear speedup in competitive parallel computing

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Exponential per-core execution times guarantee an exact linear speedup in competitive parallel computing.

desk verdict A clean sufficient-condition result wrapped around an unproved non-necessity claim; the paper is worth a referee's time only if that claim is cut or fixed. read the letter →

arxiv 1908.07715 v1 pith:5FUCLMHS submitted 2019-08-21 cs.DC

Naoki Yonezawa This is my paper · ORCID

classification cs.DC

keywords competitiveparallelcomputinglinearspeedupsuperlinearminimumofindependentrandomvariablesexponentialdistributioncoefficientvariationMonteCarlosimulationexecutiontime

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Competitive parallel computing runs identical copies of a code phase on several cores and adopts the result of the fastest core. This paper builds a probabilistic model in which the overall phase time is the minimum of n independent and identically distributed per-core execution times, then uses it to predict speedups. The main positive result is a sufficient condition: if per-core execution times are independent and identically distributed exponential random variables with a common rate, then the expected phase time on n cores is exactly 1/n of the single-core expected time, so the speedup is exactly n. The paper also proves the condition is not necessary, and its simulations show that hyperexponential distributions give superlinear speedups while Erlang and uniform distributions give sublinear ones; distributions with equal coefficients of variation (CV, standard deviation divided by mean) can give different speedups.

What carries the argument

The load-bearing object is the minimum of n i.i.d. random variables, with CDF $F_{Y_n}(y)=1-(1-F_X(y))^n$; this identity converts the per-core distribution into the distribution of the fastest core. When the parent distribution is exponential, $F_X(y)=1-e^{-\lambda y}$, the identity gives another exponential with rate $n\lambda$, so the mean phase time is $1/(n\lambda)$ and the speedup is exactly $n$. The coefficient of variation (standard deviation divided by mean) is the comparison metric the paper tests and finds insufficient.

What would settle it

Take a real phase, run it many times on one core and on n identical cores, and compare the average fastest time to $1/(n\lambda)$ where $\lambda$ is the per-core rate estimated from single-core runs. If the average fastest time does not decrease as $1/n$, or if the per-core times fail a test of exponentiality or show correlation across cores, then the theorem's precondition fails and the linear speedup is not guaranteed.

Watch

Extended reading notes

Core claim

The central claim is Theorem 4.1: exponentially distributed per-core execution times are sufficient, but not necessary, for competitive parallel computing to achieve a linear speedup. Concretely, if $X_1,\ldots,X_n$ are i.i.d. exponential with rate $\lambda$, then the phase time $Y_n=\min(X_1,\ldots,X_n)$ has CDF $F_{Y_n}(y)=1-e^{-n\lambda y}$, hence mean $\mathbb{E}[Y_n]=1/(n\lambda)$. Since one core has mean $1/\lambda$, the speedup $S_n=\mathbb{E}[Y_1]/\mathbb{E}[Y_n]$ equals $n$. The proof of non-necessity gives a hyperexponential density (a mixture of exponentials) with $n\lambda$ substituted for $\lambda$ that also yields $\mathbb{E}[Y_n]=1/(n\lambda)$. Simulations then show speedups growing with coefficient of variation, with superlinear speedups for CV above 1 and sublinear speedups below 1, and unequal speedups for distributions sharing the same CV.

Load-bearing premise

The load-bearing premise is that the n per-core execution times are independent and identically distributed and that the phase finishes exactly at the minimum, with no coordination overhead or correlation between cores; if cores are correlated, heterogeneous, or the fastest result cannot be collected for free, the predicted speedup need not hold.

Editorial extensions

If this is right

A workload whose per-core phase times are approximately i.i.d. exponential will see its expected completion time shrink as $1/n$ on $n$ cores, giving a predictable linear speedup.
Distributions with coefficient of variation above 1, such as hyperexponential mixtures, can produce superlinear speedups; the paper reports speedups of about 276 and 521 for $n=100$ at CVs 1.51 and 1.62.
Distributions with CV below 1, such as the Erlang and uniform distributions used in the simulations, give sublinear speedups; for $n=100$ Erlang CVs of 0.58 and 0.71 gave speedups around 7.7 and 15.1.
Because equal CVs do not imply equal speedups, performance prediction must use the full distribution of per-core times, not just its coefficient of variation.
Because exponential per-core times suffice, a system that can randomize per-phase times to approximate that distribution is guaranteed linear speedup without restructuring the sequential program.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Inference: The identical-rate assumption can be relaxed; for independent exponentials with rates $\lambda_i$, the minimum is exponential with rate $\sum_i \lambda_i$, so the paper's proof technique still delivers a linear speedup for heterogeneous exponential cores.
Inference: A practical test of the model would measure per-core times of a real phase and check whether the empirical minimum scales as $1/n$; if it does not, the i.i.d. assumption is likely the point of failure.
Inference: The fixed-CV comparison (uniform vs. Erlang) could be applied more broadly to other distribution pairs to map which shapes of per-core time distributions produce the largest speedups at a given CV.
Inference: The sufficient condition suggests a scheduling heuristic: randomizing per-phase execution times, for instance by launching algorithm variants with random seeds, may make a real workload's times closer to exponential and thereby unlock the linear speedup.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here is the short version. Theorem 4.1(a) is correct and clean: with i.i.d. Exp(λ) core times, the phase time is min(X1,...,Xn) ~ Exp(nλ), so the speedup is exactly n. The paper does that part well. The "not necessary" half, Theorem 4.1(b), does not hold as written. The proof fixes a distribution for Yn, the phase time, and shows its mean is 1/(nλ). But in the model Yn is not an input; it is defined as min(X1,...,Xn). You cannot prescribe Yn's distribution unless you also exhibit per-core Xi whose minimum has that law. The paper does not. This is a load-bearing gap, because the "not necessary" claim is the stated novelty beyond the exponential case. The gap is repairable — for any target CDF G, setting F_X(y)=1-(1-G(y))^{1/n} gives the desired minimum — but that construction is absent. So the claim is unsupported as stated.

What is genuinely useful: the paper formalizes competitive parallel computing as a min-of-iid-times model and shows that exponential per-core times give linear speedup. It also demonstrates by simulation that equal CV across distributions does not imply equal speedup — Erlang and uniform with CV ≈ 0.58 give different curves. That is a real, if modest, point for practitioners who use CV to predict gains. The simulation is simple enough that the qualitative result is believable, though there is no code, no seeds, no error bars, and the hyperexponential parameters are tuned for illustration. The paper is honest about these limits, noting that such distributions "might not reflect the behavior of a real-world application."

Soft spots beyond the theorem: the model ignores inter-phase dependencies, synchronization, overhead, and correlated cores; the paper acknowledges some of this in passing. The i.i.d. assumption is strong. And the mathematical novelty is small — the exponential-minimum fact is textbook order statistics. Still, applying it to competitive parallel computing is a legitimate contribution, and the citation pattern looks appropriate.

Who should read it: people working on competitive or racemic parallel execution who want a baseline formula and a caution that CV is not sufficient. It is a workshop-level contribution, not a major journal result. If I were editor, I would send it to review as a short paper, but with the explicit instruction that the non-necessity claim be removed or repaired before acceptance. The sufficiency half and the simulation can stand alone.

Referee Report

2 major / 5 minor

Summary. The paper proposes a stochastic behavioral model for competitive parallel computing, in which a phase of a sequential program is executed as n identical copies on n cores and the phase time is Yn = min(X1, ..., Xn), with X1, ..., Xn i.i.d. per-core execution times. It derives the CDF of Yn, proves that independent exponential per-core times are sufficient for an exact linear speedup Sn = n, and claims that exponentiality is not necessary for linear speedup. The paper also reports Monte Carlo simulations for exponential, Erlang, hyperexponential, and uniform distributions, concluding that larger coefficients of variation tend to yield larger speedups and that the same CV does not always imply the same speedup.

Significance. The sufficient-condition half of Theorem 4.1 is correct and clean: for i.i.d. Exp(λ) core times, Eq. (1) gives Yn ~ Exp(nλ), so E[Yn] = 1/(nλ) and Sn = n. The paper also makes a useful and non-obvious observation that the coefficient of variation alone does not determine the speedup, as the uniform/Erlang comparison with the same CV demonstrates. However, the claimed non-necessity of the exponential distribution is not established as written, because the proof prescribes the law of Yn instead of deriving it from the per-core variables Xi, and the hyperexponential distribution used in the proof and in the simulations is not a valid probability density for a ≠ 1. These are load-bearing issues for two of the three stated contributions. If the non-necessity construction is repaired and the hyperexponential densities are corrected, the paper would make a modest but valid theoretical contribution.

major comments (2)

[§4.2, Theorem 4.1(b)] The 'not necessary' direction of Theorem 4.1 is not proved. In the model, Yn is defined as min(X1,...,Xn), so its law is determined by the parent distribution FX through Eq. (1). The proof instead prescribes a density for Yn directly and shows E[Yn] = 1/(nλ); this only shows that some random variable has that mean, not that it equals the minimum of n i.i.d. per-core execution times. A valid proof would start from a target CDF G for Yn, set FX(y) = 1 - (1 - G(y))^{1/n}, and verify that this is a genuine CDF. The manuscript does not do this, so the central 'exponential is not necessary' contribution is unsupported.
[§4.1, Eq. (4)] The claimed hyperexponential PDF is not a probability density for a ≠ 1. A hyperexponential density must have weights summing to 1; for Eq. (4) the weights are a/2 and a/(4a-2), whose sum is a^2/(2a-1), which equals 1 only at a = 1. Consequently the CDF does not tend to 1 as x → ∞. This invalidates the hyperexponential simulation results in §4.3.1 and Figure 4, and the density used in Theorem 4.1(b) is also invalid. The authors need to correct the weights and re-run the affected experiments.

minor comments (5)

[§4.1, uniform distribution] The lower bound of the uniform distribution is denoted a, which collides with the hyperexponential shape parameter a in Eq. (4). Please use distinct symbols, for example l and u for the uniform bounds.
[Figure 4 caption] The caption contains the typo 'Hyperexponetial'; it should read 'hyperexponential'.
[Section 2] The citation 'Wolfgang [5]' should be 'Ertel [5]' to match the reference list.
[Section 5] The sentence 'This imply that it is possible...' should be 'This implies that it is possible...'.
[Algorithm 1] For reproducibility, the pseudocode should specify the random-number generation method and the seed, since the simulation results otherwise cannot be independently verified.

Circularity Check

1 steps flagged · score 6.0 of 10

The sufficiency direction of Theorem 4.1 is derived correctly from the minimum-of-i.i.d. model, but the non-necessity proof prescribes the distribution of the derived quantity Yn rather than deriving it from per-core times, so that half is forced by construction.

self definitional [Theorem 4.1 proof, non-necessity part, Section 4.2.2]
"(a) is not a necessary condition for (b): It is suﬃcient to show another distribution which provides (b). If the random variable Yn follows the distribution which is represented as Equation 4 with nλ instead of λ, namely, fYn(x) = a 2nλe−anλx + a 4a− 2nλe− a 2a−1nλx, then E(Yn) = 1 λn = 1 n."

In the model, Yn is not an independent input: Proposition 3.1 defines Yn = min(X1,...,Xn), so its distribution must be obtained from the per-core distribution FX through FYn(y) = 1 - (1 - FX(y))^n. The proof instead directly prescribes a hyperexponential law for Yn whose mean is 1/(nλ), thereby inserting the linear speedup into the construction rather than deriving it from per-core execution times. To prove non-necessity, the paper would need to exhibit a per-core distribution FX that yields this Yn distribution through the minimum operation, for example FX = 1 - (1 - GYn)^(1/n), and verify it is a valid non-exponential distribution.

full rationale

The paper's main positive result, Theorem 4.1(a) in the sufficient direction, is self-contained and correct: given i.i.d. Exp(λ) per-core times, Proposition 3.1 gives FYn(y) = 1 - e^{-nλy}, so E[Yn] = 1/(nλ) and Sn = n. That part is not circular and is independently verifiable. The circularity burden is concentrated entirely in the non-necessity half of the same theorem. There the proof selects a distribution for the derived variable Yn with the desired expectation, rather than deriving Yn from a distribution on per-core variables Xi. Since Yn is defined as the minimum of the Xi, prescribing its distribution is not enough to exhibit a legitimate competitive-parallel-computing instance. The claim is repairable by constructing FX = 1 - (1 - GYn)^(1/n) and checking that it is a valid CDF different from exponential, but the paper does not do this. No self-citation load-bearing issue, fitted-parameter-renamed-as-prediction issue, or ansatz-smuggling issue appears. The simulation-based findings about equal CV not implying equal speedup are empirical observations from explicitly stated distributions and are not circular. Overall, because the central sufficiency result is sound but a stated sub-claim (non-necessity) is established only by construction of the output distribution, a score of 6 is appropriate.

Assumptions & free parameters 3 free parameters · 3 assumptions · 0 invented entities

The central theorem rests on the i.i.d. assumption and the minimum model. No data fitting is used. The simulation parameters are chosen by hand to realize target CVs. The non-necessity proof effectively assumes an unstated freedom to choose Yn's distribution directly, which is not part of the model. No new entities are introduced.

free parameters (3)

hyperexponential parameter a = a = 5 and 10 in main runs; swept 1 to 100
Chosen by hand to control the coefficient of variation of the hyperexponential distribution; it is not fitted to data. Used in the non-necessity example and in simulations.
Erlang shape parameter k = k = 3 in fixed-CV comparison; swept 2 to 100
Chosen to set the CV for Erlang runs; a simulation setting, not fitted to data.
Uniform bounds a,b = a = 0, b = 2
Chosen so the uniform distribution has mean 1 and CV 1/sqrt(3), matching Erlang(3); a simulation setting, not fitted to data.

assumptions (3)

domain assumption Per-core execution times X1,...,Xn are i.i.d.
Section 3.1 states this. Real cores share memory hierarchy, OS jitter, and can be heterogeneous; independence and identical distributions are idealizations.
domain assumption Overall phase time is the minimum of the n core times.
Section 3.1 and Figure 1: the result of the fastest core is adopted and the others are terminated. This ignores overhead of launching and terminating cores and any communication cost.
standard math Minimum CDF formula for i.i.d. variables: F_Yn(y)=1-(1-F_X(y))^n.
Textbook order statistics, used in Proposition 3.1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A sufficient condition for a linear speedup in competitive parallel computing." pith.science (2026). https://pith.science/paper/5FUCLMHS

@misc{pith2026190807715,
  author       = {Pith},
  title        = {Pith review of: A sufficient condition for a linear speedup in competitive parallel computing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5FUCLMHS}},
  note         = {Machine review of arXiv:1908.07715}
}

read the original abstract

In competitive parallel computing, the identical copies of a code in a phase of a sequential program are assigned to processor cores and the result of the fastest core is adopted. In the literature, it is reported that a superlinear speedup can be achieved if there is an enough fluctuation among the execution times consumed by the cores. Competitive parallel computing is a promising approach to use a huge amount of cores effectively. However, there is few theoretical studies on speedups which can be achieved by competitive parallel computing at present. In this paper, we present a behavioral model of competitive parallel computing and provide a means to predict a speedup which competitive parallel computing yields through theoretical analyses and simulations. We also found a sufficient condition to provide a linear speedup which competitive parallel computing yields. More specifically, it is sufficient for the execution times which consumed by the cores to follow an exponential distribution. In addition, we found that the different distributions which have the identical coefficient of variation (CV) do not always provide the identical speedup. While CV is a convenient measure to predict a speedup, it is not enough to provide an exact prediction.

Figures

Figures reproduced from arXiv: 1908.07715 by the authors.

**Figure 1.** The execution times of a phase running on the different cores might be different each other if the cores are assigned to the different algorithms or the identical algorithm with the different parameters. The external factors including cache misses and network delay also produce the fluctuation of the execution times. These cause randomness. In order to model the execution of such a program, we denote the execution t… view at source ↗

**Figure 1.** A minimum model of competitive parallel computing (CPC) [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗

**Figure 2.** Speedup for various CVs linear speedup is achieved, which is identical to the exact solution mentioned in Section 4.2.2. With the distribution H2(5) (CV is 1.51), a speedup is 275.71 for n = 100. With the distribution H2(10) (CV is 1.62), a speedup is 521.15 for n = 100. These results show sufficient conditions for achieving superlinear speedups while these hyperexponential distributions might not reflect the behavi… view at source ↗

Figures from the paper (3 more)

**Figure 3.** Figure 3: Speedup for Erlang Distribution (n = 100) distribution 1 to 100 in [PITH_FULL_IMAGE:figures/full_fig_p012_3.png]

**Figure 4.** Figure 4: Speedup for Hyperexponetial Distribution ( [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]

**Figure 5.** Figure 5: Comparing speedups for the identical CV 5 Conclusion In this paper, we constructed a mathematical model which represents the behavior of competitive parallel computing and theoretically analyzed competitive parallel computing using the model. We investigate sufficient…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

Hill, M. D. and Marty, M. R. (2008): Amdahl’s law in the multicore era, Computer, 7: 33–38

work page 2008
[2]

and Tichy, W

Pankratius, V., Schaefer, C., Jannesari, A. and Tichy, W. F. (2008): Software engineering for multicore systems: an experience report, Pro- ceedings of the 1st international workshop on Multicore software engi- neering: 53–60

work page 2008
[3]

Patterson, D. A. and Hennessy, J. L. (2013): Computer organization and design: the hardware/software interface , Morgan Kaufmann, MA

work page 2013
[4]

E., Kumar, T

Cledat, R. E., Kumar, T. and Pande, S. (2011): Eﬃciently Speeding Up Sequential Computation Through the N-way Programming Model, Pro- ceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications : 537–554

work page 2011
[5]

(1992): Random competition: A simple, but eﬃcient method for parallelizing inference systems, Proceedings of the International Workshop Dagstuhl Castle : 195–209

Ertel, W. (1992): Random competition: A simple, but eﬃcient method for parallelizing inference systems, Proceedings of the International Workshop Dagstuhl Castle : 195–209

work page 1992
[6]

and Gross, T

Trachsel, O. and Gross, T. R. (2010): Variant-based Competitive Par- allel Execution of Sequential Programs, Proceedings of the 7th ACM International Conference on Computing Frontiers : 197–206

work page 2010
[7]

and Gross, T

Trachsel, O., Fischlin, C. and Gross, T. R. (2008): A platform for com- petitive execution, PESPMA 2008: 11–19

work page 2008
[8]

and Pande, S

Cledat, R., Kumar, T., Sreeram, J. and Pande, S. (2009): Opportunistic Computing: A New Paradigm for Scalable Realism on Many-cores, Pro- ceedings of the First USENIX Conference on Hot Topics in Parallelism : 1–6. 15

work page 2009

Show all 13 references

[9]

and Pande, S

Cledat, R. and Pande, S. (2010): Energy Eﬃciency via the N-way Model, Pespma 2010-Workshop on Parallel Execution of Sequential Programs on Multi-core Architecture

2010
[10]

Fushimi, M.: Probability and Stochastic Processes, Asakura Publishing (2004)

2004
[11]

Takahashi, Y.: Probability Theory, Asakura Publishing (2008)

2008
[12]

and Matsui, T.: Operations Research, Asakura Publishing (2004)

Mori, M. and Matsui, T.: Operations Research, Asakura Publishing (2004)

2004
[13]

F., Thompson, J

Gross, D., Shortle, J. F., Thompson, J. M. and Harris, C. M. (2008): Fundamentals of Queueing Theory , Wiley-Interscience, NJ. 16

2008

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Hill, M. D. and Marty, M. R. (2008): Amdahl’s law in the multicore era, Computer, 7: 33–38

work page 2008

[2] [2]

and Tichy, W

Pankratius, V., Schaefer, C., Jannesari, A. and Tichy, W. F. (2008): Software engineering for multicore systems: an experience report, Pro- ceedings of the 1st international workshop on Multicore software engi- neering: 53–60

work page 2008

[3] [3]

Patterson, D. A. and Hennessy, J. L. (2013): Computer organization and design: the hardware/software interface , Morgan Kaufmann, MA

work page 2013

[4] [4]

E., Kumar, T

Cledat, R. E., Kumar, T. and Pande, S. (2011): Eﬃciently Speeding Up Sequential Computation Through the N-way Programming Model, Pro- ceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications : 537–554

work page 2011

[5] [5]

(1992): Random competition: A simple, but eﬃcient method for parallelizing inference systems, Proceedings of the International Workshop Dagstuhl Castle : 195–209

Ertel, W. (1992): Random competition: A simple, but eﬃcient method for parallelizing inference systems, Proceedings of the International Workshop Dagstuhl Castle : 195–209

work page 1992

[6] [6]

and Gross, T

Trachsel, O. and Gross, T. R. (2010): Variant-based Competitive Par- allel Execution of Sequential Programs, Proceedings of the 7th ACM International Conference on Computing Frontiers : 197–206

work page 2010

[7] [7]

and Gross, T

Trachsel, O., Fischlin, C. and Gross, T. R. (2008): A platform for com- petitive execution, PESPMA 2008: 11–19

work page 2008

[8] [8]

and Pande, S

Cledat, R., Kumar, T., Sreeram, J. and Pande, S. (2009): Opportunistic Computing: A New Paradigm for Scalable Realism on Many-cores, Pro- ceedings of the First USENIX Conference on Hot Topics in Parallelism : 1–6. 15

work page 2009