{"id":"02f92029-93d9-49c0-a912-bb6bb0f7eb86","arxiv_id":"1908.01894","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In the mobile telephone model, pairwise, broadcast, and all-to-all capacities are characterized to within constants, and one-shot gossip is solved within polylog factors in every graph.","lead":"This paper characterizes the maximum sustained throughput for three communication patterns in the mobile telephone model, a graph abstraction of smartphone peer-to-peer links, and gives algorithms that match these bounds up to constants. It also provides a one-shot gossip algorithm that is optimal or within log factors of optimal in every graph, closing much of an open problem in this model.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The one-shot gossip upper bound rests on an external to-appear MDST result ([9]); if that result fails, the polylog-optimal gossip claim is unsupported.","rationale":"The paper's internal proofs for the three capacity results are largely sound. I checked the separator arguments in Theorems 4.1 and 5.1: the per-round counting of at most |S| component-entry events is valid, and even allowing a constant number of concurrent connections per node would only change constants, not the Θ(1/d(G)) or Θ(1/(n d(G))) asymptotics. The random-network arguments in §3.2 and §4.3 are plausible; the concentration exponent error in Lemma 3.15 is a factor-of-6 slack issue fixable by enlarging β. Lemma 3.2 contains a false intermediate claim (v(f_i)≥1/K is not guaranteed for an approximate MCMF flow), but because OPT(τ)≥1/K and the approximate flow loses only ε, the final approximation factor survives after adjusting N by a constant. The one genuinely external dependency is [9] for the distributed MDST used in Theorem 5.5; this is the single load-bearing uncertainty. It does not affect the three main capacity characterizations, and the reader already conditioned on it, so I would leave the verdict at CONDITIONAL/UNCHANGED.","tokens_in":29067,"tokens_out":46896,"duration_ms":492420,"concrete_test":"Read the published PODC 2019 version of [9] and verify (a) it constructs a spanning tree with max degree O(d(G)+log n) in Õ(D+√n) rounds using O(log n)-bit messages, and (b) each round of that algorithm can be implemented in the MTM by one O(log n)-bit advertisement per node. If (a) or (b) fails, Theorem 5.5's upper bound should be weakened accordingly; if both hold, the gossip claim is supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 5.5's one-shot gossip upper bound, the paper's headline 'largely resolves an open question,' is the least secure claim. Its O((D+√n)polylog(n)+n(d(G)+log n)) bound depends on the to-appear PODC paper [9] for a distributed MDST with degree O(d(G)+log n) in Õ(D+√n) rounds in broadcast-CONGEST, and on the assertion (Section 4.2) that this algorithm runs directly in MTM using O(log n)-bit advertisements. Neither the degree/time theorem nor the MTM simulation is proved here. The three capacity theorems are not affected: their asymptotic upper bounds use the centralized MDST algorithm of [13], so any damage is localized to the one-shot gossip result. Secondary: Lemma 3.2's proof assumes v(f_i)≥1/K for the given multi-commodity flow, which may fail for near-optimal flows; the inequality is repairable by using the known OPT≥1/K lower bound and increasing N, so it does not threaten the pairwise capacity asymptotics.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies three throughput/capacity problems in the mobile telephone model (MTM). It gives a centralized (3/2+ε)-approximation for pairwise capacity via a reduction to concurrent multi-commodity flow and Shannon edge multicoloring, and proves tight Θ(r) bounds for Gupta-Kumar random graphs above the connectivity threshold. For broadcast capacity it proves an O(1/d(G)) upper bound using graph toughness and a matching Ω(1/d(G)) algorithm based on MDST construction and edge-coloring. For all-to-all capacity it proves Θ(1/(n d(G))) bounds. It also derives lower and upper bounds for one-shot gossip, claiming a polylog-optimal algorithm in every graph, with the upper bound relying on a distributed MDST algorithm from a to-appear paper.","tokens_in":29292,"tokens_out":24743,"duration_ms":244101,"significance":"If the main theorems hold, this is the first capacity treatment of the mobile telephone model and it coherently ties pairwise, broadcast, and all-to-all throughput to the MDST parameter d(G). The MCF-rounding-to-scheduling technique and the toughness-based lower bounds are novel and likely useful beyond this paper. The one-shot gossip corollary would largely resolve an open question from prior work. The main fragility is that the headline one-shot gossip upper bound depends on an external unpublished result, and several proof details need repair; none of the core capacity theorems appear fatally flawed.","major_comments":[{"comment":"The upper bound of the one-shot gossip result is not self-contained. It depends entirely on the distributed MDST algorithm of [9], cited as 'to appear', and on the assertion in §4.2 that this broadcast-CONGEST algorithm can be run directly in the MTM using O(log n)-bit advertisements. Neither the degree bound O(d(G)+log n), the round bound Õ(D+√n), nor the MTM simulation is proved in this manuscript. Since Theorem 5.5 is advertised as largely resolving an open question, this dependency is load-bearing; the authors should either include a proof or appendix of the required MDST result and its MTM implementation, or explicitly state that the result is conditional on [9].","section":"§5.4, Theorem 5.5"},{"comment":"The Chernoff bound contains an arithmetic error. From the stated lower bound r̂ ≥ r/6 and r ≥ β r_c, one obtains exp(-n r̂²/16) ≤ exp(-n(β r_c)²/576), not exp(-n(β r_c)²/96). The stronger bound would require r̂ ≥ r/√6, which is not guaranteed (e.g., r=0.5 gives r̂=0.2, which is less than 0.204). The lemma's high-probability conclusion is still recoverable by using the 576 bound and choosing β larger, but the proof as written is incorrect.","section":"§3.2.3, Lemma 3.15"},{"comment":"The assertion that 'the value of each flow is trivially bounded from below by v(f_i) ≥ 1/K' is false for an arbitrary feasible MCMF flow, since scaling a feasible flow down by any positive factor preserves feasibility and makes the value arbitrarily small. In the application to Theorem 3.1 the flow is near-optimal and OPT ≥ 1/K because sending 1/K of each commodity along a fixed path is feasible, so the argument is repairable by adding this hypothesis and adjusting N; however, the lemma as stated and proved is not correct.","section":"§3.1, Lemma 3.2"},{"comment":"The bound dr(v) ≤ 2N 'by node capacity constraints' is not justified. For a node that is an endpoint of a commodity and also carries pass-through flow, the sum of f(e) over incident original edges equals 2 f(v_in,v_out) - A(v) - B(v), which can be as large as 2 + ετ/4, so dr(v) can be up to (2+ε/2)N rather than 2N. The discrepancy can be absorbed into the existing ε-approximation, but the displayed derivation as written is incorrect.","section":"§3.1, proof of Theorem 3.1"}],"minor_comments":[{"comment":"The abstract says 'wireless network capacity has been active area of research'; it should be 'an active area of research'.","section":"§1, Abstract"},{"comment":"The proof text refers to 'a network generated by G(n,k)', which appears to be a typo; it should be 'G ∼ GK(n,r)'.","section":"§3.2.1, Theorem 3.6"},{"comment":"The caption says broadcast gossip 'terminates in at most αn simulated rounds, for a fixed constant α', but α is not defined in the figure or surrounding text; Theorem 5.2 gives D+n rounds, so the caption should say n+D or define α.","section":"§5.2, Figure 3 caption"},{"comment":"The proof of Theorem 4.4 is only a high-level paragraph; it should specify the failure probability of initialization and give a formal amortization argument that the pipeline fill and setup costs do not affect the asymptotic throughput.","section":"§4.2, Theorem 4.4"},{"comment":"The footnote in the proof assumes a model variation with one incoming and one outgoing link per round, whereas the main model in §2.1 allows at most one connection per node per round; since the theorem is stated for the official model, the factor-2 simulation should be incorporated explicitly into the proof or the model definition should be adjusted.","section":"§3.2.3, Lemma 3.16"}],"recommendation":"major_revision","confidential_remarks":"The central capacity theorems are supported by coherent proof strategies and appear repairable, but the headline one-shot gossip result rests on a to-appear paper by one of the authors and on an unsupported MTM simulation claim. In my view the editors should require the authors to either make that dependency explicit and conditional or provide the missing theorem and its MTM implementation. The other issues (Lemma 3.15 arithmetic, Lemma 3.2 statement, and the dr(v) bound) are local and fixable, so I do not see grounds for rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is the paper that finally gives capacity bounds for the mobile telephone model, and the core results look right to me. Pairwise capacity via rounding of MCF, broadcast capacity tied to MDST degree, and the matching all-to-all bound show real craft. Worth a serious referee.\n\nWhat is new: first ongoing-communication capacity results in MTM, a clean reduction of pairwise capacity to concurrent multicommodity flow with a 3/2+epsilon approximation, use of Win's toughness theorem for the O(1/d(G)) broadcast upper bound, matching algorithms via MDST edge coloring and CONGEST simulation, and random GK network analysis. The all-to-all bound and the one-shot gossip implication are the most interesting pieces.\n\nSoft spots, in order. (1) Lemma 3.15 has an arithmetic slip: from rhat >= r/6 you get denominator 576 in the exponent, not 96. The asymptotic claim survives because beta can absorb the constant, but as printed the inequality is wrong. (2) Lemma 3.2 as stated is false for arbitrary feasible flows: the proof assumes v(f_i) >= 1/K, which need not hold for a low-value flow. In the actual application f is near-optimal and OPT >= 1/K, so the step is repairable; the theorem is safe but the lemma needs rewording. (3) The one-shot gossip upper bound, Theorem 5.5, depends on Dinitz et al. [9], a to-appear PODC paper, for a distributed MDST with degree O(d(G)+log n) in O~(D+sqrt n) rounds. That result is not proved here, and the MTM simulation of it is asserted rather than demonstrated. If [9] fails, this specific claim is unsupported, though the rest of the paper only needs the centralized MDST of [13]. The capacity theorems are not affected. (4) The model's single-connection-per-round abstraction is motivated by Multipeer's limit of 8 concurrent connections, but the paper does not analyze whether the abstraction is faithful; I see this as an empirical caveat, not a mathematical flaw.\n\nOn citations: the reliance on [9] is by overlapping authors, but that is not itself a problem; the real issue is only the external dependency. The central tools from [13] and [35] are standard and well cited.\n\nBottom line: the core results are credible and mostly well proved; the flaws are localized and repairable. The paper deserves peer review. I would bring it to a reading group and would cite it.","headline":"The first real capacity characterizations for the mobile telephone model, with solid core proofs and two localized, repairable technical slips; the one-shot gossip claim rests on an external to-appear paper.","tokens_in":29793,"tokens_out":3944,"would_cite":true,"duration_ms":38753,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"In smartphone peer-to-peer networks, the maximum degree of a minimum-degree spanning tree fixes broadcast and all-to-all throughput, while pairwise capacity is approximable to within 3/2+ε.","keywords":["mobile telephone model","network capacity","pairwise capacity","broadcast capacity","all-to-all capacity","multi-commodity flow","minimum degree spanning tree","one-shot gossip"],"falsifier":"Run a sustained broadcast experiment on a star-like network with one central node and many leaves. The model's matching constraint caps throughput at 1/(n-1) packets per round; a schedule or real library that sustains c/(n-1) with c>1 concurrent connections per round would refute the single-connection premise on which the Θ(1/d(G)) lower bound rests.","tokens_in":28889,"feed_emoji":"📶","tokens_out":8030,"duration_ms":79007,"temperature":0.7,"pith_summary":"This paper establishes tight capacity bounds for three sustained-communication problems in the mobile telephone model, an abstraction of smartphone peer-to-peer links in which a node can hold at most one connection and transfer one packet per round. The central result is that the maximum degree d(G) of the graph's minimum-degree spanning tree fixes the broadcast throughput at Θ(1/d(G)) and the all-to-all throughput at Θ(1/(n d(G))). For pairwise flows, the paper shows that near-optimal throughput can be computed by reducing the scheduling problem to multi-commodity flow and rounding, achieving a (3/2+ε)-approximation of optimal in every connected graph. The same techniques give a one-shot gossip algorithm that is optimal or within a polylogarithmic factor of optimal in every graph, largely settling a previously open question. These bounds matter because they convert a question about smartphone mesh usefulness into a computable graph quantity that can be evaluated before deployment.","feed_headline":"One tree statistic sets smartphone peer-to-peer capacity","feed_subtitle":"Broadcast, all-to-all, and gossip throughput all hinge on the minimum-degree spanning tree's max degree.","key_machinery":"The load-bearing object is d(G), the minimum possible maximum degree of a spanning tree of the network graph. The paper combines a toughness-based separator lemma with the model's single-connection rule: a separator node that can reach several disconnected components can serve at most one component per round, so d(G) lower-bounds per-packet latency. To match the lower bound, the algorithms construct a low-degree spanning tree, edge-color it with O(d(G)) colors, and use the colors as a round-robin schedule to simulate the CONGEST model, turning standard pipelined flooding or broadcast gossip into a mobile-telephone schedule. For pairwise capacity the operative machinery is different: a reduction to maximum concurrent multi-commodity flow in a node-split digraph, a value-preserving rounding lemma, and edge multicoloring to convert fractional flows into a repeating matching schedule.","core_discovery":"In the mobile telephone model, where connections in a round form a matching and each edge transfers one packet, the paper proves that for any connected graph G the optimal sustainable broadcast throughput is Θ(1/d(G)), where d(G) is the smallest k such that G has a spanning tree of maximum degree k. The upper bound comes from a graph-theoretic separator lemma: if d(G)>k, some node set S splits G into more than (d(G)-2)|S| components, and since each separator node can feed only one component per round, every broadcast packet costs Ω(d(G)) rounds. A matching algorithm constructs a spanning tree of degree O(d(G)), edge-colors it with O(d(G)) colors, and cycles through colors to simulate the CONGEST model, in which pipelined flooding gives constant throughput. All-to-all capacity is then Θ(1/(n d(G))), because n sources each require a broadcast and the same separator argument bounds the total. For pairwise capacity the paper gives a polynomial-time centralized algorithm that routes packets within a (3/2+ε) factor of optimal, via a reduction to maximum concurrent multi-commodity flow followed by rounding and an edge-multicoloring schedule. In random geometric networks with radius above the connectivity threshold, the paper shows broadcast capacity is constant and all-to-all capacity is Θ(1/n), both optimal.","pith_inferences":["If real smartphone libraries allow a small constant c>1 concurrent connections per node, the broadcast and all-to-all bounds should scale by roughly c where separators dominate; the paper's model uses c=1 even though its motivating platform allows 8.","The degree parameter d(G) may be the right complexity measure for other one-shot primitives in this model, such as rumor spreading or token dissemination, whenever a single node must relay to many disconnected components.","The pairwise reduction could be used as an offline network planner: collect the topology, solve the multi-commodity flow, and distribute the repeating schedule, since the setup cost is amortized over an infinite run."],"forward_implications":["A network's broadcast usefulness can be read off a single tree statistic: graphs admitting a low-degree spanning tree sustain constant broadcast throughput, while graphs that force high-degree trees are proportionally slower.","Centralized planners can compute near-optimal pairwise schedules in polynomial time, so before deployment one can estimate whether an intended demand set is feasible.","All-to-all throughput in any connected topology is Θ(1/(n d(G))), so per-device sustained throughput cannot beat a 1/n scaling even on the most favorable graphs.","One-shot gossip can now be solved optimally or within a polylog factor in every graph, closing the gap left by expansion-based bounds for a large family of topologies.","In random geometric deployments just above the connectivity threshold, broadcast capacity reaches constant throughput, so the mobile telephone model is not inherently a bottleneck for one-to-many distribution."],"supporting_citations":[{"why":"Introduces the mobile telephone model and its single-connection-per-round rule, the paper's defining abstraction.","marker":"[17]"},{"why":"Supplies the pairwise capacity problem, the random geometric network generation process, and the capacity-analysis paradigm.","marker":"[22]"},{"why":"Establishes the toughness-to-spanning-tree theorem from which the separator lower bound on d(G) is derived.","marker":"[35]"},{"why":"Defines graph toughness, the resilience measure used to connect d(G) to component-count bounds.","marker":"[5]"},{"why":"Gives the centralized minimum-degree spanning tree approximation with degree d(G)+1 used by the broadcast algorithm.","marker":"[13]"},{"why":"Provides the distributed low-degree spanning tree construction that makes the broadcast and gossip algorithms distributed.","marker":"[9]"},{"why":"Supplies the edge-multicoloring theorem used to schedule fractional multi-commodity flows as repeating matchings.","marker":"[32]"},{"why":"Gives the near-optimal multi-commodity flow approximation algorithm inside the pairwise capacity reduction.","marker":"[27]"},{"why":"Supplies the randomized maximal matching subroutine used to edge-color the spanning tree in the distributed setting.","marker":"[24]"},{"why":"Poses the one-shot gossip open question and gives the prior expansion-based bounds that the new algorithm largely resolves.","marker":"[29]"}],"fun_headline_variants":["Tree statistic alone fixes smartphone peer-to-peer capacity","Broadcast and all-to-all rates follow from one tree invariant","Minimum-degree spanning tree governs phone network throughput","Peer-to-peer capacity: the tree's max degree rules"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The model assumes a node can take part in at most one connection per round, so a single bottleneck node can serve at most one disconnected component in a round; if real smartphone libraries allow several simultaneous connections, the broadcast and all-to-all bounds would loosen.","fun_headline_variants_meta":{"raw":{"variants":["Tree statistic alone fixes smartphone peer-to-peer capacity","Broadcast and all-to-all rates follow from one tree invariant","Minimum-degree spanning tree governs phone network throughput","Peer-to-peer capacity: the tree's max degree rules"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000762,"raw_usage":{"total_tokens":3456,"prompt_tokens":1091,"completion_tokens":2365,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":707,"completion_tokens_details":{"reasoning_tokens":2302}},"tokens_in":707,"tokens_out":2365,"duration_ms":18331,"temperature":1.0,"reasoning_tokens":2302,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:01:43.650843+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a sustained broadcast experiment on a star-like network with one central node and many leaves. The model's matching constraint caps throughput at 1/(n-1) packets per round; a schedule or real library that sustains c/(n-1) with c>1 concurrent connections per round would refute the single-connection premise on which the Θ(1/d(G)) lower bound rests.","supporting_citations":[{"cited_title":"How to discreetly spread a rumor in a crowd","cited_arxiv_id":null,"evidence_quote":"Introduces the mobile telephone model and its single-connection-per-round rule, the paper's defining abstraction."},{"cited_title":"The capacity of wireless networks","cited_arxiv_id":null,"evidence_quote":"Supplies the pairwise capacity problem, the random geometric network generation process, and the capacity-analysis paradigm."},{"cited_title":"On a connection between the existence of k-trees and the toughness of a graph","cited_arxiv_id":null,"evidence_quote":"Establishes the toughness-to-spanning-tree theorem from which the separator lower bound on d(G) is derived."},{"cited_title":"Tough graphs and hamiltonian circuits","cited_arxiv_id":null,"evidence_quote":"Defines graph toughness, the resilience measure used to connect d(G) to component-count bounds."},{"cited_title":"Approximating the minimum-degree Steiner tree to within one of optimal","cited_arxiv_id":null,"evidence_quote":"Gives the centralized minimum-degree spanning tree approximation with degree d(G)+1 used by the broadcast algorithm."},{"cited_title":"Halld\\' o rsson, Taisuke Izumi, and Calvin Newport","cited_arxiv_id":null,"evidence_quote":"Provides the distributed low-degree spanning tree construction that makes the broadcast and gossip algorithms distributed."},{"cited_title":"A theorem on coloring the lines of a network","cited_arxiv_id":null,"evidence_quote":"Supplies the edge-multicoloring theorem used to schedule fractional multi-commodity flows as repeating matchings."},{"cited_title":"Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms","cited_arxiv_id":null,"evidence_quote":"Gives the near-optimal multi-commodity flow approximation algorithm inside the pairwise capacity reduction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the randomized maximal matching subroutine used to edge-color the spanning tree in the distributed setting."},{"cited_title":"Leader election in a smartphone peer-to-peer network","cited_arxiv_id":null,"evidence_quote":"Poses the one-shot gossip open question and gives the prior expansion-based bounds that the new algorithm largely resolves."}],"review_version":1}