pith. machine review for the scientific record. sign in

arxiv: 2605.12080 · v1 · submitted 2026-05-12 · 💻 cs.IT · cs.DC· cs.NI· cs.PF· math.IT

Recognition: 2 theorem links

· Lean Theorem

On Capacity and Delay of Wireless Networks with Node Failures

Jiandong Li, Junyu Liu, Min Sheng, Wei Li

Authors on Pith no claims yet

Pith reviewed 2026-05-13 04:35 UTC · model grok-4.3

classification 💻 cs.IT cs.DCcs.NIcs.PFmath.IT
keywords wireless ad hoc networksnode failuresnetwork capacitydelay scalingscaling lawsinterference modelresilient networks
0
0 comments X

The pith

In wireless ad hoc networks, random node failures cause both capacity and delay to scale as the square root of the number of reliable nodes over the log of total nodes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper examines how independent random node failures with probability q affect the scaling of capacity and delay in large wireless ad hoc networks. It establishes that both quantities follow the same scaling law involving the effective number of working nodes. The analysis shows that failures create an extra performance penalty even when the count of active nodes is held fixed, and that extra redundant nodes beyond a simple replacement count are needed to restore capacity. The capacity-delay tradeoff stays order one with or without failures.

Core claim

Under random node failures with probability q, the network capacity and delay in wireless ad hoc networks both scale as Θ(sqrt(n(1-q)/log n)). When q is zero this matches the known result without failures. With failures present, the capacity is lower than in a failure-free network having the same number of working nodes, and recovering the loss requires more than the obvious number of redundant nodes. The capacity-delay tradeoff remains O(1) independent of the failure probability.

What carries the argument

The adjusted scaling law for throughput capacity and delay that incorporates the fraction of non-failing nodes (1-q) inside the standard interference-limited random network model.

Load-bearing premise

The standard interference model and random node placement assumptions remain valid exactly as in the failure-free case even after independent node failures occur.

What would settle it

A measurement or simulation in a large network that tracks throughput versus total nodes n and failure probability q to test whether capacity follows Θ(sqrt(n(1-q)/log n)) rather than a different power of (1-q).

Figures

Figures reproduced from arXiv: 2605.12080 by Jiandong Li, Junyu Liu, Min Sheng, Wei Li.

