CS Paper Radar

Throughput-Optimal Control of Distributed Computing Networks for Service DAGs

Peng Li, Jianan Zhang, Jaime Llorca, Xinzhe Fu, Xiang Cheng, Chen Chen

cs.NI ·submitted 2026-11-03 14:53 UTC · v1

Abstract

Executing service workflows with directed acyclic graph (DAG) dependencies over wireless distributed computing networks requires joint control of function placement, routing, and scheduling, together with synchronization of inputs from the same request at merge points. We study throughput-optimal control of these networks under stochastic request arrivals, time-varying wireless links, and interference constraints. We use a valid mapping abstraction that assigns each service function to a computation node and each DAG dependency to a routing path. Using this abstraction, we characterize the network capacity region to support service DAGs, and prove that synchronizing the packets of a request at merge points does not shrink the region. We develop Dynamic Computing Network Control for service DAGs (DCNC-DAG), a dynamic control policy that selects queue-aware valid mappings and schedules service DAG execution by nearest-to-origin (NTO) while enforcing input synchronization at merge points. With exact minimum-cost valid mappings, DCNC-DAG is throughput-optimal and ensures rate stability of the physical queues under bounded arrivals. These guarantees hold for any fixed finite interval between mapping updates, even when mapping decisions rely on boundedly stale queue length information. For larger service DAGs, we develop DCNC-DAG-H, which replaces exact mapping optimization with a queue-aware heuristic. Simulations show that DCNC-DAG supports $2.7\times$-$5.5\times$ the throughput of queue-blind baselines, while DCNC-DAG-H achieves up to $2.68\times$ those of the corresponding baselines on larger workflow and AI service DAGs.

Closest papers

Nearest neighbours by meaning across the whole index.

Schedule Repair for DAG Workflows under Link Disruptions

cs.DC ·2026-09-28 ·Mohammadali Khodabandehlou, Jared Coleman, Bhaskar Krishnamachari, Kevin Chan
similarity 0.61
Abstract · 6 pages, 4 figures, 1 table. Accepted to the IoTAE Workshop at IEEE MILCOM 2026

Schedules for directed acyclic graph (DAG) workflows in networked IoT systems are typically computed assuming a static or generally stable network. In contested and adversarial environments, this assumption is not valid. Links degrade and fail due to mobility, interference, and jamming. We study schedule repair: when a link disruption invalidates part of a schedule, how much of it should be rescheduled? We introduce a spectrum of repair policies that vary in repair scope, how much of the pending schedule each may move: wait out the disruption, reroute data around it, reschedule only the affected tasks locally, or reschedule all pending tasks globally. We evaluate each against an oracle and charge every repair a decision latency proportional to the extent to which it moves. Across 100 workload instances spanning synthetic task graphs, RIoTBench pipelines, and WfCommons scientific workflows, each run at five communication-to-computation ratios (CCRs) and disrupted by processes with deliberately different correlation structure, we find that no single scope wins: rerouting nearly erases isolated failures that cost waiting 30%, global repair comes within 4% of the oracle under jamming blackouts, waiting is favored under memoryless link flapping for larger and communication-heavy workloads (the scheduling analog of route-flap damping), self-healing mobility outages reward patience over reaction, and accounting for repair latency erodes large scopes first. We conclude that the scope of the repair should be adapted to the disruption process and the repair cost, rather than fixed by the scheduler.

0.42

Control-Compute Governance in Agentic AI-RAN: AI Agents as Both Controllers and Workloads

cs.NI eess.SY ·2026-10-03 ·Le Xia, Rose Qingyang Hu, Yuan Zhou, Haijian Sun
benchmark similarity 0.56
Abstract · 7 pages, 4 figures. This work has been submitted to the IEEE for possible publication

Recent advances in artificial intelligence-radio access network (AI-RAN) are placing large language model (LLM)-driven agents within the open RAN (O-RAN) control hierarchy. A promising deployment for this agentic AI-RAN co-locates LLM inference with physical-layer (PHY) communication processing over the same accelerated compute pool for infrastructure sharing, data locality, and low control latency. However, this co-location induces bidirectional control-compute coupling, as the agent competes with PHY processing for compute, while its reasoned gNB control actions may alter future PHY workload and hence the compute available to its next inference. To this end, this article proposes the control-compute contract, a coordination protocol linking AI-RAN workload governance with O-RAN control execution. Specifically, we first expose direct compute contention on an over-the-air (OTA) O-RAN testbed, where continuous LLM inference increases the PHY decoding time approximately eightfold. We then formulate the contract as three protocol rules with operator-requirement protection, and map it onto O-RAN and AI-RAN functions as a five-stage workflow. Afterward, an OTA-calibrated case study of simulated uplink gNB control indicates that the contract keeps the proportion of slots violating the PHY time budget below $0.9\%$, against $20.7\%$ under ungoverned co-location, while achieving faster gNB control than a fixed compute reservation benchmark. Finally, we identify several open issues and outlooks for its practical deployment.

