pith. sign in

arxiv: 2604.19978 · v1 · submitted 2026-04-21 · 💻 cs.NI

On the Optimality of Network Topology Discovery in Single-Hop Bounded-Interference Networks

Tolunay Seyfi , Erfan Khadem , Fatemeh Afghah This is my paper

Pith reviewed 2026-05-10 01:01 UTC · model grok-4.3

classification 💻 cs.NI
keywords topology discoverysingle-hop wireless networksbounded interferencefinite-field schedulingPRISMinterference identification
0
0 comments X

The pith

PRISM identifies up to L interferers per receiver among K transmitters using finite-field modular scheduling.

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

The paper proposes PRISM, a deterministic scheduling method that labels each of K transmitters with elements from a finite field and arranges transmissions through modular multiplication under a second prime modulus. This arrangement guarantees that every receiver experiences a sufficient number of singleton transmissions from its at most L interfering transmitters, allowing each receiver to identify exactly which transmitters interfere with it. The construction yields full topology discovery in expected O(L(1+δ) log K) rounds with failure probability K^{-δ} and in O(L² log K) rounds when made fully deterministic. A reader would care because knowing the exact interference neighborhood at each receiver lets wireless systems allocate resources and avoid collisions with far less overhead than exhaustive or random probing.

Core claim

PRISM achieves full discovery in O(L(1+δ)log K) rounds in expectation with failure probability K^{-δ}, and in O(L² log K) rounds deterministically, by assigning finite-field labels to transmitters and scheduling transmissions via modular multiplication and a second prime modulus so that each receiver observes singleton transmissions from its interfering set.

What carries the argument

PRISM (Pseudorandom Residue-based Indexed Scheduling Method), which uses finite-field modular multiplication under two primes to produce singleton transmissions at each receiver.

If this is right

  • Full interference topology can be recovered without any prior graph knowledge.
  • Expected completion time scales linearly with the interference bound L and logarithmically with network size K.
  • A deterministic variant trades the expectation for a quadratic dependence on L.
  • Simulations confirm practical scaling near 0.9 L log K rounds and identify parameter ratios q/L that minimize average or tail completion time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The logarithmic dependence on K suggests topology discovery can be repeated periodically in mobile settings without dominating channel time.
  • The same modular-label technique could be combined with existing medium-access protocols to bootstrap interference-aware scheduling in ad-hoc deployments.
  • If the single-hop assumption holds only locally, the method could be applied inside clusters to reduce global discovery cost.

Load-bearing premise

The network is single-hop, each receiver sees at most L interfering transmitters, and all transmissions can be scheduled perfectly according to the finite-field rules with no synchronization errors or hidden terminals.

What would settle it

A measured completion time that grows faster than O(L² log K) rounds in a controlled single-hop testbed with known L and perfect scheduling would falsify the deterministic bound.

Figures

Figures reproduced from arXiv: 2604.19978 by Erfan Khadem, Fatemeh Afghah, Tolunay Seyfi.

