Pith. sign in

REVIEW 3 major objections 5 minor 11 references

Straggling for Covert Message Passing on Complete Graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Splitting and coding a message lets covert relay passers trade detection risk against delivery time.

desk verdict Correct, modest covert-messaging model; the headline covertness formula needs an explicit independence assumption about the warden, and Model 2 has a small internal inconsistency, but the core analysis is sound. read the letter →

arxiv 1908.05570 v2 pith:KLH4LJB2 submitted 2019-08-15 cs.CR

Pei Peng , Nikolas Melissaris , Emina Soljanin , Bill Lee , Huafeng Fan , Anton Maliev This is my paper · ORCID
classification cs.CR MSC 05C8168M20
keywords covertcommunicationrandomwalkcompletegraphcouponcollectorerasurecodingdelaywardendetectionredundancy
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper introduces a mobile multi-agent protocol for covert message passing: Alice splits a message into $k$ chunks, encodes them into $n$ redundant pieces, leaves pieces with different relays on a city graph, and Bob recovers the message by collecting any $k$ pieces. The authors derive explicit formulas for the probability that a patrolling warden detects any chunk, and for the expected time until delivery, in two warden models. The central finding is a tunable tradeoff: redundancy and chunking can reduce expected delivery time, because Bob can stop once he meets any $k$ of $n$ holders, but every extra transmission increases the chance Willie sees something. The paper computes where the optimal balance lies and confirms the formulas by simulation.

What carries the argument

The machinery is a pairing of a shifted-exponential transmission-time model (a transmission of a chunk lasts at least $m/k$ plus an exponentially distributed extra amount of rate $\lambda$) with coupon-collector random-walk counting on a complete graph (a graph in which every pair of vertices is connected). For detection, the key step is integrating the probability that the warden's uniform arrival time falls inside the shifted-exponential transmission, which gives the per-chunk $P_d$ and then the product formula $P_c=(1-P_d)^{n+k}$. For delay, the key step is the coupon-collector count $s(H_r-H_{r-n})$ for Alice to visit $n$ of $r$ relays and $s(H_n-H_{n-k})$ for Bob to visit $k$ of $n$ holders; these harmonic-number terms carry the whole delay analysis. The pairing is what makes redundancy useful: Bob only needs any $k$ of the $n$ stored chunks, so increasing $n$ shortens his collecting walk even though it lengthens Alice's dissemination walk.

What would settle it

Run the described protocol on a 50-vertex complete graph with $r=10$ relays, message length $m=10$, rate $\lambda=1$, warden window $W=50$, and parameters $k=3$, $n=5$; if the measured fraction of chunk transmissions Willie detects differs from $1/(\lambda W)+m/(kW)-e^{-\lambda(W-m/k)}/(\lambda W)$ beyond sampling error, or the mean total time differs from $(n+k)/\lambda+(n/k+1)m+s(H_r+H_n-H_{r-n}-H_{n-k})$, the paper's core formulas fail.

Watch

Extended reading notes

Core claim

The paper's central claim is that the covertness-delay tradeoff of the relay protocol is exactly described by two formulas. If a chunk transmission lasts a shifted exponential time with shift $m/k$ and tail rate $\lambda$, and Willie's check of a vertex arrives uniformly in $[0,W]$, then a single transmission is detected with probability $P_d = 1/(\lambda W) + m/(kW) - e^{-\lambda(W - m/k)}/(\lambda W)$ when $W \ge m/k$, and with probability 1 otherwise. Because Alice uploads $n$ chunks and Bob downloads $k$, the whole message stays covert with probability $P_c = (1-P_d)^{n+k}$. In the first warden model, the expected total transfer time is $E[T_{\mathrm{tot}}] = (n+k)/\lambda + (n/k+1)m + s(H_r + H_n - H_{r-n} - H_{n-k})$; in the second, where Willie can watch movements and agents spend equal time at every vertex, it is $((1/\lambda)+m/k+1)s(H_r+H_n-H_{r-n}-H_{n-k})$, minimized near $n = \sqrt{rk+k}-1$. These expressions show that $n$ and $k$ control a genuine tradeoff: redundancy and chunking can speed up delivery, but they add transmissions that Willie can catch.

Load-bearing premise

The load-bearing premise is that Willie's patrols are independent and random -- his arrival time at any checked vertex is uniform over a window of length $W$, and each chunk transmission is detected independently with the same probability -- so the overall covertness probability factors as $(1-P_d)^{n+k}$, and if Willie can correlate checks with movements or learn which vertices hold data, that factorization and the derived tradeoff break down.

Editorial extensions

