Satellites and drones that need a neural network's answer within tens of milliseconds cannot wait for a round trip to a ground data center. One option is to split the heavy linear algebra of a model layer across whichever neighbors are currently in radio range. Coded computing makes this robust to slow or missing helpers. Each helper computes a few redundant combinations of the work, and the requester rebuilds the full answer from whichever subset returns first. Two costs undermine this in mobile networks. First, the codes with the best guarantees work over large finite fields, so decoding is expensive on a small onboard computer. Second, the helpers available to a moving node change every few seconds. A code designed for a fixed cluster stalls when the planned helpers fly out of range.
This note proposes a different starting point. In orbital and road-constrained networks, when each helper will be reachable is largely predictable from known trajectories. We use that prediction to design the code itself. Each helper receives a short stream of tasks, and each task is a plain sum of a few rows of the weight matrix. The coefficients are only 0 and 1, so decoding needs nothing but subtractions. The assignment is chosen so that the results expected to arrive before each link closes can be decoded by simple back-substitution. The open question is whether foreknowledge of the topology lets a binary, subtraction-only code match or beat randomly designed fountain codes and large-field polynomial codes on deadline-meeting probability. Such a code would also cost far less to decode.
Core Claim
The claim has three parts. First, in networks with predictable link schedules, the sparse binary structure of a coded computation should be designed jointly with the predicted contact plan. A contact plan is the timetable of which links exist when, with their capacities. Second, a design of this kind can deliver the any-subset, partial-work-harvesting behavior of rateless codes with lower reception overhead at small and moderate task counts. Third, it keeps the numerically exact, cheap decoding that binary schemes offer.
The new ingredient is neither binary coding nor topology prediction alone. It is using the predicted reachability of each helper as the input to code construction. This differs from three kinds of prior work. Rateless schemes draw their sums at random. Fixed binary allocations assume a static cluster. Elastic codes handle membership changes but over general fields and with matrix-inversion decoding.
The three research directions play distinct roles. Field-size complexity supplies the mechanism: avoiding extension-field arithmetic and floating-point inversion entirely. Dynamic topology management supplies the regime and the side information: contact windows computed from orbital elements or road-constrained trajectories. Centralized processing latency supplies the constraint and the naive reference point. That reference is shipping the computation to a ground cloud, together with the requirement that decoding on the requesting node must not eat the time that offloading saved.
Research Program
The workload is distributed linear inference $y = Wx$. Here $W$ is a model's weight matrix split into $k$ row blocks, and $x$ is the input feature vector. We restrict to linear layers because the strongest systems baselines are also linear-only. The requesting node, called the master, has a deadline $D$ and a predicted contact plan. For each candidate helper $j$, the plan gives a window $[a_j, b_j]$ during which helper $j$ is reachable, plus a link rate. A model of compute speed, drawn from measured delay profiles, then yields a distribution over how many coded results helper $j$ can return before $\min(b_j, D)$.
A code is a binary matrix $G \in \{0,1\}^{m \times k}$. Each row of $G$ is one coded task, the sum of the selected blocks of $W$ multiplied by $x$. Each task is assigned to a helper and given a position in that helper's streaming order. Decoding is peeling: repeatedly find a received result that involves one unknown block, solve for that block by subtraction, and propagate. When peeling stalls, a small inactivation step finishes the job, as in Rateless Codes for Low-Latency Distributed Inference in Mobile Edge Computing. Coefficients are only 0 and 1 over the reals, so no quantization into a finite field and no division is needed. This avoids the overflow and conditioning problems that Numerically Stable Binary Coded Computations documents for pseudo-inverse gradient coding.
The design objective is
$$ \max_{G,\ \pi} \ \Pr_{\omega}\big[\,\mathrm{Peel}\big(G_{R(\pi, D, \omega)}\big) = \text{all } k \text{ blocks}\,\big] \;-\; \lambda\, C_{\mathrm{dec}}(G). $$
In this objective, $\pi$ is the assignment and ordering of tasks to helpers. The variable $\omega$ is a random scenario for compute times and contact-plan errors. $R(\pi, D, \omega)$ is the set of task results received by the deadline under that scenario. $C_{\mathrm{dec}}$ is the expected decoding work, counted as the number of block subtractions plus the size of any inactivation core. The weight $\lambda$ trades decoding work against recovery probability.
We will solve this objective with sampled scenarios and a greedy constructor. The constructor adds coded rows in order of predicted arrival time. It chooses each row's support so that it reduces the expected stall set across the sampled scenarios. The rows are then ordered so that results late in a helper's stream are the ones other helpers also cover. That ordering makes an early link closure truncate rather than wreck decodability.
The method borrows from three sources. Peeling and inactivation decoding come from the rateless line of work. The insistence on 0/1 coefficients comes from the fractional-repetition construction in Numerically Stable Binary Coded Computations. The idea that membership changes should not require moving raw data comes from the "transition compatibility" of Coded Elastic Computing. In our version, a membership change re-orders streams instead of re-encoding. Contact plans follow the time-expanded snapshot view used for LEO routing, and the per-node, constant-complexity link management of SkyLink: Scalable and Resilient Link Management in LEO Satellite Networks is treated as the routing substrate on which our code runs.
The analysis has two goals. First, we will characterize when foreknowledge helps. Our hypothesis is that the gain over random degree distributions is largest when $k$ is small to moderate and contact windows are short relative to compute time. Fountain-code reception overhead is known to shrink as $k$ grows, which is where this expectation comes from. Second, we will bound how gracefully performance degrades as the contact predictor's error grows. That degradation curve decides whether the method is useful beyond idealized orbital mechanics.
Two lines of work motivate the gap. Stochastic Coded Offloading Scheme for Unmanned Aerial Vehicle-Assisted Edge Computing and Edge Computing in the Dark handle dynamic availability, using stochastic programming in the first case and bandit learning in the second. Both use large-field polynomial codes as a black box. The stochastic program was also truncated to three stages because of exponential scenario growth. Our design uses scenarios only offline for code construction and needs no online multi-stage solve.
One result constrains the design. Barycentric Coded Distributed Computing with Flexible Recovery Threshold shows that approximate "anytime" decoding is possible: accuracy improves with each arrival. We therefore have to show that exact binary recovery is worth more than graceful approximation under hard deadlines.
Baselines
The naive reference point is bent-pipe offload to a ground cloud. The input is relayed to a ground station and computed centrally, with the full $Wx$ returned, under the same contact plan and with propagation delay included. A second weak reference is uncoded splitting across the currently visible helpers, waiting for all of them. Numerically Stable Binary Coded Computations reports 21.1 seconds for an uncoded system versus 12.7 seconds for its binary code, under 16 stragglers on a 250-instance AWS delay profile. Beating these references is necessary but not interesting.
The strongest competitor is Rateless Irregular-Repetition coding from Rateless Codes for Low-Latency Distributed Inference in Mobile Edge Computing. It is already binary in structure, harvests partial work from every helper, decodes by inactivation, and is indifferent to which helpers respond. That makes it the natural answer to dynamic topology without any prediction. That paper reports a 35% latency reduction at $k = 7{,}000$ and 48% at $k = 15{,}000$ relative to MDS-Repetition, on a static five-node edge topology. No reported result was found on Lacuna for this scheme under mobile or LEO contact dynamics. We will re-implement it on the same contact traces, delay profiles, matrix sizes and decoder hardware as our method. Its degree distribution will receive the same tuning budget, swept over the same scenario samples we use for construction. Beating it means a lower deadline-miss probability at equal or lower decoding cost, at the same $k$ and deadline, with paired confidence intervals across traces.
The other strong competitors are as follows. Coded Elastic Computing from Coded Elastic Computing reports up to 46% speedup over non-adaptive coded methods and exact results with up to 50% of the cluster preempted. We will run it with contact-window closures mapped to preemption events, so it receives the same topology information we do. A Reed–Solomon/MDS code over GF($2^8$) and GF($2^{16}$), quantized and implemented with a vectorized Galois-field library, will be run on the same embedded processor. This is what a practitioner would deploy. The barycentric anytime scheme of Barycentric Coded Distributed Computing reports a 38% task-completion improvement over Entangled Polynomial codes with 20 workers on YearPredictionMSD. We will run it at matched deadlines and score it on downstream task accuracy, since its output is approximate.
The key ablation isolates the contact plan as the ingredient. It keeps our exact construction pipeline, degree budget and stream ordering, but replaces the predicted contact plan with a topology-oblivious prior: every helper is assumed always reachable with average throughput. If this ablation matches the full method, the contribution reduces to a well-tuned rateless code and the core claim fails. A second ablation keeps the contact-aware design but disables stream re-ordering on window changes. It measures how much of the gain comes from elasticity rather than from construction.
Why not just…?
Why not just use rateless fountain codes as they are? This is the real threat. Rateless codes already avoid large fields and tolerate any helper subset. Their weakness is reception overhead: they need noticeably more than $k$ results to decode, an overhead that is largest at small $k$. They also cannot steer redundancy toward helpers that are about to disappear. The contact-plan ablation and the head-to-head sweep over $k$ and window length will settle this. We expect our advantage to vanish at large $k$ with long windows. If it also vanishes at small $k$ with short windows, we will report that the prediction does not pay for itself.
Why not just use Reed–Solomon over GF($2^8$), which is fast on modern processors? For a handful of coarse tasks, it may well be competitive, and we will say so if the measurements show it. The problem comes from harvesting partial work across windows lasting a few seconds. That requires splitting $W$ into many fine coded pieces, and GF($2^8$) supports at most 256 distinct evaluation points. Finer partitioning forces larger fields, quadratic-or-worse decoding, and quantization of real-valued activations. The Coded Computing at Full Speed testbed already found that splitting beyond 5–8 pieces stopped paying off because of $O(k^3)$ decoding. Our decoder-on-device timing experiment measures exactly this crossover.
Why not just schedule uncoded replicas using the contact plan, since the topology is predictable anyway? Predictable trajectories do not make compute times predictable, and contact predictions have errors. Replication wastes capacity on duplicated blocks and still misses the deadline when one critical replica straggles. The prediction-error sweep tests this directly. A contact-aware replication scheduler, given the same predictions, is included as a baseline. If it matches us at zero prediction error, the coding layer must earn its keep as error grows.
Why not just compute in the ground cloud? The bent-pipe reference measures this. SkyLink's results show bent-pipe operation degrading sharply under ground-station failures: costs rose by over 67%, versus under 10% for distributed management. Round-trip propagation alone threatens deadlines in the tens of milliseconds.
Proposed Experiments
The testbed combines three published setups. The workload and matrix sizes ($k$ from 7,000 to 15,000, 5 to 20 helpers) follow the Mobile Edge Distributed Inference Simulator used in Rateless Codes for Low-Latency Distributed Inference in Mobile Edge Computing, with the same sizes plus smaller $k$ to probe the overhead regime. Per-task compute times are drawn from the AWS delay profiles used in Numerically Stable Binary Coded Computations and Coded Elastic Computing. Contact plans come from two sources. The LEO setting uses OneWeb two-line-element ephemerides with population-weighted demand, as in SkyLink, with the master on a satellite and helpers drawn from inter-satellite-link neighbors. The aerial setting uses the Singapore Land Transport Authority traffic traces used in Stochastic Coded Offloading Scheme for Unmanned Aerial Vehicle-Assisted Edge Computing.
For an application-level check, the distributed layer is the linear classifier over 512-dimensional VGG19 features, following the CIFAR-10 protocol of Generalized Lagrange Coded Computing, and an equivalent layer for EuroSAT land-cover classification. We report end-to-end classification accuracy at the deadline.
The metrics are four. The first is deadline-miss probability as a function of $D$. The second is mean and 99th-percentile completion latency. The third is decoding time measured on an embedded ARM-class board rather than estimated. The fourth is accuracy at the deadline, which matters most for the approximate barycentric baseline.
The decisive check is a two-dimensional sweep over task count $k$ and the ratio of mean contact-window length to per-task compute time. It is run with predictor error injected at 0%, 10%, 25% and 50% of window length. This sweep compares the full method, the contact-oblivious ablation, and Rateless-IR. The core claim survives only if three conditions hold together. The full method must reduce deadline-miss probability relative to both comparators in the short-window, moderate-$k$ corner. It must keep that advantage at least at 10–25% prediction error. And its measured decoding time must stay below the GF($2^{16}$) Reed–Solomon decoder at matched recovery.
A secondary check verifies numerical exactness. Our real-valued output should be bit-identical to uncoded computation up to floating-point summation order. We will compare it against the quantization error of the finite-field baselines on the classification layers.
References
- Rateless Codes for Low-Latency Distributed Inference in Mobile Edge Computing
- Generalized Fractional Repetition Codes for Binary Coded Computations
- Coded Elastic Computing
- SkyLink: Scalable and Resilient Link Management in LEO Satellite Networks
- Stochastic Coded Offloading Scheme for Unmanned-Aerial-Vehicle-Assisted Edge Computing
- Edge Computing in the Dark: Leveraging Contextual-Combinatorial Bandit and Coded Computing
- Barycentric Coded Distributed Computing With Flexible Recovery Threshold for Collaborative Mobile Edge Computing
- Coded Computing at Full Speed
- Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation