Fluid limits for interacting queues in sparse dynamic graphs

Basic Information

• Paper ID: 2305.13054
• Title: Fluid limits for interacting queues in sparse dynamic graphs
• Authors: Diego Goldsztajn (Universidad ORT Uruguay), Sem C. Borst (Eindhoven University of Technology), Johan S.H. van Leeuwaarden (Tilburg University)
• Classification: math.PR (Probability Theory)
• Publication Date: October 11, 2025 (arXiv version)
• Paper Link: https://arxiv.org/abs/2305.13054

Abstract

This paper investigates a network consisting of n single-server queues, where tasks arrive independently at each server at rate λₙ. Servers are connected through a graph that is resampled at rate μₙ and is symmetric with respect to servers. Each task is dispatched to the shortest queue in its graph neighborhood. The research aims to provide deep understanding of how dynamic network structure affects load balancing dynamics, particularly the occupancy process (which describes the empirical distribution of tasks across servers). When n→∞, λₙ/n→λ, and μₙ→∞, this dependency vanishes, and the fluid limit of the occupancy process is given by a system of differential equations that depends only on λ and the limiting degree distribution of the graph.

Research Background and Motivation

Problem Background

1. Complexity of load balancing systems: In modern distributed systems, tasks must be efficiently allocated across multiple servers. Traditional load balancing research has primarily focused on complete graphs or static network topologies.
2. Practical demands of dynamic networks: In real applications, network topologies frequently change, such as in mobile ad hoc networks, peer-to-peer networks, and data center network topology adjustments.
3. Importance of sparse graphs: In practical load balancing systems, sparse graphs (with maximum degree uniformly bounded in n) are natural choices due to communication overhead considerations.

Research Challenges

1. Lack of exchangeability: In dynamic graph settings, servers with the same number of tasks are no longer exchangeable, as different servers typically have different neighborhood structures.
2. Mathematical analysis difficulties: The dynamics of the occupancy process depend not only on the occupancy process itself but also on the dynamic graph Gₙ and the process Xₙ describing the number of tasks at each server.
3. Limitations of existing theory: Previous research has primarily addressed complete graphs (supermarket model) or static graph cases, with dynamic cases lacking rigorous mathematical analysis.

Core Contributions

1. Established fluid limit theory for queue networks on dynamic sparse graphs: Proved that when the graph resampling rate is sufficiently fast, the occupancy process converges to a deterministic limit described by an infinite-dimensional system of differential equations.
2. Demonstrated universality of the limit: The fluid limit depends only on the probability generating function of the limiting degree distribution, independent of other structural properties of the graph.
3. Established convergence of stationary distributions: Under Poisson resampling assumptions, proved that stationary occupancy states converge to globally attractive equilibrium points of the differential equations.
4. Revealed phase transition phenomena in degree distributions: Discovered significant differences in system performance depending on whether the degree distribution has mass at zero.
5. Provided performance lower bounds: Derived tight lower bounds for equilibrium points under sparsity constraints and identified optimal degree distributions.

Detailed Methodology

Problem Formulation

The paper studies a queue network with n servers where:

• Tasks arrive at each server via Poisson processes at rate λₙ/n
• Service times follow exponential distributions with parameter 1
• Servers are connected through a directed graph resampled at rate μₙ
• Tasks are dispatched to the shortest queue in their neighborhood

Model Architecture

Occupancy Process Definition

The occupancy process qₙ(t,i) is defined as the proportion of servers with at least i tasks at time t:

qₙ(t,i) := (1/n) ∑ᵤ₌₁ⁿ 1{Xₙ(t,u)≥i}

Stochastic Equation

The occupancy process satisfies the stochastic equation:

qₙ(t,i) = qₙ(0,i) + (1/n)Aₙ(Gₙ,Xₙ,t,i) - (1/n)Dₙ(qₙ,t,i)

where Aₙ counts arrivals to servers with exactly i-1 tasks, and Dₙ counts departures from servers with exactly i tasks.

Key Assumptions

Assumption 1: There exist constants λ > 0 and probability mass function {p(d)} such that:

• lim_{n→∞} λₙ/n = λ
• lim_{n→∞} pₙ(d) = p(d) for all d ∈ ℕ
• The resampling process satisfies pseudo-separation events

Technical Innovations

1. Pseudo-Separation Property

Introduced the concept of "pseudo-separation events," a technical condition requiring:

• Maximum intervals between consecutive resampling times tend to zero
• Expectation of certain random variables involving arrivals and departures tends to zero

2. Process Decomposition

Decomposed the right-hand side of the occupancy process into:

• Vanishing process vₙ: Contains Lₙ (state difference term), Mₙ (martingale term), and Poisson process correction terms
• Drift process wₙ: Contains the main deterministic terms

3. Martingale Method