Figure 1
Figure 1. Figure 1: Heatmaps of PRISM performance as a function of [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: Comparison of mean network completion time (dis [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 2
Figure 2. Figure 2: Scaling behavior of PRISM. IV. CONCLUSION We presented PRISM, a deterministic and non-interactive framework for topology discovery in single-hop wireless net￾works under collision-channel constraints. PRISM uses mod￾ular arithmetic over multiplicative residue classes to construct fixed discovery schedules without feedback or probabilistic access. We showed that PRISM achieves complete discovery in O(L(1 + … view at source ↗
read the original abstract

We propose \emph{PRISM} (\textbf{Pseudorandom Residue-based Indexed Scheduling Method}), a deterministic topology-discovery framework for single-hop wireless networks with bounded interference. Each receiver has at most \(L\) interfering transmitters among \(K\) transmitters and identifies them through singleton transmissions. PRISM assigns finite-field labels to transmitters and schedules transmissions via modular multiplication and a second prime modulus. It achieves full discovery in \(O(L(1+\delta)\log K)\) rounds in expectation with failure probability \(K^{-\delta}\), and in \(O(L^2\log K)\) rounds deterministically. Simulations show \(\approx 0.9L\log K\) scaling, with \(q/L\approx1.2\) minimizing mean completion time and \(q/L\approx1.4\text{--}1.6\) improving tail performance.

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

1 major / 4 minor

Summary. The manuscript proposes PRISM, a pseudorandom residue-based indexed scheduling method for topology discovery in single-hop wireless networks with bounded interference. Each receiver has at most L interfering transmitters among K transmitters. Transmitters receive finite-field labels in GF(q) and transmissions are scheduled via modular multiplication with a second prime modulus to produce singleton transmissions. The central claims are that this yields full discovery in O(L(1+δ) log K) rounds in expectation (failure probability K^{-δ}) and deterministically in O(L² log K) rounds, with simulations confirming ≈0.9 L log K scaling and identifying q/L ratios that minimize mean or tail completion time.

Significance. If the bounds and singleton guarantee hold, the work supplies a clean, constructive upper bound on discovery latency that improves on naive L K scaling and is grounded in standard separating-system techniques. The explicit finite-field construction, the tunable expected-time result with explicit failure probability, the derandomized deterministic version, and the simulation-based guidance on the second modulus parameter q are all positive features. These elements together make the result potentially useful for interference-limited wireless settings where deterministic guarantees are desirable.

major comments (1)
  1. [Derandomization / deterministic bound section] The deterministic O(L² log K) claim is stated to follow from derandomization of the probabilistic construction, but the manuscript does not specify the derandomization technique employed nor verify that the resulting bound remains strictly O(L² log K) without additional logarithmic factors. This detail is load-bearing for the deterministic half of the main theorem.
minor comments (4)
  1. [Simulation section] Simulation results report ≈0.9 L log K scaling and specific q/L optima but omit the number of Monte Carlo trials, error bars, or variance estimates, making it difficult to judge the statistical reliability of the observed scaling.
  2. [Parameter tuning / simulation analysis] The abstract and parameter discussion state q/L ≈1.2 minimizes mean completion time and q/L ≈1.4–1.6 improves tail performance, yet the manuscript does not clarify whether these ratios are derived analytically or found empirically and whether they remain stable across wide ranges of K and L.
  3. [Abstract and main theorem statement] The allowable range for the parameter δ (appearing in both the expected round bound and the failure probability K^{-δ}) is not stated explicitly; adding the constraint δ > 0 and any upper limits would improve clarity.
  4. [Introduction / related work] A brief comparison (even asymptotic) to prior topology-discovery or interference-scheduling protocols would help situate the improvement over random access or other baselines.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment of the significance of PRISM, and the constructive comment. We address the single major comment below and will incorporate the requested clarification in the revision.

read point-by-point responses

  1. Referee: [Derandomization / deterministic bound section] The deterministic O(L² log K) claim is stated to follow from derandomization of the probabilistic construction, but the manuscript does not specify the derandomization technique employed nor verify that the resulting bound remains strictly O(L² log K) without additional logarithmic factors. This detail is load-bearing for the deterministic half of the main theorem.

    Authors: We agree that the derandomization technique and the preservation of the O(L² log K) bound merit explicit treatment. In the revised manuscript we will insert a new subsection (immediately following the probabilistic analysis) that specifies the derandomization method: we apply the method of conditional expectations to the random choices of the second prime modulus q and the finite-field labels. We will prove that there are at most O(LK) bad events (one per receiver-transmitter pair and per residue class), each with probability at most 1/poly(K), so that a single pass of conditional expectations yields a deterministic schedule whose length is strictly O(L² log K) with no hidden logarithmic factors. A formal lemma will be added to certify the bound. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation chain starts from the explicit PRISM construction (finite-field labels in GF(q), modular multiplication for slot selection, and a second prime for derandomization) and proceeds via a standard probabilistic covering argument whose success probability is bounded by a union bound over K transmitters, yielding the O(L(1+δ)log K) expectation with failure K^{-δ}. The deterministic O(L² log K) bound follows by standard derandomization. These steps are self-contained mathematical arguments that do not reduce to a fitted parameter, a self-definition, or a load-bearing self-citation; the singleton-transmission guarantee is shown directly from the separating-system properties of the schedule. Simulations are reported separately as empirical scaling checks and do not serve as inputs to the claimed bounds.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

The central claims rest on the bounded-interference model (at most L interferers per receiver) and the ability to perform deterministic scheduling in a single-hop setting; simulations introduce a tunable parameter q whose optimal ratios are reported but not derived from first principles.

free parameters (1)
  • q (second modulus parameter)
    The ratio q/L is tuned in simulations to minimize mean completion time (≈1.2) or improve tail performance (1.4-1.6); this value is chosen empirically rather than fixed by the theory.
axioms (2)
  • domain assumption Each receiver experiences at most L interfering transmitters in a single-hop network.
    Invoked to bound the number of singleton transmissions needed for identification.
  • domain assumption Transmissions can be scheduled perfectly according to finite-field modular multiplication without errors or collisions outside the model.
    Required for the deterministic and probabilistic guarantees to hold.

pith-pipeline@v0.9.0 · 5450 in / 1365 out tokens · 47821 ms · 2026-05-10T01:01:51.062574+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    V . V . Veeravalli and A. E. Gamal,Interference Management in Wireless Networks: Fundamental Bounds and the Role of Cooperation. Cam- bridge, U.K.: Cambridge University Press, 2018

    work page 2018

  2. [2]

    Efficient algo- rithms for neighbor discovery in wireless networks,

    S. Vasudevan, M. Adler, D. Goeckel, and D. Towsley, “Efficient algo- rithms for neighbor discovery in wireless networks,”IEEE/ACM Trans. Netw., vol. 21, no. 1, pp. 69–83, Feb 2013

    work page 2013

  3. [3]

    Topology discovery for network fault management using mobile agents in ad-hoc networks,

    A. Ahmed and B. H. Far, “Topology discovery for network fault management using mobile agents in ad-hoc networks,” inProc. Can. Conf. Electr . Comput. Eng., Saskatoon, SK, Canada, May 2005, pp. 2041–2044

    work page 2005

  4. [4]

    Fast detection of compact topology representation for wireless networks,

    Y . Bejerano, K. Guo, and T. Nandagopal, “Fast detection of compact topology representation for wireless networks,” inProc. Conf. Local Comput. Netw. (LCN), Oct 2015, pp. 535–543

    work page 2015

  5. [5]

    Design and evaluation of a hybrid d2d discovery mechanism in 5g cellular networks,

    M. Li and H.-L. Tsai, “Design and evaluation of a hybrid d2d discovery mechanism in 5g cellular networks,” inProc. Int. Conf. Ubiquitous Future Netw. (ICUFN), Jul 2018, pp. 641–643

    work page 2018

  6. [6]

    Learning the interference graph of a wireless network,

    J. Yang, S. C. Draper, and R. Nowak, “Learning the interference graph of a wireless network,”IEEE Trans. Signal Inf. Process. Netw., vol. 3, no. 3, pp. 631–646, Sep 2017

    work page 2017

  7. [7]

    On–off necklace codes for asynchronous mutual discovery,

    O. Tirkkonen, Z. Li, L. Wei, and A. V . Vinel, “On–off necklace codes for asynchronous mutual discovery,” inProc. IEEE 28th Annu. Int. Symp. Pers. Indoor Mobile Radio Commun. (PIMRC), Oct 2017, pp. 1–6

    work page 2017

  8. [8]

    On the complexity of radio communication,

    N. Alon, A. Bar-Noy, N. Linial, and D. Peleg, “On the complexity of radio communication,” inProc. 21st Annu. Symp. Theory Comput. (STOC), 1989, pp. 274–285

    work page 1989

  9. [9]

    A number theoretic approach for fast discovery of single-hop wireless networks,

    T. Seyfi, A. P. Mohamed, and A. E. Gamal, “A number theoretic approach for fast discovery of single-hop wireless networks,”IEEE Networking Letters, vol. 3, no. 2, pp. 89–93, 2021

    work page 2021

  10. [10]

    Degrees of freedom of interference channels with comp transmission and reception,

    V . S. Annapureddy, A. El Gamal, and V . V . Veeravalli, “Degrees of freedom of interference channels with comp transmission and reception,” IEEE Transactions on Information Theory, vol. 58, no. 9, pp. 5740– 5760, 2012

    work page 2012

  11. [11]

    Interference channels with coordinated multipoint transmission: Degrees of freedom, message assignment, and fractional reuse,

    A. E. Gamal, V . S. Annapureddy, and V . V . Veeravalli, “Interference channels with coordinated multipoint transmission: Degrees of freedom, message assignment, and fractional reuse,”IEEE Transactions on Infor- mation Theory, vol. 60, no. 6, pp. 3483–3498, 2014

    work page 2014

  12. [12]

    The role of transmitter cooperation in linear interference networks with block erasures,

    Y . Karacora, T. Seyfi, and A. E. Gamal, “The role of transmitter cooperation in linear interference networks with block erasures,” in2017 51st Asilomar Conference on Signals, Systems, and Computers, 2017, pp. 1427–1431

    work page 2017

  13. [13]

    The aloha system: another alternative for computer communications,

    N. Abramson, “The aloha system: another alternative for computer communications,” inProceedings of the November 17-19, 1970, Fall Joint Computer Conference, ser. AFIPS ’70 (Fall). New York, NY , USA: Association for Computing Machinery, 1970, p. 281–285. [Online]. Available: https://doi.org/10.1145/1478462.1478502

    work page doi:10.1145/1478462.1478502 1970

  14. [14]

    Packet switching in radio channels: Part i - carrier sense multiple-access modes and their throughput-delay characteristics,

    L. Kleinrock and F. Tobagi, “Packet switching in radio channels: Part i - carrier sense multiple-access modes and their throughput-delay characteristics,”IEEE Transactions on Communications, vol. 23, no. 12, pp. 1400–1416, 1975

    work page 1975

  15. [15]

    Asymmetric block design-based neighbor discovery protocol in sensor networks,

    S. Choi and G. Yi, “Asymmetric block design-based neighbor discovery protocol in sensor networks,”Sustainability, vol. 8, no. 5, 2016. [Online]. Available: https://www.mdpi.com/2071-1050/8/5/431

    work page 2016

  16. [16]

    Asynchronous massive access and neighbor discovery using ofdma,

    X. Chen, L. Liu, D. Guo, and G. W. Wornell, “Asynchronous massive access and neighbor discovery using ofdma,”IEEE Transactions on Information Theory, vol. 69, no. 4, pp. 2364–2384, 2023

    work page 2023