Peer-to-peer file distribution splits a file into chunks that peers trade with each other, so download capacity grows as more people join. A known way this fails is the missing piece syndrome. Peers leave as soon as they finish, so one chunk becomes scarce. Everyone else ends up holding the same set of common chunks, which leaves them nothing useful to trade. All of them then wait on the original uploader (the "seed"). Every stability result for this failure, and every scheduling rule that cures it, assumes that all chunks cost the same to move. Real workloads break that assumption. Variable-bitrate video segments differ in size. Shards of a model checkpoint can vary by orders of magnitude. Chunks held in different cloud storage tiers carry different egress prices. The bandit and Bayesian-optimization literature has studied for years what happens when unequal evaluation costs are ignored, and what happens when they are handled naively.
This note proposes to carry that lesson into swarm scheduling. In black-box optimization, a cost-normalized greedy rule ("value divided by cost") steers learners into cheap regions and starves the expensive ones. We claim the same thing happens in swarms. A cost-normalized rule makes the expensive chunk the missing piece by construction. A cost-blind rule is not safe either, because the stability threshold it inherits is set by the single most expensive chunk. We will derive the stability boundary for swarms with heterogeneous chunk costs. We will then design a cost-weighted version of mode suppression that stays stable at every arrival rate while paying for expensive chunks only when scarcity requires it, and test both claims against the existing chunk-sharing simulators.
Core Claim
The uniform-cost assumption hides a specific failure. Suppose chunk $k$ takes $s_k$ units of upload time, and the seed has upload rate $U_s$ that it spreads evenly across chunks. The seed then injects chunk $k$ at a rate proportional to $U_s/s_k$. Meanwhile, new peers join a growing "one-club" (peers that hold everything except chunk $k$) at the arrival rate $\lambda$, regardless of cost. A flow-counting argument in the style of Stability of a Peer-to-Peer Communication System therefore predicts the following for random-useful or rarest-first scheduling with a uniform seed. The swarm's critical arrival rate is set by the largest $s_k$ rather than the average. Once $\lambda$ exceeds that threshold, the most expensive chunk is the one that goes missing.
Making peers cost-aware in the obvious way makes this worse. Consider a peer that ranks requests by rarity per unit cost, the swarm analogue of Expected Improvement per unit cost. Expected Improvement per unit cost divides the expected gain of an evaluation by its cost, and A Nonmyopic Approach to Cost-Constrained Bayesian Optimization showed it locks onto cheap points and never reaches an expensive optimum. A peer using the analogous rule postpones the expensive chunk. Many peers doing the same thing synchronize on the cheap subset, which is exactly the one-club state. Our claim has two parts. First, these two thresholds can be stated in closed form. Second, a mode-suppression rule whose suppression threshold is scaled by chunk cost restores stability at all arrival rates, while spending less total transfer cost than count-based mode suppression applied to the same heterogeneous file.
Prior Work and How This Differs
The P2P side supplies both the failure mode and the mechanism we build on. The missing piece syndrome in peer-to-peer communication and Stability of a Peer-to-Peer Communication System model a swarm as a Markov chain. They identify when the swarm is stable versus when it explodes, and they show that letting peers stay long enough to upload one extra piece restores stability. Both treat all pieces as interchangeable unit-time transfers, and we relax exactly that.
Mode-Suppression supplies the method we extend. In mode suppression, peers stop sending the most common chunk once its count exceeds the rarest by a threshold $T$. The paper uses Lyapunov drift arguments to prove stability at every arrival rate, sets $T=2m$ empirically, and leaves its sampled-neighbor variant unproven for more than two chunks. Rarest-First With Probabilistic-Mode-Suppression softens the suppression to recover flash-crowd speed, using a tuning weight $\beta_w\approx1.5$ found by simulation. Both suppress by replica count. Under unequal costs, a count gap on an expensive chunk takes much longer to close than the same gap on a cheap one, so a count threshold is the wrong trigger.
Rarest First and Choke Algorithms Are Enough acts as a constraint on our claims. It found near-perfect piece diversity in 70–80% of 26 real torrents. We must therefore show that the cost-heterogeneous failure appears in regimes those torrents did not exercise, namely non-persistent peers, high arrival rates, and skewed chunk sizes. It is not enough to say rarest-first is fragile in general. Heterogeneous download times in a homogeneous BitTorrent swarm shows that completion times spread out even when peers are identical. That warns us to separate the spread caused by cost from the spread caused by randomness.
The cost-aware optimization side supplies the diagnosis and one design principle. A Nonmyopic Approach to Cost-Constrained Bayesian Optimization motivates the claim that ratio rules starve expensive options. We borrow its observation that the right policy treats cheap actions as a means to an end and must eventually pay for the expensive one. We do not reuse its rollout planner, because a per-peer rollout over swarm states is too heavy for a scheduling rule. Cost-aware Stopping for Bayesian Optimization and Balancing Performance and Costs in Best Arm Identification give principled rules for when paying more is no longer worth it. We use them only in a secondary experiment on when a stalled peer should pay for a server download. Neither line of work considers many agents whose individually rational cost-aware choices synchronize. That collective effect is the new object here.
Research Program
The first part is analytical. We extend the Hajek–Zhu Markov model to chunks with transfer times $s_1,\dots,s_m$. Here a peer's upload of chunk $k$ takes time $s_k$, peers arrive at rate $\lambda$, and peers leave immediately on completion. We derive transience and positive-recurrence conditions under three regimes: uniform-random seed allocation, cost-proportional seed allocation, and the cost-per-rarity peer rule. The expected result is a threshold of the form $\lambda^\ast \propto U_s/\max_k s_k$ for the cost-blind seed. With cost-proportional seed allocation, the threshold should rise toward the mean cost, but it should remain finite. That finite ceiling is why seed-side fixes alone cannot match mode suppression's guarantee of stability at every arrival rate.
The second part is the algorithm. In cost-weighted mode suppression, a peer withholds chunk $j$ when
$$c_j\,(N_j - N_{\min}) > T\,\bar c,$$
where $N_j$ is the number of peers holding chunk $j$, $N_{\min}$ is the count of the rarest chunk, $c_j$ is the transfer cost of chunk $j$, $\bar c$ is the mean chunk cost, and $T$ is the existing mode-suppression threshold. Requests otherwise follow rarest-first, ranked by count rather than by count per cost. This deliberately reverses the ratio heuristic. A cheap chunk can run far ahead of the others at little cost to anyone. An expensive chunk that runs ahead ties up a great deal of upload time, so suppression triggers on it sooner. We will attempt a Lyapunov drift proof that extends the mode-suppression argument with cost-weighted chunk counts. We will also test a sampled-neighbor version that uses three peers, as in the distributed variant.
The third, smaller part asks when a peer stuck on the last expensive chunk should pay a server. We adapt the stopping rule from Cost-aware Stopping for Bayesian Optimization, which halts when the expected benefit of waiting no longer exceeds its cost. Here the costs are expected waiting time versus server egress price. We compare this rule against "never fall back" and "fall back immediately."
Baselines
The naive reference point is random-useful-piece selection with a uniform seed, the setting analyzed in Stability of a Peer-to-Peer Communication System. It fixes where instability should begin and lets us check the derived threshold numerically. The second baseline is plain cost-blind rarest-first, which Rarest First and Choke Algorithms Are Enough argues is sufficient in practice. It is the baseline a practitioner would actually deploy. The third baseline is rarest-first ranked by rarity per unit cost, the swarm analogue of Expected Improvement per unit cost. We include it because our central prediction is that it fails worst.
The strongest existing competitors are count-based mode suppression with $T=2m$ and its sampled-neighbor variant from Mode-Suppression, and RFwPMS with $\beta_w\approx1.5$ from RFwPMS. RFwPMS is the most direct threat. It is already stable and fast on equal-cost files, and it may tolerate cost skew well without any change. We found no reported sojourn-time values on Lacuna for mode suppression or RFwPMS. The file reports only qualitative results: sojourn time independent of $\lambda$ for mode suppression, and download time linear in file size for RFwPMS. For that reason we will rerun both in the same discrete-event simulator rather than compare against published figures.
For fairness, every method runs on identical arrival traces, chunk-cost profiles, seed rates, and random seeds. Every tunable parameter ($T$, $\beta_w$, and our cost-scaled threshold) gets the same grid-search budget on a held-out set of cost profiles. "Beating" RFwPMS means two things. First, at arrival rates where RFwPMS is stable, our rule must show lower mean sojourn time or lower total transfer cost, with non-overlapping confidence intervals across at least 20 seeds. Second, our rule must stay stable at arrival rates where RFwPMS's queue grows without bound.
Two ablations isolate the key ingredient. One applies cost-proportional allocation at the seed only and leaves peers unchanged. The other uses our threshold with $c_j$ replaced by $\bar c$, which recovers count-based mode suppression on the same code path. Random linear network coding serves as an upper reference for sojourn time. Network coding mixes chunks so that no chunk identity can go missing. We report it with its decoding cost and do not count it as a competitor to beat.
Why not just…?
Why not just use network coding, which removes chunk identity altogether? Coding does dissolve the missing piece, as Stability of a Peer-to-Peer Communication System notes. But Rarest First and Choke Algorithms Are Enough and Network Coding Meets Multimedia: A Review report high decoding cost and exposure to pollution attacks, where one corrupted packet spoils every combination built from it. With heterogeneous chunks, coding also requires padding or mixing blocks of unequal size, which inflates the cost of the cheap ones. We will report coded sojourn time alongside decode work, so a reader can see what our rule gives up and what it saves.
Why not just make peers stay a little longer after finishing? This is a real threat. Zhu and Hajek showed that a dwell time sufficient to upload one extra piece gives stability. Under heterogeneous costs, our analysis predicts the required dwell is measured in units of the expensive chunk. We will compute this cost-adjusted dwell and simulate it. If a modest dwell, expressed in mean-chunk units, stabilizes every profile we test, the contribution shrinks to the threshold analysis. Our rule would then matter only in settings where peers cannot be compelled to stay, and we will state that plainly.
Why not just have the seed spend more time on expensive chunks? That is the cheapest fix, and we test it directly as an ablation. Our argument predicts it raises the instability threshold but cannot remove it. The one-club grows at rate $\lambda$, while any seed injects at a bounded rate. If simulations show seed-only allocation staying stable well beyond any realistic arrival rate, we will reframe the result as a seed-allocation rule.
Why not just keep RFwPMS, which already balances stability and speed? RFwPMS may tolerate moderate cost skew. Our prediction is that its count-based trigger misfires once chunk costs differ by roughly an order of magnitude. The head-to-head sweep over cost skew below tests exactly that. If RFwPMS matches our rule across the full sweep, the cost-weighted threshold is unnecessary.
Proposed Experiments
All experiments use the discrete-event chunk-sharing simulator from the mode-suppression and RFwPMS papers, in single-swarm and multi-swarm settings. We add per-chunk transfer times drawn from three profiles: uniform (a sanity check reproducing published qualitative behavior), lognormal with variance swept from mild to two orders of magnitude, and a two-class profile with one heavy chunk, which isolates the predicted failure. No dataset in the file records per-chunk cost heterogeneity. The Legout trace set records arrival patterns and swarm sizes but not chunk sizes. We will therefore use it only to set realistic arrival bursts and neighbor counts (up to 80), and we label all cost profiles as synthetic.
The metrics are as follows. We measure stability empirically as the slope of swarm population over a long horizon, alongside mean and tail sojourn time as a function of $\lambda$. We measure the fraction of time a one-club exists and which chunk it is missing, and total transfer cost per completed download. For the fallback study, we additionally measure server egress cost against stall time.
Three checks decide the proposal. The first is whether the simulated instability point for cost-blind rarest-first tracks the predicted $U_s/\max_k s_k$ scaling as the heavy chunk grows. If it tracks the mean cost instead, the core claim is wrong. The second is whether the cost-per-rarity rule produces one-clubs missing the expensive chunk at a higher rate than cost-blind rarest-first, which tests the transfer of the ratio-heuristic failure mode. The third is whether cost-weighted mode suppression remains stable at every tested arrival rate on the heavy-chunk profile while RFwPMS and count-based mode suppression do not, and whether it uses less total transfer cost than count-based mode suppression where both are stable. If the first and third checks fail, the cost dimension adds nothing beyond existing protocols, and we will say so.
References
- Stability of a Peer-to-Peer Communication System
- A Nonmyopic Approach to Cost-Constrained Bayesian Optimization
- The missing piece syndrome in peer-to-peer communication
- Mode-Suppression: A Simple, Stable and Scalable Chunk-Sharing Algorithm for P2P Networks
- Rarest-First With Probabilistic-Mode-Suppression (RFwPMS)
- Rarest first and choke algorithms are enough
- Heterogeneous download times in a homogeneous BitTorrent swarm
- Cost-aware Stopping for Bayesian Optimization
- Balancing Performance and Costs in Best Arm Identification
- Network Coding Meets Multimedia: a Review