If this is right

  • Extra coded redundancy ($n>k$) can lower the expected end-to-end delay, because Bob's collection time falls as $s(H_n-H_{n-k})$; simulations in the paper show an optimal $n$ that balances Alice's longer dissemination against Bob's shorter collection.
  • Covertness decreases exponentially in the total number of chunk transmissions $n+k$, so every added coded chunk buys delay at a predictable cost in detection probability.
  • If Willie's monitoring window $W$ is shorter than the per-chunk transmission time $m/k$, each chunk is detected with probability 1; splitting the message into smaller chunks is therefore a precondition for covertness in that regime.
  • When Willie can observe agent movements, the delay-minimizing number of coded chunks is approximately $\sqrt{rk+k}-1$, giving a closed-form design rule rather than a simulation search.
  • The delay-covertness tradeoff is not monotone: for small $n$, increasing $k$ helps covertness; for large $n$, there is an optimal $k$ beyond which further splitting lowers covertness.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An optimization rule the paper leaves implicit: for a fixed covertness floor, choose the smallest $n+k$ that meets the delay target, since $P_c$ decays exponentially in $n+k$ while delay is non-monotone; the closed-form delay can be used to solve for that frontier directly.
  • The complete-graph formulas can be read as a fast-mixing approximation for any graph with short mixing time; on sparse or hub-based graphs the harmonic-number terms become hitting-time quantities, so the optimal redundancy would shift and the paper's curves are a best-case delay estimate.
  • Because the protocol only needs any $k$ of $n$ pieces to recover the message, rateless or fountain codes fit the same model; the covertness-delay formulas should apply without committing to a fixed code rate.
  • The warden-independence assumption is the main stress point: an adaptive Willie who learns which vertices never hold data would shrink the effective graph size, raise per-check detection probabilities, and break the product form $P_c=(1-P_d)^{n+k}$; the paper's own future-work section names this possibility.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. This paper introduces a stylized model of covert message passing on complete graphs. Alice walks randomly, deposits n coded chunks (derived from k message chunks) at the first n distinct relays she encounters, and Bob walks and collects any k chunks to recover the message. Willie patrols vertices; if he checks a vertex while a chunk transmission is taking place, the transmission is detected. The transmission time is modeled as shifted exponential with mean 1/λ + m/k, and Willie's check time for a transmission is taken to be uniform on [0,W]. The paper derives the per-transmission detection probability (Theorem 1), the covertness probability under a product-form assumption (Eq. (1)), and expected dissemination/collection/total delays for two warden models (Theorems 2 and 3), using coupon-collector arguments. Section VI reports simulations that match the theoretical delay expressions.

Significance. If the assumptions are made explicit and the technical errors are corrected, the paper provides a clean, closed-form illustration of a covertness-delay tradeoff in a mobile relay protocol: chunking and erasure redundancy can reduce delay but increase the number of transmission opportunities visible to Willie. The derivations are elementary but transparent; no parameters are fit to data, and the coupon-collector delay expressions in Model 1 (Lemmas 1–3) are correct as stated, with the reported simulation-theory agreement in Figures 2–4 as supporting evidence. The paper is honest about the simplicity of its warden models and explicitly defers adaptive wardens to future work. Its main value is as a baseline model for covert mobile message passing rather than as a new information-theoretic bound.

major comments (3)
  1. [Section II-C, Eq. (1)] The covertness probability Pc=(1-Pd)^(n+k) is obtained by multiplying per-transmission survival probabilities, but the paper never specifies a joint distribution for Willie's checks across the n+k transmissions. The model states only that 'when the transmission starts, the warden's (monitoring) time follows a uniform distribution U(0,W)'; it does not say that these checks are independent across transmissions. A single non-adaptive warden on a fixed periodic patrol with one random phase has marginal check times that can be uniform, yet the detection events for consecutive transmissions are dependent because the same patrol phase is shared, so the product form fails. As Eq. (1) is the sole support for the covertness axis of the claimed tradeoff, this missing independence assumption is load-bearing. The revision should either explicitly assume i.i.d. monitoring opportunities for each transmission and state that as part of the warden model, or derive a correlated-warden covertness probability or bound.
  2. [Section V-B, Lemmas 4–5 and Theorem 3] The prose states that in the second model 'every node visited by Alice or Bob takes 1 + m/k units of time,' but the delay expressions multiply the expected number of node visits by (1/λ + m/k + 1). The shifted-exponential transmission time has expected value 1/λ + m/k, so the prose omits the 1/λ term. If the intended model is that Alice and Bob transmit a dummy signal at every visited node with the same shifted-exponential duration, the prose should read 1 + 1/λ + m/k; if the intended model is a fixed dwell time of 1 + m/k at every node, then Lemmas 4–5 and Theorem 3 should use (1 + m/k) instead of (1/λ + m/k + 1). As written, the Model 2 expectation formulas do not correspond to the process described in the text.
  3. [Section V-B.3 (optimal n derivation)] The threshold for the optimal n does not follow from the displayed inequality. The derivation gives (n+1)^2 > k(r+1), so the correct condition is n > sqrt(k(r+1)) − 1, not n > sqrt(rk+k−1) as typeset. The stated formula is also inconsistent with the reported numerical optimum n=5 for r=10, k=3: sqrt(rk+k−1) is about 5.66, whereas sqrt(k(r+1)) − 1 is about 4.74. This algebra error occurs in the only closed-form optimization result in the paper and should be corrected together with the subsequent ceiling/floor prescription.