Constructed discrete-time martingales {Mᵐₙ(i) : m ≥ 0}, exploiting the independence of graph resampling to establish martingale properties, and using Doob's maximal inequality to control their behavior.

Experimental Setup

Graph Topologies

The paper considers three undirected graph topologies with n=12 nodes:

1. Cycle graph: All nodes have degree 2
2. Separated triangles: All nodes have degree 2
3. Double star graph: Degree distribution pₙ(2)=(n-2)/n, pₙ(n-1)=2/n

Simulation Parameters

• Number of servers: n = 1500, 5000
• Arrival rate: λₙ = 9n/10 (load 0.9)
• Resampling rate: μₙ = log log n, log n
• Resampling process: Poisson process

Performance Metrics

• Time-averaged occupancy process qₙ(t,i)
• Comparison with fluid limit solution q*(i)
• Mean response time R

Experimental Results

Main Results

Static vs. Dynamic Graph Performance

Experiments demonstrate that dynamic resampling significantly improves performance:

• For all three topologies, time-averaged qₙ(i) under dynamic conditions is smaller than under static conditions
• The double star topology under static conditions performs equivalently to n independent single-server queues

Fluid Approximation Accuracy

• For cycle and separated triangle graphs at μₙ = log log n, sample paths remain close to the differential equation solution (4)
• For double star graphs at μₙ = log n, approximation is insufficient, demonstrating the necessity of the pseudo-separation condition

Phase Transition in Degree Distribution

Proposition 6 reveals a critical phase transition:

• When m = min{d ≥ 0 : p(d) > 0} = 0, q*(i) is bounded between two geometric sequences
• When m > 0, q*(i) is bounded between two doubly exponential decay sequences

Performance Lower Bounds

Proposition 7 provides optimal results under sparsity constraints:

• Under the constraint ∑ᵢ ip(i) ≤ d, the lower bound is achieved if and only if d ∈ ℕ and p(d) = 1
• Deterministic degree distributions are optimal under sparsity constraints

Related Work

Supermarket Model

• Complete graph case: Classical power-of-d scheme by Vvedenskaya et al.
• Mean-field approach: Mean-field arguments exploiting server exchangeability

Queue Systems on Static Graphs

• Edge expansion properties: Mukherjee et al. requiring appropriate edge expansion properties
• Diverging minimum degree: Budhiraja et al. analyzing static graphs with diverging minimum degree and appropriate regularity

Interacting Particle Systems

• Euclidean space: Classical results by Oelschläger
• Sparse graphs: Non-Markovian interacting particle systems by Ganguly and Ramanan

Conclusions and Discussion

Main Conclusions

1. Universality result: Load balancing systems on dynamic sparse graphs converge under appropriate conditions to a fluid limit depending only on the degree distribution
2. Phase transition phenomenon: Whether the degree distribution has mass at zero leads to fundamental differences in system performance
3. Optimality: Deterministic degree distributions achieve optimal performance under sparsity constraints

Limitations

1. Pseudo-separation condition: Requires resampling rate μₙ→∞ satisfying specific conditions, potentially limiting practical applications
2. Sparsity assumption: Primarily focuses on cases where maximum degree is uniformly bounded
3. Exponential service times: Assumes unit-mean exponential service times

Future Directions

1. More general service time distributions: Extension to non-exponential service times
2. Finite resampling rates: Investigation of behavior when μₙ is bounded
3. Network optimization: Design of optimal dynamic network strategies based on theoretical results

In-Depth Evaluation

Strengths

1. Theoretical rigor: Provides the first rigorous fluid limit theory for queue networks on dynamic graphs
2. Technical innovation: Cleverly addresses the challenge of lacking exchangeability in dynamic settings
3. Practical insights: Reveals fundamental effects of degree distribution on performance, providing design guidance
4. Complete analysis: Comprehensive theoretical framework from transient to stationary states

Weaknesses

1. Complex conditions: The technical conditions of pseudo-separation are complex and difficult to verify in practice
2. Limited simulations: Numerical experiments are relatively simple, lacking large-scale practical application validation
3. Extensibility: Unclear whether the theory can be extended to more general network models

Impact

1. Theoretical contribution: Establishes mathematical foundations for queue theory on dynamic networks
2. Practical value: Provides design principles for distributed systems and load balancing
3. Methodology: Proposed technical methods may be applicable to other dynamic network problems

Applicable Scenarios

• Dynamic load balancing in cloud computing and data centers
• Task allocation in mobile ad hoc networks
• Resource scheduling in peer-to-peer networks
• Any system requiring load balancing on dynamically changing sparse networks

References

The paper cites 63 related references, primarily including:

• Classical queueing theory literature (Vvedenskaya et al.'s supermarket model)
• Mean-field theory literature (Kurtz's limit theorems)
• Interacting systems on graphs literature (Ganguly and Ramanan's work)
• Load balancing systems literature (Mukherjee et al.'s static graph analysis)