An analytical model for distributed tree searches can calculate expected completion times exactly for three of the five strategies it examines under its stated unknown-count and capacity-K models. In a separate multicore prototype limited to eight workers, the reported median speedups for S2 through S5 were 3.69, 3.03, 3.02 and 4.30, compared with unbounded-model predictions of 19.5, 4.5, 3.8 and 58.5.
The paper starts with a planning question: can expected completion time be estimated before a distributed search begins, so an operator can compare strategies? Its framework covers five strategies, two information conditions and three per-file capacity classes. The calculations use mixture corrections for scan times, conditioning on random layer widths, occupancy laws for signature placement, and computational routes for evaluating the results.
What the formulas can predict
In the unknown-count case, where each file has at most one signature, T1, T3 and T5 have exact expressions. T2 uses a plug-in estimate, meaning the model substitutes an average layer width, because its conditional expectation is nonlinear in width. In the capacity-K version, T1, T3 and T5 remain exact; T2 is still plug-in, while T4 combines plug-in with central-limit and extreme-value approximations. If K tends to infinity while 0 < p < 1, early termination becomes impossible and every node is searched.
When the number of signatures is known in advance, the model changes how it describes their distribution across files. At capacity one it uses a multivariate hypergeometric law, a probability rule for distributing a fixed total across files. At higher capacity, it distinguishes Bose-Einstein equal-composition placement from Maxwell-Boltzmann uniform placement, with both handled through a generating-function calculation.
Testing the shortcuts
To check the formulas, the study uses a discrete-event Monte Carlo simulator, with repeated computer simulations implementing the model and normally roughly 100,000 to 1 million replications. The simulator and scripts are available from the authors. The exact expressions matched simulation within Monte Carlo noise, with discrepancies under 0.1% in every tested configuration. One reported case predicted 2.6875 time units and simulated 2.6870.
The choice of occupancy rule mattered in validation. Hypergeometric occupancy matched simulations point by point, and its layer-time estimate was within 2% of the sampled result. The alternative uniform-composition law overstated the chance that the minimum count was zero by about fivefold and overstated layer time by 4%.
The weaker point was the plug-in route. Reported error for unknown-count T2 was 0.07% in the design example, 1.1% at the prototype setting and 74% in a cited subcritical case. The paper treats a model quantity written pni, when it is about 2 or more, as a heuristic threshold for using the exact alternative when the margin between strategies matters.
S4 gets a separate treatment. Its hybrid rule uses an asymptotic formula for larger cases, when the current layer has ni of at least 50 and the preceding layer has Mi-1 of at least 10, and a numerical route otherwise. Across n from 4 to 100 and M from 3 to 50, the numerical route stayed within 0.06% of simulation. The asymptotic error reached 3.3% at n = 4 and M = 5.
Speed is only one measure
Measured as speedup over S1, S2 and S5 improve fastest as fan-out, the number of branches, grows. S3 scales linearly, while S4 sits one fan-out power below full parallelism apart from a logarithmic correction. Only S3 and S4 can change order as tree depth H and fan-out n vary.
Using the paper's example settings of H = 4, n = 10 and p = 0.5, predicted and simulated completion times in full-file scan units were S1 1170.0 versus 1173.8, S2 4.0 versus 4.0, S3 156.0 versus 156.5, S4 35.2 versus 35.1, and S5 1.0 versus 1.0. Reservation costs for S1 through S5 were 1,170, 5,000, 1,560, 4,394 and 11,110. The example puts the latency and capacity trade-off in concrete terms: the fastest strategy also carried the largest reservation figure.
The prototype's numbers were lower than the unbounded predictions. With eight workers, median speedups over eight trees were 3.69 for S2, 3.03 for S3, 3.02 for S4 and 4.30 for S5. The prototype retained the broad S5-then-S2 ordering but did not distinguish S3 from S4. The analysis behind the design example took under a millisecond, compared with minutes for Monte Carlo.
A useful model with an open edge
One unresolved corner is the known-count version of S4. When a layer width meets the condition mi is at least rK, the required capacity-constrained distribution of the minimum count is not derived, so term-by-term averaging covers only widths that satisfy the regime used by the derivation. The prediction therefore remains incomplete for that part of the parameter space.
The document is an arXiv version 1 preprint dated 25 Aug 2026, with finalized journal and DOI details not reported in the supplied record. Its front matter says the work was based in part on the first author's 2022 doctoral dissertation and received no specific grant from public, commercial or not-for-profit funding agencies.
Paper data and sources
Original title: Probabilistic Performance Analysis of Parallel Signature Search Strategies in Multi-Level Tree Networks
Authors: Jingwei Li, Thomas G. Robertazzi
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text