Neighbor-Only Work Stealing Matches Global Performance for LEO Satellite Clusters

A new paper from Reitz et al. addresses a key challenge in Space Edge Computing (SEC): adapting work stealing—a technique from High Performance Computing (HPC)—to the sparse, mesh-like topology of LEO satellite constellations. In HPC, work stealing relies on a fully connected network with uniform low latency; a worker that runs out of tasks can steal from any other worker at random. But LEO satellites connect via inter-satellite links that form a 2D mesh, where reaching a distant node requires multiple hops, each adding latency.

The authors propose a neighbor-only strategy where workers steal exclusively from directly connected neighbors, eliminating multi-hop communication overhead. They develop an analytical model that shows per-attempt latency improves as constellation size grows, since global stealing's random selection would increasingly target distant nodes. Preliminary experiments on an HPC cluster with an emulated mesh (using uniform low-latency links to isolate topology effects) found the neighbor-only approach achieves load balancing within ~2.2% of global stealing on both balanced and irregular workloads.

The results suggest that restricting the victim set does not harm performance in emulated settings, and the model indicates neighbor-only stealing becomes preferable at scale. This work paves the way for efficient distributed computing on satellite constellations, enabling applications like on-orbit data processing, real-time analytics, and edge AI without relying on ground stations.