0.28

Online Network Design with Maximum Delay and Stochastic Arrivals

cs.DS ·2026-11-10 ·Tianhang Lu
theory similarity 0.56
Abstract

We study online network services that combine pending requests into batches. Each batch pays for its spatial service and for the waiting time of its oldest request. The objective is the sum of these costs over all batches. Thus requests can share both a spatial purchase and one maximum-delay charge. We assume independent Poisson arrivals of known rates, while actual requests are revealed only upon arrival. For stateless services, suppose that each type has an attainable minimum cost when served alone, that every batch costs at least the stand-alone minimum of each type it contains, and that one finite-cost action can serve any batch, regardless of its request multiplicities. We give a deterministic algorithm with long-run ratio of expectations $e/(e-1)$ against an unrestricted offline optimum. This factor is optimal, even allowing randomization, already at one request location. The key comparison measures the union of time intervals associated with requests. The theorem applies directly to multi-root and pair aggregation on trees. We also study facility location, where each request pays its own connection distance and the bounded-action assumption can fail. A deterministic policy gives a ratio $3$ for arbitrary nonnegative opening costs. It immediately serves a finite initial set of requests, computes an assignment from their observed arrival gaps, and then keeps that assignment fixed. Its analysis combines Poisson insertion with a time-slice packing bound on the offline optimum. Every guarantee includes the full cost of completing finite inputs without an end-of-input signal.

0.15

Age of Information in Queueing Systems with Merging Server Streams

cs.NI ·2026-10-07 ·Lucrezia Rossi, Leonardo Badia, Andrea Munari
similarity 0.56
Abstract

We present a novel analytical framework for evaluating the age of information (AoI) in multi-path queueing topologies where output streams from multiple servers converge into a single pipeline. This theoretical scenario finds immediate application in ultra-reliable low-latency networks and edge computing architectures, where multi-path routing and stream merging can be vital strategies for maintaining fresh status updates. Specifically, we investigate two setups: a split-merge network and a duplicate-merge network. The split-merge case has been addressed in prior work, but we show that existing studies are incorrect, and our approach provides instead an exact analytical formulation. Moreover, building on similar reasoning, we provide the first formal analysis of the previously unexplored duplicate-merge scenario. Finally, we show how to leverage our theoretical results to solve key system-level optimization problems, deriving the optimal randomized routing probabilities and traffic injection rates that minimize average AoI.

0.24

Centrality-Based Deployment of Queue Policies in Acyclic Multipath Routing Networks

cs.NI ·2026-08-25 ·Mahima Gupta, Acquin Biju, Rijul Jain, Dipesh Sharma, Sreelakshmi Manjunath
similarity 0.55
Abstract

Excessive queueing delays constitute a significant impediment to latency-sensitive network applications. Although effective deployment of Active Queue Management (AQM) strategies has been proposed as a necessary solution, deployment remains sparse. This paper studies AQM deployment in a specific class of networks where routers/switches have a topological hierarchy, form acyclic paths, and adopt multipath routing. Our approach rests on the well-established premise that AQM deployment impacts packet-forwarding dynamics in networks carrying TCP flows, thus establishing a direct link between stability and network performance. We use fluid models for TCP and queue dynamics in the network, along with a simple threshold-based queue policy to outline a closed-loop model for the network. Stability analyses reveal that while the network is vulnerable to instability as the average round-trip time (RTT) of the TCP flows increases, it tolerates a much larger RTT without losing stability when the threshold-based AQM is deployed in an appropriate router. We then define a Katz centrality-based metric to choose the most appropriate router for AQM deployment, and argue that doing so ensures the greatest stabilising effect. Finally, packet-level simulations corroborate that the proposed deployment strategy ensures low-latency operation of the network.

0.29

Stability of Fork-Join Systems with Redundancy and Heterogeneous Servers

cs.IT math.PR ·2026-09-08 ·Chutong Gao, Seyed Iravani, Ohad Perry
similarity 0.55
Abstract · 28 pages, 1 figure. Current status: Reject and Resubmit, Operations Research. Resubmitted on July 26, 2026