minor comments (5)
  1. [Section VI-A] The first sentence says 'the covertness probability increases with the redundancy n,' which contradicts Eq. (1), where (1-Pd)^(n+k) decreases in n for 0<Pd<1; the following discussion and Figure 1 correctly treat n=1 as the maximum-covertness case.
  2. [Section III-A and Lemma 1] The geometric-probability notation in Eq. (2) is mangled: it should read (1-p)^a p, and the sentence 'there aren stores' should read 'there are n stores.'
  3. [Section V-B.3] The definition of A_n omits the constant H_r that appears in Theorem 3's full expression; omitting it is harmless for optimization, but the text should say so to avoid confusion.
  4. [Section VI-B] No simulation details (number of independent runs, confidence intervals, or random-walk implementation) are provided, even though the close match between simulation and theory is a central part of the numerical validation.
  5. [General] The manuscript contains numerous typographical and grammatical errors (e.g., 'tradoofs', the broken sentence about n=2 or n=3 in Section VI-A, and several missing superscripts); a careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: the covertness and delay formulas follow directly from the stated stochastic model, with no fitted inputs or load-bearing self-citation.

full rationale

The paper derives its central quantities from explicitly stated model assumptions rather than from the quantities being predicted. Theorem 1 computes the single-transmission detection probability Pd from the shifted-exponential transmission time and the uniform warden arrival time U(0,W), and equation (1) multiplies (1-Pd) over n+k transmissions. This is a direct consequence of the paper's stated independence model for detection events, not a fitted parameter renamed as a prediction. The delay expressions in Lemmas 1-3 and Theorems 2-3 are obtained from coupon-collector expectations and linearity of expectation, and the simulations instantiate the same formulas rather than supplying a separate fitted input. The only self-citation, reference [9], is used as motivational analogy for coding reducing delay and is not load-bearing for the present derivation. The skeptical concern about unstated independence of Willie's patrols across transmissions is a modeling assumption gap and a correctness risk, but it is not circularity: an unstated or unrealistic assumption is not the same as a derivation that reduces to its own inputs by construction.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

All system parameters, including lambda, W, s, r, m, k, and n, are model inputs rather than fitted values, so the ledger contains no free parameters and no invented entities. The central formulas follow from the stated stochastic assumptions; the cost is that the model itself, rather than external data, determines the result.

assumptions (8)
  • domain assumption The communication graph is complete, and Alice and Bob walk randomly so that each step visits a uniformly random vertex; relays are fixed on r distinct vertices.
    Used throughout Section II-A and in all delay derivations; the coupon-collector calculations rely on uniform random visits.
  • domain assumption Each chunk transmission time is a shifted exponential with shift m/k and rate lambda.
    Stated in Section II-B and used in Theorem 1 and all delay lemmas.
  • domain assumption Willie's monitoring arrival time at a vertex is uniform on [0,W] when a transmission starts.
    Stated in Section II-C and used to derive the per-chunk detection probability in Theorem 1.
  • domain assumption If Willie checks a vertex during a chunk transmission, he detects it with probability 1; no physical-layer covertness is in place.
    Stated in Section II-C; this sets the detection probability used for covertness.
  • domain assumption Any k of the n encoded chunks are sufficient to recover the message.
    Assumed in Section II-A and used to define collection time as needing k chunks out of n.
  • domain assumption Detection events across the n+k chunk transmissions are independent and each has the same probability Pd.
    Used in equation (1) to write Pc=(1-Pd)^(n+k); not justified against correlated patrol schedules.
  • standard math The next unvisited relay is met with probability (r-i+1)/s, and any non-relay visit costs one time unit.
    This is the coupon-collector model stated in Section V-A and used in Lemmas 1 and 2.
  • domain assumption In Model 2, Alice and Bob spend equal time at every visited node so that Willie cannot infer which nodes hold data.
    Stated in Section V-B; however the paper inconsistently describes the per-node time as 1+m/k in prose and 1+1/lambda+m/k in Lemma 4.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Straggling for Covert Message Passing on Complete Graphs." pith.science (2026). https://pith.science/paper/KLH4LJB2

@misc{pith2026190805570,
  author       = {Pith},
  title        = {Pith review of: Straggling for Covert Message Passing on Complete Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KLH4LJB2}},
  note         = {Machine review of arXiv:1908.05570}
}
read the original abstract