Figure 2
Figure 2. Figure 2: Geometric conditions of single-hop successful transmission [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: The division mode of unit squares edge between the corresponding vertices. The failure proba￾bility for non-empty small squares is q ′ , which is determined by the number of non-faulty nodes within each small square. When q ′ is less than the critical probability qc, the connec￾tivity of the site percolation graph increases sharply to one with probability 1 (forming a unique connected component). Conversel… view at source ↗
Figure 5
Figure 5. Figure 5: Multi-hop transmission strategy independent of the network size. Therefore, the value of ∆′ does not affect the order of network capacity and delay. 3) Multi-hop transmission strategy: A multi-hop transmis￾sion strategy is used to transport data packets between a source node and a destination node. For each source-destination pair i, the corresponding S-D line is constructed by connecting the source node S… view at source ↗
Figure 6
Figure 6. Figure 6: The number of redundancy nodes varies with the node failure [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Network capacity loss vs. node failure probability. [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Network connectivity under different combinations of path loss [PITH_FULL_IMAGE:figures/full_fig_p010_8.png] view at source ↗
read the original abstract

One key challenge in designing resilient large-scale wireless ad hoc networks is to understand how random node failures affect fundamental network performance. In this work, we show that both network capacity and delay scale as \scalebox{0.65}{$\textstyle \Theta\left(\sqrt{\frac{n(1-q)}{\log n}}\right)$}, where $n$ is the total number of nodes and $q$ is the node failure probability. The network capacity degenerates to the classical result given by P. Gupta and P. R. Kumar when $q=0$. Based on these results, we find that even with the same number of non-faulty nodes, a network with $n$ nodes and node failure probability $q$ has lower network capacity than a failure-free network with $n(1-q)$ nodes. To compensate for the network capacity loss caused by random node failures, at least $\epsilon(n,q) nq$ redundant nodes are required, where $\epsilon(n,q)>1$. We further prove that the optimal trade-off between network capacity and delay remains $O(1)$ regardless of node failures, implying that high network capacity and low delay cannot be achieved simultaneously. These results demonstrate robustness against stochastic variations in wireless channels.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper examines the effects of independent node failures with probability q on the asymptotic capacity and delay scaling in large-scale wireless ad hoc networks under the standard Gupta-Kumar interference model. It claims that both capacity and delay scale as Θ(√[n(1-q)/log n]), reducing to the classic Gupta-Kumar result at q=0. The work further asserts that this yields strictly lower capacity than a failure-free network with exactly n(1-q) nodes, requiring at least ε(n,q) n q additional redundant nodes where ε(n,q)>1 to compensate, while the optimal capacity-delay tradeoff remains O(1) independent of q.

Significance. If the derivations hold under the stated model, the results quantify the overhead of stochastic node failures for network resilience and extend the foundational Gupta-Kumar scaling laws to faulty settings. The finding that the capacity-delay tradeoff is unaffected by q is a useful design insight. The explicit comparison to the equivalent non-faulty network and the redundant-node calculation provide concrete guidance for deployment.

major comments (2)
  1. [Abstract (scaling statement and comparison to n(1-q) network)] The claimed scaling Θ(√[n(1-q)/log n]) and the assertion of strictly lower capacity than a failure-free m-node network (m = n(1-q)) rest on using log n rather than log m in the denominator. By the thinning property of the binomial point process, the active nodes form a homogeneous Poisson point process identical to a fresh random placement of m nodes; under the standard interference model this should produce the classic Θ(√(m/log m)) scaling unless transmission range or scheduling parameters are deliberately held fixed to the original n (non-adaptive to realized failures). The abstract supplies no such modeling choice, and the standard derivation does not support the claimed difference. This assumption is load-bearing for the central claim that ε(n,q) > 1 redundant nodes are required.
  2. [Derivation of capacity and delay scaling (presumably §3 or §4)] The abstract states that the results degenerate to the Gupta-Kumar result at q=0 and that the optimal tradeoff remains O(1), but without the full derivation or proof details the central claims cannot be verified for gaps, post-hoc choices, or hidden assumptions in the interference model when nodes fail. Please provide the explicit steps showing how the (1-q) factor and the log-n term arise, including any adaptation (or lack thereof) of the transmission range r(n) and the scheduling policy.
minor comments (2)
  1. [Abstract] The use of scalebox in the abstract for the math expression may cause rendering issues; replace with standard LaTeX sizing commands.
  2. [Model description] Clarify whether the node-failure process is assumed to be static (fixed realization) or dynamic (ongoing failures), as this affects whether parameters can be adapted after failures occur.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments highlight important modeling clarifications that we will address explicitly in the revision. We respond to each major comment below.

read point-by-point responses

  1. Referee: [Abstract (scaling statement and comparison to n(1-q) network)] The claimed scaling Θ(√[n(1-q)/log n]) and the assertion of strictly lower capacity than a failure-free m-node network (m = n(1-q)) rest on using log n rather than log m in the denominator. By the thinning property of the binomial point process, the active nodes form a homogeneous Poisson point process identical to a fresh random placement of m nodes; under the standard interference model this should produce the classic Θ(√(m/log m)) scaling unless transmission range or scheduling parameters are deliberately held fixed to the original n (non-adaptive to realized failures). The abstract supplies no such modeling choice, and the standard derivation does not support the claimed difference. This assumption is load-bearing for the central claim that ε(n,q) > 1 redundant nodes are required.

    Authors: We agree that the distinction is central and will revise the abstract, introduction, and model section to state the assumption explicitly. Our model is non-adaptive: transmission range r(n) and the scheduling policy are fixed in advance based on the design parameter n (and known q), without real-time adjustment to the realized set of active nodes. This reflects practical large-scale deployments where node failures occur randomly and independently, and global reconfiguration after each failure pattern is infeasible. With r(n) held at the Gupta-Kumar value Θ(√(log n / n)), the interference exclusion zones and the chromatic number of the interference graph retain the log n factor even after thinning. Consequently, the total capacity scales as Θ(√(n(1-q)/log n)) rather than the adaptive Θ(√(m/log m)). This yields the claimed strict inequality and the requirement of ε(n,q) > 1 extra nodes. We will add a dedicated paragraph contrasting the adaptive and non-adaptive regimes. revision: yes

  2. Referee: [Derivation of capacity and delay scaling (presumably §3 or §4)] The abstract states that the results degenerate to the Gupta-Kumar result at q=0 and that the optimal tradeoff remains O(1), but without the full derivation or proof details the central claims cannot be verified for gaps, post-hoc choices, or hidden assumptions in the interference model when nodes fail. Please provide the explicit steps showing how the (1-q) factor and the log-n term arise, including any adaptation (or lack thereof) of the transmission range r(n) and the scheduling policy.

    Authors: We will expand §§3–4 with complete proofs. The key steps (to be inserted verbatim) are: (i) Nodes are placed uniformly in the unit square; each fails independently with probability q, producing a thinned PPP of intensity λ = n(1-q). (ii) The transmission range is set once as r(n) = Θ(√(log n / n)) and remains fixed (non-adaptive). (iii) Under the protocol interference model, each transmitter occupies an exclusion disk of area Θ(r²); the maximum number of concurrent transmissions is therefore Θ(1/r²) = Θ(n/log n). (iv) The interference graph is colored with Θ(log n) colors, so each active node obtains a transmission opportunity every Θ(log n) slots. The (1-q) factor enters both through the fraction of active nodes and through the reduced number of end-to-end flows. Summing over the Θ(n/log n) concurrent links yields total capacity Θ(√(n(1-q)/log n)). When q = 0 the expression collapses to the classic Gupta-Kumar result. Delay scaling follows from the same hop-count and queueing analysis, again with fixed r(n). The capacity-delay tradeoff is obtained by parameterizing r(n,α) = n^{-α} and optimizing α; the resulting relation C·√D = O(1) is independent of q. All lemmas and concentration bounds will be supplied in the revision. revision: yes

Circularity Check

0 steps flagged

No circularity: scaling extends Gupta-Kumar via density adjustment in standard model

full rationale

The claimed scaling follows from applying the classic random geometric graph analysis (connectivity threshold, interference exclusion, hop count) to the thinned active-node process with density scaled by (1-q). Because the derivation starts from the same first-principles assumptions as Gupta-Kumar and inserts the failure probability directly into the node density, the result is not obtained by fitting a parameter to a subset of data and renaming it a prediction, nor by any self-referential definition or load-bearing self-citation. The observation that capacity is lower than for an exactly m-node network arises from the modeling choice to keep transmission range and scheduling parameters fixed to the original n (non-adaptive to realized failures), which is an explicit assumption rather than a hidden reduction to the input. The trade-off result O(1) likewise inherits directly from the same non-circular extension.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard random geometric graph and interference model assumptions from prior wireless network literature plus the new independent failure model; no new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Nodes are placed uniformly at random in a unit square and communicate under the standard protocol or physical interference model of Gupta and Kumar.
    The scaling derivation inherits the geometric and interference assumptions of the baseline result.
  • domain assumption Each node fails independently with fixed probability q, independent of location and traffic.
    The paper models stochastic node failures as i.i.d. Bernoulli trials.

pith-pipeline@v0.9.0 · 5528 in / 1481 out tokens · 75386 ms · 2026-05-13T04:35:59.688365+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Cyclic-pursuit-based circular formation control of mobile agents with limited communication ranges and communication delays,

    B. Y . Zheng, C. Song, and L. Liu, “Cyclic-pursuit-based circular formation control of mobile agents with limited communication ranges and communication delays,” IEEE-CAA J. Autom. Sin. , vol. 10, pp. 1860–1870, 2023

    work page 2023

  2. [2]

    Intelligent communication and networking key technologies for manned/unmanned cooperation: State-of-the-art and trends,

    H. Yin, J. B. Wei, H. T. Zhao, J. Zhang et al., “Intelligent communication and networking key technologies for manned/unmanned cooperation: State-of-the-art and trends,” J. Commun., vol. 45, no. 1, pp. 1–17, 2024, in Chinese

    work page 2024

  3. [3]

    The capacity of wireless networks,

    P. Gupta and P. R. Kumar, “The capacity of wireless networks,” IEEE Trans. Inf. Theory, vol. 46, pp. 388–404, 2000

    work page 2000

  4. [4]

    An intelligent adaptive architecture for wireless communication in complex scenarios,

    H. Yin, J. B. Wei, H. T. Zhao et al., “An intelligent adaptive architecture for wireless communication in complex scenarios,” Sci. China Inf. Sci. , vol. 51, pp. 294–304, 2021, in Chinese

    work page 2021

  5. [5]

    Cyber-physical framework for uav intelligent communications,

    H. J. Wang, H. T. Zhao, B. Q. Ren et al. , “Cyber-physical framework for uav intelligent communications,” Sci. China Inf. Sci. , vol. 52, pp. 2141–2154, 2022, in Chinese

    work page 2022

  6. [6]

    Toward an internet of battlefield things: A resilience perspective,

    T. Abdelzaher, N. Ayanian, T. Basar et al. , “Toward an internet of battlefield things: A resilience perspective,” Computer, vol. 51, pp. 24– 36, 2018

    work page 2018

  7. [7]

    Mobility increases the capacity of ad hoc wireless networks,

    M. Grossglauser and D. N. C. Tse, “Mobility increases the capacity of ad hoc wireless networks,” IEEE/ACM Trans. Netw., vol. 10, pp. 477–486, 2002

    work page 2002

  8. [8]

    Robust capacity of wireless networks under cascading failures,

    W. Li, J. Y . Liu, M. Sheng et al., “Robust capacity of wireless networks under cascading failures,” in Proc. IEEE GLOBECOM , Rio de Janeiro, Brazil, 2022, pp. 6013–6018

    work page 2022

  9. [9]

    The capacity of k-connectivity d-dimensional wireless networks with node failure,

    ——, “The capacity of k-connectivity d-dimensional wireless networks with node failure,” Sci. China Inf. Sci. , vol. 66, p. 209302, 2023

    work page 2023

  10. [10]

    Robust throughput capacity of multi-connectivity wireless networks,

    M. Sheng, W. Li, J. Liu, and J. Li, “Robust throughput capacity of multi-connectivity wireless networks,” IEEE Trans. Commun. , vol. 73, pp. 4228–4240, 2025

    work page 2025

  11. [11]

    Capacity, delay and mobility in wireless ad-hoc networks,

    N. Bansal and Z. Liu, “Capacity, delay and mobility in wireless ad-hoc networks,” in Proc. IEEE INFOCOM , San Francisco, CA, USA, 2003, pp. 1553–1563

    work page 2003

  12. [12]

    Capacity and delay tradeoffs for ad hoc mobile networks,

    M. J. Neely and E. Modiano, “Capacity and delay tradeoffs for ad hoc mobile networks,” IEEE Trans. Inf. Theory , vol. 51, pp. 1917–1937, 2005

    work page 1917

  13. [13]

    Delay and capacity trade-offs in mobile ad hoc networks: A global perspective,

    G. Sharma, R. Mazumdar, and N. Shroff, “Delay and capacity trade-offs in mobile ad hoc networks: A global perspective,” IEEE/ACM Trans. Netw., vol. 15, pp. 981–992, 2007

    work page 2007

  14. [14]

    Optimal delay-throughput tradeoffs in mobile ad hoc networks,

    L. Ying, S. Yang, and R. Srikant, “Optimal delay-throughput tradeoffs in mobile ad hoc networks,” IEEE Trans. Inf. Theory, vol. 54, pp. 4119– 4143, 2008

    work page 2008

  15. [15]

    Optimal throughput- delay scaling in wireless networks part i: The fluid model,

    A. El Gamal, J. Mammen, B. Prabhakar et al. , “Optimal throughput- delay scaling in wireless networks part i: The fluid model,” IEEE Trans. Inf. Theory, vol. 52, pp. 2568–2592, 2006

    work page 2006

  16. [16]

    On the throughput-delay tradeoff in georouting networks,

    P. Jacquet, S. Malik, B. Mans, and A. Silva, “On the throughput-delay tradeoff in georouting networks,” IEEE Trans. Inf. Theory , vol. 62, pp. 3230–3242, 2016

    work page 2016

  17. [17]

    Asymptotic distribution of the number of isolated nodes in wireless ad hoc networks with bernoulli nodes,

    C. W. Yi, P. J. Wan, X. Y . Li et al. , “Asymptotic distribution of the number of isolated nodes in wireless ad hoc networks with bernoulli nodes,” IEEE Trans. Commun. , vol. 54, pp. 510–517, 2006

    work page 2006

  18. [18]

    Scaling laws for ad-hoc wireless networks: An information theoretic approach,

    F. Xue and P. R. Kumar, “Scaling laws for ad-hoc wireless networks: An information theoretic approach,” Found. Trends Netw., pp. 1–125, 2006

    work page 2006

  19. [19]

    Internets in the sky: The capacity of three dimensional wireless networks,

    P. Gupta and P. R. Kumar, “Internets in the sky: The capacity of three dimensional wireless networks,” Commun. Inf. Syst. , vol. 1, pp. 33–50, 2001

    work page 2001

  20. [20]

    A deterministic approach to through- put scaling in wireless networks,

    S. R. Kulkarni and P. Viswanath, “A deterministic approach to through- put scaling in wireless networks,” IEEE Trans. Inf. Theory , vol. 50, pp. 1041–1049, 2004

    work page 2004

  21. [21]

    Franceschetti and R

    M. Franceschetti and R. Meester, Random Networks for Communication: From Statistical Physics to Information Systems . Cambridge Univ. Press, 2008

    work page 2008

  22. [22]

    The impact of channel ran- domness on coverage and connectivity of ad hoc and sensor networks,

    D. Miorandi, E. Altman, and G. Alfano, “The impact of channel ran- domness on coverage and connectivity of ad hoc and sensor networks,” IEEE Trans. Wireless Commun. , vol. 7, pp. 1062–1072, 2008

    work page 2008

  23. [23]

    Ad hoc wireless networks with noisy links,

    L. Booth, J. Bruck, M. Cook et al. , “Ad hoc wireless networks with noisy links,” in Proc. IEEE ISIT , 2003, p. 386

    work page 2003