We consider the stability problem of fork-join systems with redundancy (FJR) and heterogeneous servers under both static and dynamic capacity-allocation policies. In an $(n,k)$ FJR system, each arriving job is split into $n$ independent tasks, with one task assigned to each of $n$ parallel servers. Once $k \le n$ tasks have been processed, they are joined and the corresponding job departs the system; the remaining $n-k$ unprocessed tasks are then removed and are therefore termed redundant. We first identify the nominal traffic intensity and characterize the maximal stability region, defined as the set of traffic intensities for which there exists an admissible policy that stabilizes the system. We then establish conditions under which this maximal stability region is attained for two classes of policies: static and dynamic. Specifically, we show that for static allocation policies, in which service capacities remain fixed over time, maximality is achieved whenever the fastest server is allocated no more than $1/k$ of the total service capacity. For dynamic allocation policies, in which a fixed total service capacity may be repeatedly reallocated among the servers, we show that maximality is achieved whenever the cumulative capacity allocated to the $j$ shortest queues does not exceed $j/k$ of the total capacity for every $j=1,\ldots,k-1$. Our analysis is based on a projection of the $(n,k)$ FJR system onto a simpler $(k,k)$ system that has no redundancy, together with a novel sample-path comparison argument for multidimensional processes based on the generalized Schur-convex order.

0.31

Seamless Reconfiguration for DAG-BFT (Technical Report)

cs.DC ·2026-10-01 ·Michael Yiqing Hu, Leander Jehl, Paul Franke-Bergmann, Jialin Li, Christian Berger
published similarity 0.55
Abstract · Accepted to OPODIS 26

Byzantine Atomic Broadcast in Asynchronous networks has been studied extensively for decades. In a fully asynchronous system with even one possible crash failure, the FLP impossibility result rules out deterministic consensus, motivating randomized protocols that achieve termination with probability one. More recently, DAG-Rider popularized a new abstraction in which processes continuously reliably broadcast blocks to construct a Directed Acyclic Graph (DAG) and then locally derive a total order using a randomized perfect coin. This separation of dissemination from ordering has renewed interest in asynchronous DAG-based Byzantine Fault Tolerance (BFT) and inspired numerous protocols that improve expected latency or throughput. Reconfiguration, however, remains largely unexplored. Existing DAG-based BFT protocols generally assume a static set of processes, whereas deployed systems must occasionally add or remove nodes in response to operational demands. Existing solutions are not seamless; they either pause the system or delay membership changes until a predetermined epoch boundary. This may be impractical and can introduce downtime. A single agreed switching round is difficult to use seamlessly: by the time processes learn it, the dissemination layer may already have advanced beyond it. In this work, we present a seamless reconfiguration protocol for Asynchronous DAG-based Byzantine Atomic Broadcast. Our protocol allows the DAG to continue growing while the membership and corresponding quorum thresholds change, without halting the system. To the best of our knowledge, ours is the first protocol to provide seamless reconfiguration for DAG-based Byzantine atomic broadcast in a fully asynchronous network.

0.17

Gutenberg: Taming Latency-Critical Cloud Services with Near-Data-Processing

cs.DC cs.AR ·2026-09-06 ·Qiushi Lin, Phillip B. Gibbons, Jovan Stojkovic, Yiwei Zhao
similarity 0.54
Abstract

Latency-critical cloud services place growing pressure on memory while requiring isolation, fairness, and predictable QoS. Near-data processing (NDP) reduces data movement by executing requests close to memory, and prior systems further improve locality through caching and replication. However, writes make replica maintenance expensive, while uneven compute and memory traffic can overload a few NDP units and increase tail latency. Existing throughput-oriented schedulers do not fully address these challenges for co-located cloud services. We present Gutenberg, a CPU+NDP for mutable, latency-critical cloud services. Gutenberg stages subpage updates in a CPU-resident delta buffer, allowing hot writable pages to remain replicated without eager full-page synchronization. It also adopts CPU helper cores to assist request execution when NDP execution or replica maintenance becomes costly. An online controller jointly decides page placement, replication, CPU/NDP execution, and routing using access patterns, queue pressure, and feedback from prior decisions. The system further enforces isolation and fair resource allocation across services. We also model-check CPU--NDP coordination protocol for correctness. We evaluate on TailBench using ZSim with Ramulator-calibrated memory timing. Across evaluated services, Gutenberg outperforms prior systems, reducing average and p99 latency by up to 80.4% and 85.8%. It also improves isolation and fairness while adapting to changing workload behaviors.

0.14