REVIEW 5 major objections 5 minor 31 references
Redundancy Scheduling in Systems with Bi-Modal Job Service Time Distribution
T0 review · 5 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read A non-adaptive, stateless scheduler based on balanced incomplete block designs gives perfect load balance and the best overlap diversity in the urns-and-balls model, and simulations show it reduces queueing time for bi-modal workloads…
desk verdict BIBD scheduling is a neat idea with plausible simulation support, but the queueing claim rests on an explicitly unproved analogy and a thin set of experiments. 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 object is the symmetric balanced incomplete block design with $\lambda=1$, written $(n,r,1)$-BIBD: a collection of $n$ blocks, each of size $r$, over $n$ server labels such that every pair of labels appears together in exactly one block. The scheduler picks blocks cyclically, one per arriving job. The supporting machinery is the urns-and-balls analogy, in which $T$ arrivals place one ball in each of $r$ chosen urns, and the three indicators $LBF$, $ROF$, and $RDF$ defined from urn occupancies and overlap counts; the paper derives these indicators for each policy and uses their ranking to predict queueing performance.
What would settle it
Run the same queueing simulation with the long-job probability $p$ set to 0 or with $q=1$, so the service-time distribution is effectively exponential and bi-modality disappears; if BIBD no longer beats random and round-robin, the claimed benefit is driven by bimodality as the paper's mechanism asserts. Independently, record the empirical distribution of overlaps between the $r$-server sets assigned to consecutive jobs in the full queueing simulation and compare its first two moments with the paper's $ROF$ and $RDF$ formulas; disagreement would show the arrival-only indicators miss queue-dependent effects.
Extended reading notes
Core claim
The paper claims that, for a system of $n$ identical servers where each job is replicated to $r$ servers and extra copies are cancelled as soon as one copy enters service, the scheduling rule should be judged by two urns-and-balls indicators: load balance and overlap diversity. It proposes using the blocks of a symmetric $(n,r,1)$-BIBD, cycled in round-robin order, so that every pair of servers appears together in exactly one block and consecutive jobs share almost no servers. For $n = r(r-1)+1$, the paper derives closed-form values of $LBF$, $ROF$, and $RDF$ for random, round-robin, and BIBD scheduling: BIBD matches random on overlap diversity while reaching the perfect load balance of round-robin, and round-robin has strictly worse diversity. On this basis it concludes that BIBD provides perfect load balancing and the best performance in terms of diversity of redundancy among the three non-adaptive policies. Simulated queueing times then show BIBD below both alternatives across arrival rates, with the largest gains when long jobs are rare but very slow.
Load-bearing premise
The paper's queueing conclusions rest on the stated belief that a policy's load-balance and overlap-diversity indicators in an arrival-only urns-and-balls model predict its queueing time in the real system; if that analogy fails, the simulated advantages are not backed by the analysis.
Editorial extensions
If this is right
- A stateless scheduler can reduce average queueing time for bi-modal workloads without inspecting queue lengths or server loads, as long as it balances loads and controls overlap between consecutive jobs' server sets.
- BIBD scheduling inherits round-robin's perfect load balance when $n \mid T$ and random scheduling's overlap diversity, so it does not have to trade one objective for the other.
- Round-robin's weakness is not load balancing but overlap diversity: its $RDF$ is strictly smaller than BIBD's and shrinks as $r$ grows, predicting larger queueing losses at high redundancy.
- The simulations show larger BIBD gains when long jobs are rare but slow, meaning the policy is most valuable in exactly the skewed bi-modal regimes observed in real cluster workloads.
Reading between the lines
- Because $(n,r,1)$-BIBDs exist only for $n = r(r-1)+1$, practical deployment would need near-balanced or other design families; testing whether the indicators degrade gracefully when the exact balance condition is relaxed is a natural next step.
- The analogy's validity can be probed by measuring the actual overlap distribution inside the full queueing simulation and checking whether the first two moments track the paper's $ROF$ and $RDF$ formulas across different loads.
- The same LBF/ROF/RDF indicators could also rank adaptive policies against BIBD, offering a common language for comparing stateless and stateful schedulers on bi-modal workloads.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies non-adaptive redundancy scheduling in a system of n servers with bi-modal job service times. It develops an urns-and-balls analogy and defines three performance indicators (LBF, ROF, RDF), evaluates random and round-robin policies in that model, proposes a scheduling policy based on symmetric balanced incomplete block designs (BIBDs), and reports simulation results which indicate that the BIBD policy reduces mean queueing time compared with random and round-robin scheduling. The paper's central assertion is that the BIBD policy combines perfect load balancing with good diversity of redundancy and therefore outperforms the two classical non-adaptive policies.
Significance. If the heuristic analogy is accepted, the paper offers a simple, elegant non-adaptive policy with closed-form indicator values and demonstrates potentially large queueing-time gains in simulation. The indicator definitions are parameter-free, no constants are fitted to the simulation data, and the BIBD construction is a clean combinatorial idea with exact load balancing by design. The paper also makes the useful observation that round-robin scheduling, despite perfect average load balance, is poor at diversifying the server sets of consecutive jobs. The main limitation is that the analytical bridge from the urns-and-balls indicators to actual queueing delay is explicitly stated only as a belief, and the validating simulations cover just two BIBD instances. The current manuscript is therefore best read as a promising heuristic plus a narrow simulation study rather than a proven scheduling result.
major comments (5)
- [Section III-A] The entire analytical comparison rests on the sentence 'We believe that a scheduling policy's capability of improving these indicators in the only-arrival system is a good indicator of its performance in the actual queuing system.' No theorem or formal scaling argument connects LBF/ROF/RDF to mean queueing time, and the indicators ignore the service-time realization, the cancellation dynamics, and the fact that a job waits only when all r selected servers are busy. A further load-bearing issue is that LBF in Definition 1 depends on an unspecified horizon T; for fixed n and r, the random-policy LBF in Lemma 1 tends to 1 as T grows, so the finite-horizon LBF advantage of BIBD over random disappears in the limit. The authors should either prove a formal connection (e.g., in a heavy-traffic or asymptotic regime) or substantially expand the simulation evidence, including a sweep of p, q, utilization, n, and r, to establish the analogy empirically.
- [Section III-C, Proposition 1] The formulas ROF_rand = n/r^2 and RDF_rand = n(n-1)/(r^2(n+r(r-2))) in Proposition 1 are stated with 'The proof is omitted because of the space constraint.' These formulas are load-bearing because Table I uses them to conclude that random has the same ROF as round-robin/BIBD and the same RDF as BIBD. An omitted proof is not acceptable for a core analytical result; please provide a full proof or an explicit reference that contains it.
- [Section III-F and Table I] The text claims that BIBD 'has the best performance in terms of diversity of redundancy,' but this is contradicted by Table I: RDF_BIBD = RDF_random = ((r-1)^2+r)/(r(2r-1)), and all three policies have the identical ROF. The only indicator on which BIBD strictly exceeds random is LBF. Thus the paper's own indicators attribute BIBD's queueing-time advantage over random to load balancing, not diversity. The narrative should be corrected to match the table, or a different notion of diversity should be defined and justified.
- [Section III-E2] The paper notes that a (n,r,1)-BIBD is not possible for arbitrary parameters but does not state the concrete restriction: a symmetric (n,r,1)-BIBD is a projective plane of order r-1, known to exist for prime-power orders and not known to exist in general, with order 6 (r=7) known to be impossible. Since n = r(r-1)+1 is necessary but not sufficient, the proposed policy is unavailable for many values of r, and the simulations only instantiate r=4 and r=5. This restriction should be stated explicitly, and its practical impact on the claimed general superiority of BIBD scheduling should be discussed.
- [Section IV] The queueing-time claim rests entirely on the simulations, but the simulation study is narrow: only (n,r) = (13,4) and (21,5), four (q,p) settings, and no information about run length, number of independent replications, warm-up period, or statistical error. The reported improvements of 10-20% could be within simulation noise. Please add confidence intervals or error bars, report full experimental details, and ideally sweep the arrival rate, p, q, and the available (n,r) combinations.
minor comments (5)
- [Section III-B] In Definition 1, the order statistics N^T_{1:n} and N^T_{n:n} should be explicitly identified as the minimum and maximum occupancy; currently the notation is introduced only verbally.
- [Section III-C] The use of 'max{0,...}' inside the asymptotic limit in equation (5) is informal; a statement about finite-n approximations with error bounds would be clearer.
- [Section IV] The captions of Figures 5-8 do not state which subfigure corresponds to low versus high arrival rate; please label the subfigures or clarify in the captions.
- [General] There are several typos and stylistic issues: 'experiment1' should be 'experiment 1'; 'when jobs' service time are is bi-modal'; 'distributions..'; and 'it's performance' in Section III-A should be 'its performance'.
- [Section IV] The simulation section does not state whether the simulator code or seeds are available; for a simulation-based central claim, a reproducibility statement would be helpful.
Circularity Check
No circularity: BIBD is deliberately designed to optimize the paper's own indicators, but the queueing-time claim rests on independent simulations, not on the indicator definitions.
full rationale
The derivation chain does not reduce to its own inputs. The urns-and-balls indicators LBF/ROF/RDF are defined independently of the queueing metric, and the values for random, round-robin, and BIBD are derived from the policies' combinatorial properties rather than fitted to queueing data. BIBD is deliberately constructed to balance loads (by cycling through blocks) and to minimize pairwise overlap (via lambda=1), so the favorable indicator values follow from that design choice; this is construction, not circular prediction. The central queueing-time claim is not derived from the indicators alone: Section IV tests the policies by explicit simulation under four parameter tuples, and the paper itself marks the indicator-to-delay connection as a belief in Section III-A ('We believe that a scheduling policy's capability of improving these indicators in the only-arrival system is a good indicator of it's performance in the actual queuing system'). That is an acknowledged, unproved heuristic and an evidentiary limitation, not a circular step. The only self-citation used in an analytical step is [29] for the asymptotic random-LBF formula in Lemma 1; this is a peripheral supporting calculation, not a load-bearing uniqueness argument or a renamed prediction. No fitted parameters are presented as predictions, and no result is imported from the authors' prior work to forbid alternatives. The paper's main weakness is the gap between the proxy indicators and actual queueing delay, plus the small number of simulated BIBD instances; those are validation concerns, not circularity.
Assumptions & free parameters
assumptions (4)
- domain assumption Only-arrival urns-and-balls indicators (LBF, ROF, RDF) predict queueing time of the real system.
- standard math The asymptotic maximum and minimum loaded urn formulas from [28] and [29] approximate finite-n, finite-T random scheduling.
- domain assumption A symmetric (n,r,1)-BIBD exists whenever n = r(r-1) + 1.
- domain assumption Bi-modal service-time model: short jobs are exponential with rate mu1, long jobs are exponential with rate mu1/q, job type probability is p, and each copy samples the job's service-time distribution.
Cite this review
Pith. "Pith review of Redundancy Scheduling in Systems with Bi-Modal Job Service Time Distribution." pith.science (2026). https://pith.science/paper/5LA26LFN
@misc{pith2026190802415,
author = {Pith},
title = {Pith review of: Redundancy Scheduling in Systems with Bi-Modal Job Service Time Distribution},
year = {2026},
howpublished = {\url{https://pith.science/paper/5LA26LFN}},
note = {Machine review of arXiv:1908.02415}
}
read the original abstract
Queuing systems with redundant requests have drawn great attention because of their promise to reduce the job completion time and variability. Despite a large body of work on the topic, we are still far from fully understanding the benefits of redundancy in practice. We here take one step towards practical systems by studying queuing systems with bi-modal job service time distribution. Such distributions have been observed in practice, as can be seen in, e.g., Google cluster traces. We develop an analogy to a classical urns and balls problem, and use it to study the queuing time performance of two non-adaptive classical scheduling policies: random and round-robin. We introduce new performance indicators in the analogous model, and argue that they are good predictors of the queuing time in non-adaptive scheduling policies. We then propose a non-adaptive scheduling policy that is based on combinatorial designs, and show that it has better performance indicators. Simulations confirm that the proposed scheduling policy, as the performance indicators suggest, reduces the queuing times compared to random and round-robin scheduling.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[1]
The tail at scale,
J. Dean and L. A. Barroso, “The tail at scale,” Communications of the ACM, vol. 56, no. 2, pp. 74–80, 2013
2013
-
[2]
On the delay-storage trade-off in content download from coded distributed storage systems,
G. Joshi, Y . Liu, and E. Soljanin, “On the delay-storage trade-off in content download from coded distributed storage systems,” IEEE Journal on Selected Areas in Communications , vol. 32, no. 5, pp. 989–997, 2014
2014
-
[3]
Efficient redundancy tech- niques for latency reduction in cloud systems,
G. Joshi, E. Soljanin, and G. Wornell, “Efficient redundancy tech- niques for latency reduction in cloud systems,” ACM Transactions on Modeling and Perform. Eval. of Computing Systems (TOMPECS) , vol. 2, no. 2, p. 12, 2017
work page 2017
-
[4]
Speeding up distributed machine learning using codes,
K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchan- dran, “Speeding up distributed machine learning using codes,” IEEE Transactions on Information Theory , vol. 64, pp. 1514–1529, 2017
work page 2017
-
[5]
Comet: batched stream processing for data intensive distributed computing,
B. He, M. Yang, Z. Guo, R. Chen, B. Su, W. Lin, and L. Zhou, “Comet: batched stream processing for data intensive distributed computing,” in Proceedings of the 1st ACM symposium on Cloud computing. ACM, 2010, pp. 63–74
work page 2010
-
[6]
J. Bernardin, P. Lee, and J. Lewis, “Using execution statistics to select tasks for redundant assignment in a distributed computing platform,” Aug. 15 2006, uS Patent 7,093,004
work page 2006
-
[7]
Redundancy-d: The power of d choices for redundancy,
K. Gardner, M. Harchol-Balter, A. Scheller-Wolf, M. Velednitsky, and S. Zbarsky, “Redundancy-d: The power of d choices for redundancy,” Operations Research, vol. 65, no. 4, pp. 1078–1094, 2017
work page 2017
-
[8]
Effec- tive straggler mitigation: Attack of the clones,
G. Ananthanarayanan, A. Ghodsi, S. Shenker, and I. Stoica, “Effec- tive straggler mitigation: Attack of the clones,” in Presented as part of the 10th{USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 13), 2013, pp. 185–198
work page 2013
Show all 31 references
-
[9]
Straggler mitigation at scale,
M. F. Aktas and E. Soljanin, “Straggler mitigation at scale,” arXiv preprint arXiv:1906.10664, 2019
1906 arXiv
-
[10]
On the effect of task-to-worker assignment in distributed computing systems with stragglers,
A. Behrouzi-Far and E. Soljanin, “On the effect of task-to-worker assignment in distributed computing systems with stragglers,” in2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 2018, pp. 560–566
2018
-
[11]
Delta probing policies for redundancy,
Y . Raaijmakers, S. Borst, and O. Boxma, “Delta probing policies for redundancy,” Perform. Eval. Rev., vol. 127, pp. 21–35, 2018
2018
-
[12]
Load sharing in distributed systems,
Y .-T. Wang et al., “Load sharing in distributed systems,” IEEE Trans. on Computers, vol. 100, no. 3, pp. 204–217, 1985
1985
-
[13]
Exploiting process lifetime distributions for dynamic load balancing,
M. Harchol-Balter and A. B. Downey, “Exploiting process lifetime distributions for dynamic load balancing,” in ACM SIGMETRICS Perform. Eval. Rev., vol. 24, 1996, pp. 13–24
1996
-
[14]
Bansal and M
N. Bansal and M. Harchol-Balter, Analysis of SRPT scheduling: Investigating unfairness. ACM, 2001, vol. 29, no. 1
2001
-
[15]
Classifying scheduling policies with respect to higher moments of conditional response time,
A. Wierman and M. Harchol-Balter, “Classifying scheduling policies with respect to higher moments of conditional response time,” ACM SIGMETRICS Perform. Eval. Rev. , vol. 33, pp. 229–240, 2005
2005
-
[16]
R- storm: Resource-aware scheduling in storm,
B. Peng, M. Hosseini, Z. Hong, R. Farivar, and R. Campbell, “R- storm: Resource-aware scheduling in storm,” in Proceedings of the 16th Annual Middleware Conference . ACM, 2015, pp. 149–161
2015
-
[17]
Learning effective straggler mitigation from experience and modeling,
M. F. Aktas and E. Soljanin, “Learning effective straggler mitigation from experience and modeling,” in CodML (ICML Workshop), 2019
2019
-
[18]
Analysis of join- the-shortest-queue routing for web server farms,
V . Gupta, M. H. Balter, K. Sigman, and W. Whitt, “Analysis of join- the-shortest-queue routing for web server farms,” Perform. Eval. Rev., vol. 64, no. 9-12, pp. 1062–1081, 2007
2007
-
[19]
On choosing a task assignment policy for a distributed server system,
M. Harchol-Balter, M. E. Crovella, and C. Murta, “On choosing a task assignment policy for a distributed server system,” 1998
1998
-
[20]
Analysis and lessons from a publicly available google cluster trace,
Y . Chen, A. S. Ganapathi, R. Griffith, and R. H. Katz, “Analysis and lessons from a publicly available google cluster trace,” 2010
2010
-
[21]
A better model for job redundancy: Decoupling server slowdown and job size,
K. Gardner, M. Harchol-Balter, A. Scheller-Wolf, and B. Van Houdt, “A better model for job redundancy: Decoupling server slowdown and job size,” IEEE/ACM transactions on networking , vol. 25, no. 6, pp. 3353–3367, 2017
2017
-
[22]
Approximations for the m/g/m queue,
P. Hokstad, “Approximations for the m/g/m queue,” Operations Research, vol. 26, no. 3, pp. 510–523, 1978
1978
-
[23]
Diffusion approximation for an m/g/m queue,
T. Kimura, “Diffusion approximation for an m/g/m queue,” Opera- tions Research, vol. 31, no. 2, pp. 304–321, 1983
1983
-
[24]
On the inapprox- imability of m/g/k: why two moments of job size distribution are not enough,
V . Gupta, M. Harchol-Balter, J. Dai, and B. Zwart, “On the inapprox- imability of m/g/k: why two moments of job size distribution are not enough,” Queueing Systems, vol. 64, no. 1, pp. 5–48, 2010
2010
-
[25]
Reducing latency via redundant requests: Exact analysis,
K. Gardner, S. Zbarsky, S. Doroudi, M. Harchol-Balter, and E. Hyy- tia, “Reducing latency via redundant requests: Exact analysis,” ACM SIGMETRICS Perform. Eval. Rev. , vol. 43, pp. 347–360, 2015
2015
-
[26]
“balls into bins
M. Raab and A. Steger, ““balls into bins”—a simple and tight analy- sis,” in International Workshop on Randomization and Approximation Techniques in Computer Science . Springer, 1998, pp. 159–170
1998
-
[27]
Balls and bins: A study in negative dependence,
D. Dubhashi and D. Ranjan, “Balls and bins: A study in negative dependence,” Random Structures & Algorithms , vol. 13, no. 2, pp. 99–124, 1998
1998
-
[28]
A short note on the average maximal number of balls in a bin,
M. Michelen, “A short note on the average maximal number of balls in a bin,” arXiv preprint arXiv:1905.08933 , 2019
1905 arXiv
-
[29]
On the average maximal number of balls in a bin resulting from throwing r balls into n bins t times,
A. Behrouzi-Far and D. Zeilberger, “On the average maximal number of balls in a bin resulting from throwing r balls into n bins t times,” arXiv preprint arXiv:1905.07827 , 2019
1905 arXiv
-
[30]
D. R. Stinson, Combinatorial designs: constructions and analysis . Springer Science & Business Media, 2007
2007
-
[31]
Scheduling with bibd,
E. Catania and D. Burke, “Scheduling with bibd,” http://reu.dimacs.rutgers.edu/ ecatania/, 2018
2018
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.