We introduce a model for mobile, multi-agent information transfer that increases the communication covertness through a protocol which also increases the information transfer delay. Covertness is achieved in the presence of a warden who has the ability to patrol the communication channels. Furthermore we show how two forms of redundancy can be used as an effective tool to control the tradeoff between the covertness and the delay.

Figures

Figures reproduced from arXiv: 1908.05570 by the authors.

Figure 1
Figure 1. The covertness probability vs. k for 5 different values of n. The covertness probability increases rapidly with k when k is small. Then the benefits of increasing k get smaller and even negative. 10/k. The Willie’s arrival time follows uniform distribution U(0, 50) [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 3
Figure 3. The average time changes with redundancy [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. The average time changes with redundancy [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

  1. [1]

    B. A. Bash, D. Goeckel, D. Towsley, and S. Guha, ``Hiding information in noise: Fundamental limits of covert wireless communication,'' IEEE Communications Magazine, vol. 53, no. 12, pp. 26--31, 2015

    work page 2015

  2. [2]

    M. R. Bloch, ``Covert communication over noisy channels: A resolvability perspective,'' IEEE Transactions on Information Theory, vol. 62, no. 5, pp. 2334--2354, 2016

    work page 2016

  3. [3]

    Kadhe, S

    S. Kadhe, S. Jaggi, M. Bakshi, and A. Sprintson, ``Reliable, deniable, and hidable communication over multipath networks,'' in 2014 IEEE International Symp.\ on Inform.\ Theory. 1em plus 0.5em minus 0.4em IEEE, 2014, pp. 611--615

    work page 2014

  4. [4]

    A. R. Girard, A. S. Howell, and J. K. Hedrick, ``Border patrol and surveillance missions using multiple unmanned air vehicles,'' in 2004 43rd IEEE Conference on Decision and Control (CDC)(IEEE Cat. No. 04CH37601), vol. 1. 1em plus 0.5em minus 0.4em IEEE, 2004, pp. 620--625

    work page 2004

  5. [5]

    Puri, ``A survey of unmanned aerial vehicles (uav) for traffic surveillance,'' Department of computer science and engineering, University of South Florida, pp

    A. Puri, ``A survey of unmanned aerial vehicles (uav) for traffic surveillance,'' Department of computer science and engineering, University of South Florida, pp. 1--29, 2005

    work page 2005

  6. [6]

    D. A. Paley, F. Zhang, and N. E. Leonard, ``Cooperative control for ocean sampling: The glider coordinated control system,'' IEEE Transactions on Control Systems Technology, vol. 16, no. 4, pp. 735--744, 2008

    work page 2008

  7. [7]

    Villa, F

    T. Villa, F. Salimi, K. Morton, L. Morawska, and F. Gonzalez, ``Development and validation of a uav based system for air pollution measurements,'' Sensors, vol. 16, no. 12, p. 2202, 2016

    work page 2016

  8. [8]

    Tripathi, R

    V. Tripathi, R. Talak, and E. Modiano, ``Age optimal information gathering and dissemination on graphs,'' in 2019 IEEE Conference on Computer Communications, INFOCOM 2019, Paris, France, April 29 - May 2, 2019 , 2019, pp. 2422--2430

    work page 2019

Show all 11 references
  1. [9]

    Joshi, Y

    G. Joshi, Y. Liu, and E. Soljanin, ``Coding for fast content download,'' in Communication, Control, and Computing (Allerton), 2012 50th Annual Allerton Conference on. 1em plus 0.5em minus 0.4em IEEE, 2012, pp. 326--333

    2012

  2. [10]

    d " PQ ѕ 75iҦ& <sK&i;=\ y1_ IDDDDDDDD䵘 #

    11em plus .33em minus .07em @technote 4000 4000 100 4000 4000 500 `\.=1000 = #1 #1 #1 0pt [0pt][0pt] #1 * \| ** #1 \@IEEEauthorblockNstyle \@IEEEauthorblockAstyle \@IEEEauthordefaulttextstyle \@IEEEauthorblockconfadjspace -0.25em \@IEEEauthorblockNtopspace 0.0ex \@IEEEauthorbl...

    2012 arXiv

  3. [11]

    d " PQ ѕ 75iҦ& <sK&i;=\ y1_ IDDDDDDDD䵘 #

    11em plus .33em minus .07em @technote 4000 4000 100 4000 4000 500 `\.=1000 = #1 #1 #1 0pt [0pt][0pt] #1 * \| ** #1 \@IEEEauthorblockNstyle \@IEEEauthorblockAstyle \@IEEEauthordefaulttextstyle \@IEEEauthorblockconfadjspace -0.25em \@IEEEauthorblockNtopspace 0.0ex \@IEEEauthorbl...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.