{"id":"5a92f706-b1bd-4e38-9d83-cc4193991600","arxiv_id":"1908.02415","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A balanced block-design scheduling policy for redundant jobs with two service-time classes achieves perfect load balance in the urn model and lower queueing times in simulations than random or round-robin policies.","lead":"This paper studies how to assign redundant copies of computing jobs to servers when jobs can be short or long, and proposes a patterned assignment based on combinatorial designs. Simulations show the proposed assignment cuts average queueing delay by 10 to 50 percent compared with random and round-robin scheduling.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The only-arrival LBF/ROF/RDF indicators are an explicitly unproved proxy for queueing delay, and the validating simulations cover only two BIBD instances.","rationale":"The paper's own text admits the core bridge is a belief, so the central queueing-time claim is not established analytically. The indicator formulas are mostly transparent, but they are defined in a model without service, and no result proves their relevance to queueing delay. The positive simulations for two valid BIBD configurations support a weak version of the claim, but the narrow parameter sampling cannot rule out regimes where the proxy fails. This is exactly the reader's weakest assumption, and the recommended concrete test would settle it. The verdict should remain conditional: not rejected, because the simulations are consistent with the heuristic and the BIBD construction is valid for the tested cases, but not accepted as a general theorem without broader validation.","tokens_in":11391,"tokens_out":9499,"duration_ms":102913,"concrete_test":"Run a discrete-event queueing simulation over all small valid BIBD parameter sets (n=13,r=4; n=21,r=5; n=31,r=6; n=57,r=8; n=73,r=9), sweeping utilization from 0.3 to 0.95, p in {0.1,0.5,0.9}, q in {10,50}, with at least 100 independent replications per cell and confidence intervals on mean queueing time. Check whether BIBD is strictly better than random and round-robin in every cell and whether the ordering by LBF/ROF/RDF matches the delay ordering. If BIBD wins uniformly and the indicator ordering tracks delay, the analogy is supported; if any cell reverses, the central claim is overgeneralized.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the unexplained jump from Section III's urns-and-balls indicators to Section IV's queueing-delay claim. Section III-A states only a belief: 'We believe that a scheduling policy's capability of improving these indicators... is a good indicator of its performance in the actual queuing system.' No theorem connects LBF/ROF/RDF to mean delay; the indicators ignore service-time realization, cancellation dynamics, and the fact that a job waits only when all r selected servers are busy. The simulations are the entire bridge, and they test just two BIBD instances (n=13,r=4 and n=21,r=5), with no error bars and no systematic sweep of q, p, or utilization. Because a (n,r,1)-BIBD exists only for special parameters (n=r(r-1)+1 is necessary, not sufficient; e.g., r=7 gives no such design), these two points are a thin basis for a general ordering claim. Also, BIBD has the same ROF and RDF as random, so the claimed advantage over random rests on LBF alone, which is precisely the unproved predictor.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11602,"tokens_out":9634,"duration_ms":99092,"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":[{"comment":"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":"Section III-A"},{"comment":"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":"Section III-C, Proposition 1"},{"comment":"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":"Section III-F and Table I"},{"comment":"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":"Section III-E2"},{"comment":"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.","section":"Section IV"}],"minor_comments":[{"comment":"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":"Section III-B"},{"comment":"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":"Section III-C"},{"comment":"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.","section":"Section IV"},{"comment":"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":"General"},{"comment":"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.","section":"Section IV"}],"recommendation":"major_revision","confidential_remarks":"The idea is attractive and the simulations are suggestive, but the current manuscript's central claim rests on an explicitly unproved analogy and a very small number of simulation instances. I would push the authors to either prove a formal connection between the indicators and queueing delay, or expand the empirical study substantially so the heuristic is well supported. The unproved Proposition 1 should also be addressed before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The BIBD scheduling policy is a genuinely nice idea: use the blocks of a symmetric (n,r,1)-BIBD as the r-server subsets, selected in round-robin. For bi-modal job sizes, giving a small job a set of servers with bounded pairwise overlap protects it from being trapped behind one big job in every queue. The three indicators (LBF, ROF, RDF) are simple, and the calculations for random, round-robin, and BIBD mostly line up. I also give the authors credit for stating the heuristic explicitly: “We believe…” rather than smuggling the analogy in as a theorem. No constants are fitted, and the simulations are not cherry-picked to hit a target.\n\nThe soft spots are real but addressable. The analytical bridge from the urns-and-balls indicators to mean queueing delay is exactly one sentence of belief. The indicators ignore service-time realizations, the cancellation dynamics, and the fact that a job waits only when all r selected servers are busy. So the simulation section is the entire evidence base, yet it tests only two BIBD instances (n=13,r=4 and n=21,r=5), has no error bars, and does not sweep p, q, or utilization systematically. The generality claim is also too strong: an (n,r,1)-BIBD exists only for certain r (projective-plane orders), not for every r satisfying n=r(r-1)+1. There is a typo in Proposition 5: for BIBD, E[X] is (n+r-1)/n, not (n+r^2-1)/n, which makes the derivation momentarily confusing. Also, Fig. 8’s caption and text disagree about q (50 vs 15), and “reduces the queuing time by 100%” must mean 50%. Proposition 1’s proof is omitted.\n\nNone of these flaws sinks the paper. The simulations do show BIBD beating random and round-robin in the tested regimes, and the intuition is coherent. As a rigorous queueing analysis it is not there yet, but as a heuristic with a clean design idea and honest limits it is a useful contribution. I would send it to a conference or workshop on performance evaluation or scheduling, with revisions expected: full proofs, a comment about existence of BIBDs, and a broader simulation study.\n\nRecommendation: it deserves a serious referee—accept for peer review, not a desk reject.","headline":"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.","tokens_in":12110,"tokens_out":6388,"would_cite":false,"duration_ms":61459,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B05","60K25","68M20"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["redundancy scheduling","bi-modal job sizes","balanced incomplete block designs","non-adaptive scheduling","queueing time","load balancing","urns and balls","overlap diversity"],"falsifier":"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.","tokens_in":11209,"feed_emoji":"⏱️","tokens_out":9816,"duration_ms":105301,"temperature":0.7,"pith_summary":"This paper studies a distributed system where each arriving job is replicated to $r$ of $n$ servers and the losing copies are cancelled as soon as one copy starts service, with job sizes drawn from a bi-modal distribution of short or long exponential service times. It argues that for such workloads a scheduler must balance two things: spreading load evenly and diversifying the set of servers chosen for successive jobs so a short job is not trapped behind a long job in every queue it joins. To compare policies, the paper maps the arrival process to an urns-and-balls model and defines three indicators: the load balancing factor (LBF), redundancy overlap factor (ROF), and redundancy diversity factor (RDF). It claims that a policy based on balanced incomplete block designs (BIBD) achieves perfect load balancing and the best diversity of redundancy among the three non-adaptive policies studied, and that simulations show it reduces average queueing time relative to random and round-robin scheduling. If true, this gives a simple, stateless scheduling rule that improves latency in systems with two-speed jobs without inspecting queue lengths.","feed_headline":"Block-design server picks cut queueing delay for two-speed jobs","feed_subtitle":"A stateless schedule built from balanced incomplete block designs beats random and round-robin in bi-modal workload simulations.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the asymptotic approximation for the average maximum-loaded bin that the random-policy LBF formula in Lemma 1 is built on.","marker":"[28]"},{"why":"Supplies the companion asymptotic result for the average number of balls in a bin after T rounds of throwing r balls into n bins, also used in Lemma 1.","marker":"[29]"},{"why":"Defines balanced incomplete block designs and the parameter relation the proposed BIBD scheduler relies on.","marker":"[30]"},{"why":"Introduces the redundancy model in which copies are cancelled once the first copy starts service, the model adopted here.","marker":"[3]"},{"why":"Provides another analysis of redundancy with cancellation at first service start, supporting the choice of the queuing model.","marker":"[11]"},{"why":"Gives the service-time scaling model in which long jobs are q times slower than short jobs, used in the simulations.","marker":"[21]"},{"why":"Shows why exact queueing analysis with general job-size distributions is unreliable, motivating the indirect urns-and-balls performance indicators.","marker":"[24]"},{"why":"Supplies empirical evidence of bi-modal job service times in real cluster workloads, motivating the model.","marker":"[20]"}],"fun_headline_variants":["BIBD schedule trims queue lag for two-speed jobs","Balanced block design beats random, round-robin scheduling","Combinatorial scheduler cuts wait times in bi-modal queues","Symmetric BIBD slashes redundancy queueing delays"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["BIBD schedule trims queue lag for two-speed jobs","Balanced block design beats random, round-robin scheduling","Combinatorial scheduler cuts wait times in bi-modal queues","Symmetric BIBD slashes redundancy queueing delays"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000175,"raw_usage":{"total_tokens":1291,"prompt_tokens":959,"completion_tokens":332,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":575,"completion_tokens_details":{"reasoning_tokens":264}},"tokens_in":575,"tokens_out":332,"duration_ms":4242,"temperature":1.0,"reasoning_tokens":264,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:45:18.978978+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"A Short Note on the Average Maximal Number of Balls in a Bin","cited_arxiv_id":"1905.08933","evidence_quote":"Supplies the asymptotic approximation for the average maximum-loaded bin that the random-policy LBF formula in Lemma 1 is built on."},{"cited_title":"On the Average Maximal Number of Balls in a Bin Resulting from Throwing r Balls into n Bins T times","cited_arxiv_id":"1905.07827","evidence_quote":"Supplies the companion asymptotic result for the average number of balls in a bin after T rounds of throwing r balls into n bins, also used in Lemma 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines balanced incomplete block designs and the parameter relation the proposed BIBD scheduler relies on."},{"cited_title":"Efficient redundancy tech- niques for latency reduction in cloud systems,","cited_arxiv_id":null,"evidence_quote":"Introduces the redundancy model in which copies are cancelled once the first copy starts service, the model adopted here."},{"cited_title":"Delta probing policies for redundancy,","cited_arxiv_id":null,"evidence_quote":"Provides another analysis of redundancy with cancellation at first service start, supporting the choice of the queuing model."},{"cited_title":"A better model for job redundancy: Decoupling server slowdown and job size,","cited_arxiv_id":null,"evidence_quote":"Gives the service-time scaling model in which long jobs are q times slower than short jobs, used in the simulations."},{"cited_title":"On the inapprox- imability of m/g/k: why two moments of job size distribution are not enough,","cited_arxiv_id":null,"evidence_quote":"Shows why exact queueing analysis with general job-size distributions is unreliable, motivating the indirect urns-and-balls performance indicators."},{"cited_title":"Analysis and lessons from a publicly available google cluster trace,","cited_arxiv_id":null,"evidence_quote":"Supplies empirical evidence of bi-modal job service times in real cluster workloads, motivating the model."}],"review_version":1}