Distributed Computing · Cross-listed from cs.AI
Agency as a New Organizing Abstraction for Computer Science
Ian Foster
Advances in large-scale machine learning have enabled agentic AI systems: persistent, autonomous computational entities that pursue goals, initiate actions, and interact with open environments. These systems are often framed as applications of foundation models. We argue that this framing is incomplete: agency is also a candidate new organizing abstraction for computer science. What is new is not the concept of an
agent, nor runtime policy generation per se, but its general-purpose, open-ended form, in which systems can synthesize courses of action from goals, observations, and
memory, over tools and environments for which no complete task-specific model was specified in advance. Thus agency becomes a systems-level abstraction as well as an AI modeling concept. Where the process abstraction organizes computation around executing programs, agency organizes it around pursuing goals under bounded resources: a process executes a program; an
agent pursues a goal. From this perspective, the recurring failures of deployed agentic systems (runaway resource consumption, behavior redirected by
adversarial content, opaque continuous operation) are symptoms of structural abstraction gaps, not isolated engineering defects. We examine these gaps across six dimensions (execution, interfaces, correctness, oversight, coordination, and persistence) and argue that closing them requires coordinated advances in systems,
Read the full abstract ▾
Distributed Computing · Cross-listed from cs.NI
Computing All-Pairs Shortest Communication Time Paths for Periodically Varying Satellite Networks
Koushik Sinha, Dibakar Saha, Sai Puppala et al. (+1 more)
We address the problem of designing an efficient
algorithm for computing the all-pairs shortest-time paths in time-varying networks, specifically targeting the dynamic topological characteristics of low earth orbit (LEO) satellite constellations. We model such temporal graphs as $G = (V, E_t)$, where $V=\{1, 2,\ldots , n\}$ is the set of $n$ vertices in the graph, and $E_t$ is the set of $M$ time-varying edges considered over a total time window of size $T = M\tau$, $\tau$ being the duration of each interval in that time window. For such a network, our
algorithm finds the all-pair shortest paths in $O(M^2n^3)$-time. A key advantage of our approach is its computational structure, which mirrors two
matrix multiplication steps, first in the forward direction and then in the backward direction. This structure of the
algorithm makes it exceptionally suitable for parallelization on SIMD architectures like GPUs, thereby offering a significant speedup over traditional shortest-path
algorithms and enabling efficient, network-wide message routing in rapidly changing LEO satellite constellations.
Read the full abstract ▾
All authors Koushik Sinha, Dibakar Saha, Sai Puppala, Bhabani P. Sinha
Distributed Computing
GPU Goldmines: Tunable WebGPU Kernels for Edge LLM Inference
Rithik Sharma, Reese Levine, Zheyuan Chen et al. (+3 more)
As demand for LLM inference grows and consumer GPUs grow more capable, edge deployment is becoming increasingly attractive. WebGPU is compelling in this setting because it offers cross-platform portability and browser accessibility. However, these same strengths also make high performance difficult to achieve, as an implementation that performs well in one context may not perform well in another. To address this, we present GPU Goldmines, a framework for specifying, executing, and tuning WebGPU kernels. We instantiate GPU Goldmines with kernels for key LLM building blocks:
matrix multiplication,
matrix-vector multiplication, and flash
attention. We characterize performance across diverse devices, shapes, and browsers, and use the resulting database to accelerate subsequent autotuning and configuration selection. On shapes drawn from Llama and Qwen models, our
matrix multiplication kernels outperform ONNX Runtime and llama.cpp WebGPU kernels by 7.0x and 1.41x
geometric mean, respectively, and deliver end-to-end improvements of 1.48x in the prefill stage of llama.cpp for chat workloads.
Read the full abstract ▾
All authors Rithik Sharma, Reese Levine, Zheyuan Chen, Ananthajit Srikanth, Yanwen Xu, Tyler Sorensen
Distributed Computing · Cross-listed from cs.AI
Towards Resilience: Slice-Driven Orchestration of Mobile IoMT in 6G-Edge-Continuum
Muhammad Zeeshan, Hafiz Faheem Shahid and Erkki Harjula
Emerging healthcare services, such as real-time diagnostics, remote health monitoring and computer-assisted surgery, require stringent Quality of Service (QoS) guarantees while operating under limited and heterogeneous edge resources. Existing Internet of Medical Things (IoMT) orchestration methods primarily focus on communication metrics such as latency and bandwidth, while overlooking edge resource constraints and dynamic adaptation to workload and user mobility. This paper presents a novel resource-slicing-based adaptive orchestration framework that integrates 5G network slicing (NS), resource-aware orchestration, and mobility-aware task offloading into a single adaptive system. IoMT services are assigned to distinct 5G network slices while jointly considering CPU capacity,
memory availability and amount of storage, enabling more efficient service placement and execution. In addition, the system supports user mobility and dynamic task offloading to maintain service continuity under changing network conditions. SimPy-based simulation demonstrates that the proposed method enhances service deployment efficiency, reduces request blocking, and improves user acceptance while maintaining reliable performance across diverse IoMT scenarios.
Read the full abstract ▾
Distributed Computing · Cross-listed from cs.LG
Protocol Choices Matter More Than the Aggregation Algorithm: Federated Learning for In-Hospital Mortality Prediction in Care-Unit and Multi-Hospital Federations
Rodrigo Tertulino, Ricardo Almeida and Laércio Alencar
Federated learning allows hospitals to train a shared mortality model without pooling their records, but published comparisons of aggregation strategies rarely control the evaluation protocol. This study compared seven strategies (FedAvg, FedProx, SCAFFOLD, FedAdagrad, FedAdam, FedYogi and FedCluster) on two federations built with one pipeline: 12 care units of a hospital in MIMIC-IV and 49 hospitals in eICU-CRD. Each strategy was tuned and selected on validation data by the same rule, and every comparison was repeated across 10 seeds with Friedman and Holm-corrected tests. SCAFFOLD ranked first in both federations (AUC-ROC 0.886 and 0.819) and in 17 of 18 variants, but its margin over the runner-up never exceeded 0.008, and a control sharing its local optimizer attributed most of its margin over FedAvg to drift correction. On the multi-hospital federation,
federated training matched centralized training. In the care-unit federation, three protocol choices changed discrimination by more than the choice of strategy did: discharge-coded predictors (+0.038 in AUC-ROC), client-level SMOTE (up to -0.074), and evaluating the last instead of the best validation round (up to -0.084). Platt scaling on validation data repaired the risks distorted by imbalance corrections without loss of discrimination. Studies should therefore fix the protocol before ranking
algorithms.
Read the full abstract ▾
Distributed Computing · Cross-listed from cs.NI
MCCL: Measurement-based Collective Communication Library
Michele Ferrero, Gabriele Castellano, Paolo Medagliani et al. (+3 more)
Collective communication is a critical performance bottleneck in large-scale distributed training. Existing libraries and synthesis frameworks compute open-loop schedules once, assuming a static
topology and peak link capacities. In production, however, persistent gray failures can silently degrade link throughput and latency for hours, causing pre-computed schedules to lose much of their efficiency during execution. In this paper, we present Measurement-based Collective Communication Library (MCCL), a collective communication library that closes the loop between runtime network measurement and dynamic schedule synthesis. MCCL passively measures GPU-to-GPU throughput, detects persistent degradation, re-synthesizes the affected communication-intensive schedules with warm-started synthesizers, and hot-swaps them without interrupting training. We validate the complete loop on a multi-node hardware prototype and use simulations to evaluate cluster-scale scenarios. In our experiments, MCCL incurs negligible overhead (<2%) while maintaining high measurement accuracy (<1.2% error) and low schedule hot-swap time (about 12 ms). Notably, under gray failures, MCCL reduces training time by up to 4.99x over static schedules on simulated training workloads for state-of-the-art LLMs such as Llama and DeepSeek.
Read the full abstract ▾
All authors Michele Ferrero, Gabriele Castellano, Paolo Medagliani, Sebastien Martin, Roberto Morabito, Massimo Gallo
Distributed Computing
FlashT2S: GPU-Accelerated Tensor-to-Spike Conversion Operators for Heterogeneous Neuromorphic LLM Backends
Rongyuan Guo, Haotian Wang, Yufeng Zhang et al. (+2 more)
Artificial intelligence faces two growing challenges: computational bottlenecks and energy inefficiency inherent to the von Neumann architecture. Neuromorphic computing offers a promising alternative, yet its immature ecosystem still relies on conventional systems for data supply, requiring efficient conversion between tensor and spike dataflow. We observe a clear mismatch, where data conversion is slow while downstream computation is fast. As data size grows quadratically with large
language models, this mismatch becomes a major bottleneck. In this work, we examine the data-conversion components that appear on the critical path of training and inference in neuromorphic LLMs. The work presents FlashT2S (Flash Tensor-to-Spike): GPU-Accelerated Tensor-to-Spike Conversion Operators, which applies architecture-aware and data-centric optimizations to reduce conversion latency. Experimental results show that FlashT2S delivers an average speedup of 850.78x over the native operators across individual operators and 802.83x in realistic workloads. Additionally, compared with GPU kernels automatically generated by torch.compile, our kernels achieve 5-11x speedups. Notably, it achieves near-optimal absolute performance: large-scale conversions are reduced to tens of microseconds (10-99 us), while small-scale conversions reach single-digit microsecond levels (less than 10 us). Furthermore, its standardized output enables seamless integration across heterogeneous backends, including diverse neuromorphic hardware.
Read the full abstract ▾
All authors Rongyuan Guo, Haotian Wang, Yufeng Zhang, Wangdong Yang, Kenli Li
Distributed Computing · Cross-listed from cs.LG
Mixture of GFlowNets
Omar G. Younis, Joseph D. Viviano, Chirayu Anant Haryan et al. (+3 more)
Generative Flow Networks (GFlowNets) learn a policy that samples compositional objects in proportion to an unnormalized reward $R(x)$. This makes them useful wherever many diverse, high-reward candidates are needed and oracle queries are expensive. In practice, a single GFlowNet often fails to cover all modes of a complex distribution, and the obvious ways to scale compute saturate: larger batches and data-parallel gradient averaging draw every trajectory from one, possibly biased, policy, so extra rollouts rediscover known modes instead of finding new ones. We explore whether this mode-bias problem (mode collapse in the extreme) can be addressed with a population of asynchronously trained policies which divide the state space between them. Mixture of GFlowNets (MoG) replaces the single forward policy with a community of $K$ independent GFlowNets coupled through one jointly trained soft classifier, which assigns each member its own region of the state space through reward shaping. Mixing the members under their learned partition functions provably recovers the target $p(x)\propto R(x)$. MoG exchange (MoGX) also lets the classifier route sampled trajectories: a trajectory the classifier assigns to another member is sent to that member and trained on there, with no importance sampling. We evaluate both methods by keeping the environment-interaction budget fixed while scaling the community size, turning parallel compute into mode coverage without extra oracle calls. On HyperGrid, across six reward landscapes and communities of up to $K{=}64$, MoG and MoGX keep finding new modes as $K$ grows, while data-parallel training saturates. On a genomic ideotype-design task, MoGX covers $39%$ of the $1024$ optima at $K{=}64$, against $31\%$ for independent
agents and $20\%$ for data-parallel training. MoG also has a lower per-iteration synchronization cost than data-parallel training.
Read the full abstract ▾
All authors Omar G. Younis, Joseph D. Viviano, Chirayu Anant Haryan, MD Vasimuddin, Sanchit Misra, Yoshua Bengio
Distributed Computing
MODAIC: Coordinated Asynchrony for Decentralized Multimodal Learning
Yanhang Shi, Xiaoyu Wang, Houwei Cao et al. (+2 more)
Multimodal decentralized learning enables collaboration across heterogeneous edge devices without sharing raw data, but differing modality sets create coupled computation and communication bottlenecks.
Multimodal agents support cross-modal
alignment while training more model components and sharing bandwidth across multiple modality overlays. Under bandwidth limits, these
agents can become hot spots: transfers miss aggregation windows, and their updates become stale or underrepresented, degrading worst-
agent accuracy. Asynchrony removes global blocking but does not by itself coordinate local cross-modal interaction with timely peer-update exchange. We present MODAIC (Modality-Decoupled Asynchrony with Interleaved Coordination), a wait-free system that coordinates local modality progress, peer-to-peer update delivery, and aggregation under heterogeneous compute and bandwidth. Hierarchical asynchrony lets modalities progress independently while enforcing reciprocal feature exchange; load-aware update fetching overlaps training with communication, limits concurrent serving load, and reuses late arrivals; and consensus-aware peer selection uses lightweight metadata to account for update availability, peer participation, and loss similarity without active probing. We implement MODAIC as a containerized multi-
agent framework and evaluate it on local and cross-region cloud testbeds. Across AVE and KU-HAR, MODAIC improves average accuracy and
multimodal worst-
agent performance. On AVE at 200 Mbps per
agent, it improves
multimodal worst-
agent accuracy by 11.0 percentage points at 1000 seconds over the strongest baseline. On the cloud testbed, it reduces time-to-accuracy by up to 30%. Ablations show that simpler load-balancing and delayed-aggregation variants leave a worst-
agent accuracy gap, and stress tests show tolerance to WAN variability and partial tracker unavailability.
Read the full abstract ▾
All authors Yanhang Shi, Xiaoyu Wang, Houwei Cao, Jian Li, Yong Liu
Distributed Computing
Beyond the Boundary: Optimal Grid Dispersion by Spread, Reverse, and Collect
Manish Kumar, Anisur Rahaman Molla, Debasish Pattanayak et al. (+1 more)
Dispersion requires a set of mobile
agents to occupy distinct nodes of a graph such that each node contains at most one
agent. We study deterministic dispersion of $k\le n$
agents on an $n$-node oriented square grid, where each node has globally consistent North, East, South, and West port labels, from arbitrary initial configurations. This includes both rooted configurations, where all
agents are co-located initially, and general configurations, where
agents are initially distributed arbitrarily across the nodes. On oriented square grids, Kshemkalyani, Molla, and Sharma~\cite{KMS20} gave an $O(\min(k,\Side))$-round
algorithm in the local-communication model, where only
agents on the same node can exchange information, and an $O(\sqrt{k})$-round
algorithm in the global-communication model, where any two
agents can communicate regardless of position, both using $O(\log k)$ bits per
agent. The bound in the local communication model is optimal when $k=\Theta(n)$, but it remains open whether local communication alone can match the $\Omega(\sqrt{k})$ time lower bound when $k=o(n)$. We solve this by presenting Spread–Reverse–Collect (SRC), a deterministic
algorithm that disperses any $k\le n$
agents in $O(\sqrt{k})$ synchronous rounds using $O(\log k)$ bits of persistent
memory per
agent, matching both time and
memory lower bounds. SRC is based on a
geometric primitive, a \sharpS-shaped parallel sweep, together with a simple priority rule. Unlike earlier grid
algorithms that gather
agents at the boundary and spread out from there, each SRC sweep starts from the
agents' current position, and when it reaches the boundary the group simply reflects its sweep back inside and continues. SRC therefore needs no knowledge of the grid size and runs unchanged on an infinite oriented grid.
Read the full abstract ▾
All authors Manish Kumar, Anisur Rahaman Molla, Debasish Pattanayak, Subhajit Pramanick
Distributed Computing · Cross-listed from cs.AR
FORGE: Procedural Weight Generation for Sparse MoE Inference
Chanyoung Moon, Travis Pence, Daisuke Yamada et al. (+4 more)
We introduce FORGE (Fast On-chip Rotor Generation for Experts), a procedural weight generation system for Sparse Mixture-of-Experts (MoE) inference. Rather than storing and loading every expert weight tensor from HBM, we show how a compact accelerator inside each Streaming Multiprocessor can regenerate them on-the-fly from $O(\log^2 d)$ rotor parameters per projection. Per replaced layer, gigabytes of stored expert weights are approximated with under a megabyte of seeds. This addresses the dual
memory bottleneck of autoregressive Sparse MoE decode, where per-expert FFN operations are HBM-bandwidth-bound at small routed-
token counts and the aggregate expert footprint forces multi-node Expert Parallelism (EP) with all-to-all traffic. We realize the approach as the Rotor Generation Unit (RGU), a fixed-function datapath that generates FFN weight tiles without competing with Tensor Core execution. With 30% of the MoE FFN layers replaced across five Sparse MoE models, we estimate 1.3-2.8x higher system throughput at matched GPU count and 1.10-1.15x lower per-user decode latency at short context. In exchange, downstream accuracy on three model families falls below that of the same model fine-tuned without rotor replacement, and the replacement ratio controls this tradeoff. FORGE also expands KV cache capacity by 1.2-2.6x. It is agnostic to the bit width at which weights are stored, so it can compose with quantization. The RGU is fully implemented/verified in SystemVerilog at ~0.9% SM area overhead (0.032 mm^2/SM, 7nm).
Read the full abstract ▾
All authors Chanyoung Moon, Travis Pence, Daisuke Yamada, Jiaqi Mo, Yanxin Zhang, Vikas Singh, Karthikeyan Sankaralingam
Distributed Computing · Cross-listed from cs.LG
Efficient Resource-Shiftable RL Post-training with Generative Rewards
Yanfeng Zhao, Haoyang Li, Sheng Lin et al. (+4 more)
Reinforcement learning (RL) post-training with generative reward models (GenRM) has become a central recipe for improving large
language models (LLMs), and it is also increasingly resource-intensive: policy rollout, GenRM-based reward evaluation, and policy training all compete for GPU resources. However, existing colocated and disaggregated systems rely on static resource allocation for these roles. Such allocation cannot adapt as each role's workload changes during RL and therefore leaves a role's resources underutilized. We present PivotRL, an RL post-training system that dynamically shifts resources among different roles according to their runtime demands. PivotRL introduces a resource-shiftable runtime built on a Global Parameter Storage, together with a unified mechanism that efficiently shifts role-specific context. A shift-aware scheduler enables sequence migration upon a shift, while a planner considers the aggregate throughput benefit and the shift overhead to determine when and how to shift. We evaluate PivotRL on a 128-GPU cluster using four model groups spanning dense and mixture-of-experts models. PivotRL enables resource shifting within seconds and improves end-to-end throughput by 1.81-2.05 times over colocated deployment and 1.50-1.95 times over disaggregated deployment, while preserving RL convergence.
Read the full abstract ▾
All authors Yanfeng Zhao, Haoyang Li, Sheng Lin, Yuming Zhou, Jiawei Jiang, Bin Cui, Fangcheng Fu
Distributed Computing
Improved Massively Parallel Shortest Path Computation
Yi-Jun Chang and Shaun Quek
We present new
algorithms for approximate shortest path computation in weighted undirected graphs within the Massively Parallel Computation (MPC) model. Specifically, we construct an $a$-approximate Single-Source Shortest Path (SSSP) oracle: Given a query consisting of a source vertex $u \in V$, the oracle returns $a$-approximate distances $\delta(u,v)$ for all $v \in V$. Fix an $n$-vertex weighted undirected graph. We consider two regimes of the MPC model: the near-linear regime, where each machine has $\tilde{\Theta}(n)$
memory, and the heterogeneous regime, where all machines have $\Theta(n^\gamma)$
memory for some constant $\gamma\in (0,1]$, except for a single machine with $\tilde{\Theta}(n)$
memory. We develop randomised
algorithms that construct $O(1)$-approximate SSSP oracles in $O(\log\log n)$ rounds in the near-linear regime and in $O(\log^2\log n)$ rounds in the heterogeneous regime. These oracles answer distance queries in $O(1)$ rounds. Our results improve upon the recent work of Dory and Matar (SPAA 2024) which, for the same total
memory, requires $\left(\log\log n\right)^{2+O(1/\gamma)}$ rounds and applies only to unweighted graphs in the heterogeneous setting. We say that $\tilde N_k(u)$ is the approximate $k$-nearest neighbourhood of a vertex $u$ if there exists an approximate distance estimate $\delta$ such that $\tilde N_k(u)$ consists of the $k$ vertices closest to $u$ according to $\delta$, breaking ties by vertex ID. The main technical ingredient is a new method for efficiently computing approximate $n^{O(\gamma)}$-nearest neighbourhoods in the heterogeneous MPC model in $O(\log^2\log n)$ rounds.
Read the full abstract ▾
Distributed Computing · Cross-listed from cs.CR
PrivacyGuard: Source-Linked Sanitization and Locally Resolvable PII References for Cloud GUI Agents
Zian Yuan and Wei Li
Cloud graphical user interface (GUI)
agents send instructions and screenshots to remote planners, exposing personally identifiable information (PII). Existing placeholder defenses mask detected spans and reuse exact strings. Fragmented or changed forms can expose PII or break entity continuity across turns. PrivacyGuard addresses this private reference problem with source-linked sanitization (SAN) and a structured reference lifecycle (REF). SAN reconstructs fragmented or overlapping evidence and rewrites the complete source extent. REF links changed appearances to session entities and supports locally resolvable references without returning raw values to the upload path. In five-turn sessions scored against common gold, PrivacyGuard reduces audited source-value leakage by 33.55%–82.60% relative to the closest prior full-pipeline system in all four reader–
language combinations. REF raises strict cross-form continuity from 0.04 under exact-value reuse to 0.81. In reference-required Android tasks, verified completion rises from 8/30 and 7/30 to 17/30 and 20/30. On AndroidLab, PrivacyGuard achieves the highest or tied-highest task-success point estimate among protection pipelines for all four planners. On PrivScreen, it reduces fixed-reader field exposure by 62.72%–62.84% relative to the same baseline. PrivacyGuard lowers upload exposure while preserving a locally resolvable task path.
Read the full abstract ▾
Distributed Computing
StageBreaker: Shifting Video RL Post-Training Scheduling from Stages down to Data Dependencies
Li Peng, Chenghuan Huang, Ziyang Ma et al. (+3 more)
Reinforcement learning (RL) post-training has emerged as the key paradigm for improving autoregressive
video models. Emerging
vision-
language reward models further strengthen post-training with accurate rewards, but their long chain-of-thought inference substantially raises the associated costs, while the pursuit of long
videos prolongs policy training. Despite these rising costs, existing
video RL systems still adopt coarse-grained stage-centric execution, which stalls policy training until all reward evaluation finishes, replays every trajectory twice due to a further barrier within policy training, and induces load imbalance across GPUs. To address the challenges, we propose StageBreaker, a fine-grained data-dependency-driven scheduling framework, which schedules the true dataflow of an RL step rather than its stages. Specifically, StageBreaker overlaps policy training with reward evaluation by exploiting reward-separable policy training, and merges the two trajectory replays into one by leveraging loss-independent back-propagation. It further balances GPU load by scheduling computation at the finer granularity. Our evaluation results show that StageBreaker achieves a speedup of up to 1.41$\times$ over stage-centric execution.
Read the full abstract ▾
All authors Li Peng, Chenghuan Huang, Ziyang Ma, Jing Lyu, Xiang Chen, Jie Zhang
Distributed Computing · Cross-listed from cs.GT
The Voter Model with Opinion Graph
Petra Berenbrink, Thorsten Götte, Martin Hoefer et al. (+1 more)
We study the voter model with opinion graph, a generalization of the standard (pull) voter model that adds a notion of bounded confidence. In this process, we consider a finite set $A$ of $n$
agents. Each
agent $u \in A$ has an opinion $x_u \in O$, where we model opinions as vertices in an undirected opinion graph $G = (O,E)$ with $|O|=q$. In each step, an
agent $u$ interacts with another
agent $v \in A$. In contrast to classical voting, $u$ adopts the opinion $x_v$ if and only if $x_v$ and $x_u$ are neighbors in $G$. The process is stable once all remaining opinions are an independent set in $G$. We analyze two variants of the process: the ordinary EdgeVOG process, which samples a pair of interacting
agents uniformly at random from all possible pairs, and the productive EdgeVOG process, which samples only pairs with neighboring opinions in $G$. We show the following: - For every opinion graph and every initial configuration, ordinary EdgeVOG stabilizes within $O(n^2\log n)$ steps in expectation and with high probability. The expectation bound is asymptotically tight. For the productive EdgeVOG process, the expected stabilization time is exactly the initial number of compatible
agent pairs, while $O(n^2\log n)$ steps suffice with high probability. - An opinion $i$ with initial support $s_i$ survives with probability at least $p_i:=s_i/(s_i+\sum_{j\in N(i)}s_j)$. Further, let $\mu = \sum_{i \in O} p_i$, then we show the probability that less than $(1-\delta)\mu$ opinions survive is at most $\exp(-\delta^2\mu/(2(\Delta^2+1)))$ for every $0\leq\delta\leq1$. -If $G$ has maximum degree $\Delta$ and every opinion initially has support at most $\hat{s}$, then no opinion ever acquires more than $\tilde{O}(\min\{n,\Delta^6\hat{s}\})$
agents with high probability. This yields near-linear stabilization bounds for productive EdgeVOG for a large class of configurations.
Read the full abstract ▾
All authors Petra Berenbrink, Thorsten Götte, Martin Hoefer, Tim Koglin
Distributed Computing
Prorsa: Unleashing the Potential of Prefill-Decode Disaggregation in Agentic Reinforcement Learning
Chiheng Lou, Xiangwei Deng, Bangjun Xiao et al. (+4 more)
Agentic reinforcement learning (RL) is commonly used to enhance the capabilities of large
language models (LLMs) in solving complex multi-turn tasks. During rollout, agentic RL exhibits a workload pattern distinct from that of traditional RL: multi-turn interactions repeatedly introduce prefill requests, causing prefill and decode workloads to coexist throughout rollout. This workload makes prefill-decode (PD) disaggregation, a design widely used for online LLM serving, promising for speeding up agentic RL rollout. This paper shows that PD disaggregation can improve rollout efficiency by (a) mitigating interference among data-parallel
attention modules, (b) enabling stage-specific parallelism, and (c) reducing end-to-end trajectory completion time. However, a fixed prefill-decode allocation may fail to sustain these benefits as workload composition varies across tasks and over time. We therefore present Prorsa, an agentic RL framework for prediction-guided prefill-decode resource allocation. Prorsa observes the lifecycle of every trajectory to forecast short-horizon prefill and decode demand. These forecasts then guide worker allocation decisions and trigger role switching of rollout engines, aligning prefill and decode capacity with anticipated workload demand. Across synchronous and asynchronous agentic RL settings, Prorsa achieves end-to-end rollout speedups of 1.11x-4.05x over prefill-decode colocation.
Read the full abstract ▾
All authors Chiheng Lou, Xiangwei Deng, Bangjun Xiao, Xiaodong Ji, Yikai Zhao, Xin Jin, Hailin Zhang
Distributed Computing · Cross-listed from cs.DS
Distributed $(\Delta+1)$-Coloring in $O(\sqrt{\Delta}+\log^* n)$ Rounds
Marc Fuchs and Fabian Kuhn
We give a deterministic distributed
algorithm for $(\Delta+1)$-coloring an $n$-node graph of maximum degree $\Delta$ in $O(\sqrt\Delta+\log^* n)$ rounds in both the LOCAL and CONGEST models. More generally, $(\deg+1)$-list coloring with lists from a color space of size $C\geq\Delta+1$ can be solved in $O(\sqrt\Delta\log(1+C/\Delta)+\log^* n)$ rounds; in CONGEST, we assume $C\leq n^{O(1)}$. The
algorithm combines Barenboim's
polynomial coloring procedure with arbdefective decompositions, degree reduction, and a short family of hash functions. Using the
polynomial procedure in the degree-reduction framework already gives an $O(\sqrt\Delta\log\Delta+\log^* n)$-round
algorithm when $C=O(\Delta)$. Hashing adapts the color space to the current degree and removes the logarithmic factor. We prove the existence of the hash family by the probabilistic method and compute it by deterministic exhaustive search, using unrestricted local computation. We also give an explicit variant based on lossless expanders that avoids this search and achieves $O(\sqrt\Delta+\log^* n)$ rounds for $C=O(\Delta)$.
Read the full abstract ▾
Distributed Computing · Cross-listed from cs.NI
CALIPER: Calibrating HPC/AI Network Simulators
Seyyidahmed Lahmer, Daniel Seibel, Srijeet Basu et al. (+9 more)
Network simulation plays an important role in HPC/AI system research by enabling exploration of network architectures, communication strategies, and system configurations at scales that may be impractical to study experimentally. Existing approaches to network simulator calibration and validation lack a principled methodology that combines parameter
alignment, constrained inference, and independent validation for collective-centric HPC/AI networks. We present CALIPER, a methodology for systematic calibration and validation of HPC/AI network simulators. CALIPER distinguishes directly observable system parameters from auxiliary parameters which are configured via calibration and constrains the latter to feasible domains consistent with the target system. We evaluate CALIPER's hierarchical, scale-aware calibration and its effects on parameter identifiability and generalization using collective communication
benchmarks on a reference system with up to 64-nodes at the Jülich Supercomputing Centre. Validation results show that the calibrated parameter configurations identified by CALIPER predict system performance with less than 5% mean errors across scale-up and scale-out network domains. CALIPER demonstrates that hierarchical, constrained calibration can produce simulator configurations whose predictive accuracy persists beyond the observations used for fitting.
Read the full abstract ▾
All authors Seyyidahmed Lahmer, Daniel Seibel, Srijeet Basu, Arno Troch, Jayesh Badwaik, Subhomoy Bhattacharyya, Abubakr Nada, Debjyoti Bhattacharjee, Vinay Kumar Baapanapalli Yadaiah, Michael Peeters, Andreas Herten, Darayus Adil Patel
Distributed Computing
Revisiting Fast Tendermint: An Agreement Violation and Two Repairs
Alejandro Ranchal-Pedrosa
Fast Tendermint reduces Tendermint's good-case latency to two communication steps for n>=5f+1. We show that its published round-change rule violates Agreement: one Byzantine process suffices for every f>=1, and for f>=2 two Byzantine processes suffice without double signing. The failure occurs when a process advances past a round without recording the value that may have been decided there. The Quint specification that accompanies the protocol does not allow this kind of round skipping and is not affected; the violation lies in the published pseudocode. We present two repairs. Walk requires a process to leave each round on a quorum of that round's precommits and to precommit before leaving. It keeps the recorded valid state and removes the wait after a precommit quorum. Justify carries the evidence needed to accept a proposal in the proposal itself, removing both the recorded valid state and the proposer's synchronization wait. Both satisfy Agreement and Validity under asynchrony and Termination under the partially synchronous gossip model of Tendermint and Fast Tendermint. Both retain proposal timeouts. The main text presents the executions that violate Agreement and explains the two repairs. The appendices provide proofs, a brief comparison with other round-change designs, and an extension to chains.
Read the full abstract ▾
Distributed Computing
Federated Coreset Subsampling for Distributed Memory Banks
Jason Witzemann, Daniel Pröll and Sebastian Hegenbart
In real-world scenarios, industrial processes can span multiple factories and goods are often produced at multiple sites, leading to a shared yet non-identical distribution of data across locations. To address this, we propose two
federated approaches for i) combining existing coresets (Double Subsampling) and ii) creating new coresets (
Federated Subsampling) in a distributed anomaly detection setting. In particular, we adapt the
memory bank based PatchCore
algorithm to a
federated setting, resulting in increased cold-start performance, resilience to domain- and sensor-shift, and resilience to unreliable actor participation, a common problem in classical, network based
federated learning strategies.
Read the full abstract ▾
Distributed Computing
Space AI Infrastructure: Where the Edge Meets the Orbital Cloud
Zhanwei Wang, Jianhao Huang, Min Sheng et al. (+1 more)
The fusion of artificial intelligence (AI) and space technologies is extending spaceborne intelligence beyond onboard payloads toward a global infrastructure, here termed Space AI infrastructure (SpaceAI-Infra). Its promise rests on two distinctive advantages of space systems: abundant solar energy in orbit and the global reach of satellite constellations. Realizing this promise hinges on a fundamental systems question: How should satellite constellations be designed and orchestrated to deliver data-center-scale AI services competitive with their terrestrial counterparts? This article develops a roadmap-oriented answer. We first chart the
evolution of SpaceAI-Infra through three progressive stages: onboard AI, Space Edge AI, and Space Cloud AI. By revisiting the space-constrained fundamentals for end-to-end
token services, we derive enabling design principles and translate them into an integrated space edge–cloud architecture. The communication-centric space edge comprises free-flying LEO constellations that provide user-proximate computing and form the access and backhaul fabric for cloud AI services. Complementing the edge, the computing-centric space cloud comprises formation-flying satellite constellations organized as space data centers in dawn–dusk sun-synchronous orbits. A case study demonstrates that the proposed architecture can support data-center-scale foundation-model inference for millions of concurrent users worldwide.
Read the full abstract ▾
All authors Zhanwei Wang, Jianhao Huang, Min Sheng, Kaibin Huang
Distributed Computing
SP-Allreduce: Symmetric Tree Schedules for Tori and Beyond
Mikhail Cherniavskii, Andrey Kupavskii, Georgy Mironov et al. (+1 more)
Allreduce is a fundamental communication primitive in large-scale distributed training, and
torus interconnects remain widely deployed in high-performance systems. We introduce SP-allreduce, a new allreduce
algorithm for $d$-dimensional
tori that exploits the
symmetry of the
topology and routes only along shortest paths. We call an allreduce
algorithm fully bandwidth-optimal if it incurs no bandwidth overhead, no multihop-induced traffic inflation, and achieves perfect per-round load balance. SP-allreduce is based on a family of carefully symmetrized shortest-path trees that guarantees full bandwidth optimality in the $\alpha$–$\beta$ model. We prove that it uses the minimum possible number of rounds among all fully bandwidth-optimal allreduce
algorithms on $d$-dimensional
tori, and therefore the minimum running time in this class. In this sense, SP-allreduce refines Bucket allreduce: it preserves Bucket's key strengths while reducing the number of rounds by a factor of two. We further extend our approach to broader symmetric
topologies and to communication trees of prescribed depths. Experimentally, the resulting
algorithms improve over the best compared state-of-the-art
algorithms for
tori by up to $1.19\times$ on square
tori and $1.65\times$ on rectangular
tori across the tested configurations. On HyperX and spine-leaf networks, we demonstrate gains of up to $14.82\times$ and $1.72\times$, respectively, over the best evaluated baselines.
Read the full abstract ▾
All authors Mikhail Cherniavskii, Andrey Kupavskii, Georgy Mironov, Stanislav Moiseev
Distributed Computing
From Nominal Capacity to Deliverable Compute: Design, Calibration and Validation of the D-PIN SCU Dynamic Metering System
Cheng Li, Jiexiong Liu, Shikun Wang et al. (+1 more)
Nominal chip specifications do not capture the compute deliverable by heterogeneous distributed networks under communication, runtime and verification constraints. We formalize D-PIN Standardized Compute Units (D-PIN SCU) as a dynamic metering system for deliverable compute. The system combines five-dimensional resource normalization with
topology-aware and runtime-corrected metering. A cluster-scale Roofline model yields a closed-form communication ridge, while runtime factors describe thermal, fault and load effects. We show that runtime deviations cannot be identified from nominal specifications alone. Uniform re-anchoring preserves relative metering results, and a simplex-constrained calibration
algorithm estimates resource weights. The framework couples Proof-of-Physical-Work verification to a no-arbitrage condition for over-claiming and electricity-aware pricing. An end-to-end recomputation on the Zhangjiang Science Gate production node covers ten heterogeneous 8-GPU servers totaling 59.5 D-PIN SCU. Billed throughput of approximately 33,000 D-PIN SCU-hours is consistent with the physical upper bound at 78% utilization over 720 hours. Derived metrics are 3.02 kW per D-PIN SCU at the supply-and-distribution design boundary and 0.26 D-PIN SCU-hours per delivered kWh. Empirically calibrated chip values differ materially from datasheet projections; the published calibration is not independently reproducible from vendor specifications. Validation is limited to one production node, and the originality claim concerns the integrated system rather than the SCU terminology or individual components. The framework provides a basis for scheduling, verification and pricing of deliverable compute in distributed heterogeneous networks.
Read the full abstract ▾
All authors Cheng Li, Jiexiong Liu, Shikun Wang, Feiyu Ren
Distributed Computing
HeteroVDiff: Pipelining Video Diffusion across Mobile NPU and GPU with Shared Weights
Zheyu Shen, Ziyao Wang, Yexiao He et al. (+5 more)
Video generation is moving from the cloud to phones for
privacy and offline use, and applications often ask for several clips at a time, so on-device
video generation is a throughput problem before it is a latency problem. Contemporary mobile SoCs carry both a GPU and a neural processing unit (NPU) on shared DRAM, yet existing on-device
video diffusion systems run the denoiser on one engine while the other sits idle or only decodes the finished latent afterwards. Heterogeneous designs built for mobile LLMs do not carry over: they synchronise the two engines at every operator and partition weight tensors between them instead of sharing one stored copy. We first measure the platform limits that decide what can run on this class of SoC: how large one buffer may be, whether both runtimes can map the same buffer, and how much activation
memory the NPU toolchain lets one graph hold. Guided by these measurements, we store the base weights once in INT8 in the layout the NPU reads natively; the GPU consumes the same bytes directly as integer dot-product operands, so neither runtime rearranges weights on load. We then flatten the denoising trajectory into its full sequence of block executions and cut it once at a block boundary, so the GPU runs the prefix and the NPU the suffix. The cut is placed from measured rather than modelled rates, including the decoder that only the NPU can run, and taken while both engines run together because each engine's speed changes when the other is active. We present HeteroVDiff, which serves a multi-expert
video diffusion model across the NPU and GPU with 48% less weight
memory than giving each engine its own copy. Generating
videos back to back on a
Galaxy S25 with decoding inside the pipeline, HeteroVDiff sustains 1.35x the stream throughput of NPU-only execution, and on VBench-2.0 it matches FP32 in the total score over all 18 dimensions.
Read the full abstract ▾
All authors Zheyu Shen, Ziyao Wang, Yexiao He, Guoheng Sun, Yuning Zhang, Yiting Wang, Wanghao Ye, Ang Li
Distributed Computing
A New Lens on Multi-GPU Communication: API-Level Memory Models for Portable Optimization
Johnathan Alsop, Bradford Beckmann, Brandon Potter et al. (+5 more)
As network communication increasingly becomes a performance bottleneck for ML and HPC workloads, it is more important than ever to optimize multi-GPU data transfers. Recently, low-level device APIs have emerged that allow programmers to perform fine-grain optimizations via one-sided put/get operations triggered directly from the device. However, the communication libraries providing these device APIs (e.g., rocSHMEM, MSCCL++, and NCCL/RCCL GIN) currently lack a rigorous
memory model defining how their primitives interact with the underlying
memory systems. Without this, emerging HPC and ML workloads aggressively optimizing network communication via device APIs can be brittle, error-prone, and face compatibility and inter-operability challenges. This paper proposes the use of API-level
memory models for these emerging device communication APIs. An API-level
memory model defines the
memory semantics of communication API calls in a way that abstracts lower-level details from the API user and simplifies development. This work defines one such model for device-side communication (implemented in AMD's recently open sourced rocSHMEM library) and demonstrates how formal relaxations to such a model can enable low-level LLM performance optimizations while retaining a well-defined standardized interface. Specifically, we describe how updating the SHMEM API implemented by rocSHMEM can properly support cache bypassing for network data, improving performance of a collective communication workload by up to 2.48x, a fused compute+communication workload by up to 1.77x, and a state-of-the-art expert-parallel communication workload by up to 1.18x.
Read the full abstract ▾
All authors Johnathan Alsop, Bradford Beckmann, Brandon Potter, Jiakun Yan, Aurelien Bouteiller, Omri Mor, Tony Tye, Sameer Sahasrabuddhe
Distributed Computing
Substep Linearizability: Relaxing Atomicity While Preserving Sequential Specification
Finn Hackett, Evan Wrench, Ivan Beschastnikh et al. (+1 more)
Linearizability is a standard correctness condition for concurrent objects. It takes a correct by construction sequential specification of a concurrent data structure, and produces a composable specification under atomic interleavings of operations. However, some operations like atomic exchangers are not specifiable atomically, making it difficult to reason compositionally about their specifications. Interval linearizability is the state of the art in relaxing linearizability's constraints. Formally it is a powerful framework, but it requires an interval-sequential specification of the target data structure, which we show is challenging to correctly generate or understand, even for simple operations on a single concurrent register. We propose substep linearizability, which we show is equivalent to interval linearizability using X-CCorrectness, a relaxed concurrency framework we created to compare existing linearizability semantics. We show that substep linearizability's sequential specifications are suitable for previously infeasible specification tasks, while being comparable in complexity to linearizability's sequential specifications. For evaluation, we model an atomic exchanger, a popular non-linearizable queue structure, and snapshot isolation between database transactions.
Read the full abstract ▾
All authors Finn Hackett, Evan Wrench, Ivan Beschastnikh, Yuanhao Wei