PaperlayerView exact revision on arXiv

Source-linked AI summary

Amplified Pruning and Path Selectors for Deterministic Radio Gossiping

Qin Xin

arXiv:2610.28930v1cs.DScs.CCcs.DC

TL;DR

Wu and Chrobak’s questions about polynomial identifiers and nearly edge-linear gossiping are answered only in specified regimes. The paper combines reception certificates, adaptive pruning, and permutation selectors to obtain corresponding guarantees, while unrestricted general-graph cases remain open.

Abstract

from arXiv · show

We study deterministic gossiping in unknown strongly connected directed radio networks with $n$ vertices, $m$ arcs, and distinct identifiers in $\{1,\ldots,N\}$, where $N=n^{\mathcal O(1)}$. Messages are unrestricted; collision detection is unavailable. Our protocol combines amplified reception certificates, adaptive pruning, and permutation selectors. Each pruning iteration costs $\mathcal O(n\log^2n\log\log n)$ rounds. A two-step quadratic contraction limits each receiver and each class of identical closed in-neighborhoods to $\mathcal O(\log\log n)$ qualifying selections. Under an explicit degree-concentration condition, our protocol takes $\mathcal O(m\log^2n(\log\log n)^2)$ rounds. For directed regular graphs with common in- and out-degree $\Delta$, our strategy achieves $\widetilde{\mathcal O}(\min\{n\sqrt\Delta,n^2/\Delta\})$, extending the identifier range of Wu and Chrobak and improving their high-degree bound. At completion entry, let $a\ge1$ count original sources not yet credited as globally disseminated. Permutation selectors reduce our balanced completion budget by a factor of $\log^{2/3}(a+1)$ relative to interleaved path selectors. Our geometric protocol attains $\widetilde{\mathcal O}(k^2+n\tau+\min\{u^2,(nu)^{2/3}\})$ for an original path cover of scale $k$, weight $\tau$, and $u$ exceptions. Every graph also admits $\widetilde{\mathcal O}(\min\{n^{4/3},N+(mn)^{3/5}\})$ rounds. Only $n,N$ are inputs. Within the stated graph classes and identifier ranges, these results answer the polynomial-identifier and average-degree questions of Wu and Chrobak. The unrestricted general-graph cases remain open.

I. INTRODUCTION

The paper develops deterministic gossiping protocols for unknown directed radio networks with polynomial-size identifier ranges, where collisions and silence are indistinguishable. Its guarantees cover specified graph classes and conditions; the unrestricted general-graph extensions remain open.

B. Structural condition and results

  • At completion entry, permutation selectors reduce the balanced budget by a factor of log^(2/3)(a + 1) relative to interleaved path selectors.Here a counts sources not yet credited by designated completed broadcasts.Source: B. Structural condition and results · p. 2
  • For an original path cover with scale k, weight τ, and u exceptions, the geometric protocol attains e O(k^2 + nτ + min{u^2, (nu)^(2/3)}).The cover parameters are analytical witnesses, not protocol inputs.Source: B. Structural condition and results · p. 2

C. Open questions addressed by our approach

B. Structural condition and results

D. Relation to previous techniques

II. MODEL AND CONTROL

  • The model has n vertices, m arcs, distinct identifiers in [N], unknown topology, and no collision detection; only n and N are common inputs.Reception requires exactly one in-neighbor to transmit while the receiver listens.Source: §I · p. 1, §II · p. 3

A. Knowledge, ledgers, and namespaces

  • The common ledger F credits designated completed broadcasts, while active sources are those not yet credited; dormant vertices can still relay control and hold inventories.Inventories contain genuine source-tagged rumors, and F is a common record rather than a locally observed fact of global dissemination.Source: §II · p. 3, A. Knowledge, ledgers, and namespaces · p. 3

B. Selective schedules

Selective schedules isolate senders in finite, commonly chosen transmission patterns. The paper uses partial and weak selectors for different guarantees, then combines them with common control tests and amplified reception certificates.

B. Selective schedules

  • Selectors isolate an identifier by making it the sole transmitter from a contender set in some schedule row; strong selectors leave none unisolated.For k and r, the schedules leave at most r members of every set of size at most k unisolated.Source: B. Selective schedules · p. 4

1) Uniformity over small contender sets:

  • Padding a partial selector preserves isolation of contenders, but padding a weak selector can place its only successful sender outside the original set.The weak-selector construction instead concatenates partial selectors at dyadic scales to guarantee a genuine success.Source: 1) Uniformity over small contender sets · p. 4

C. Common tests and selection

  • Boolean OR tests and frozen-key searches provide common control decisions without relying on collision detection or changing flags during a test.The selection call can then broadcast the winning vertex’s frozen inventory and update the common ledger.Source: C. Common tests and selection · p. 4
  • DRAIN(q) ends at a common boundary with fewer than q uncredited sources in every frozen inventory, using at most R + B⌊a/q⌋ rounds.Each successful selection adds at least q new sources to F; the final empty call costs the initial R-round OR test.Source: C. Common tests and selection · p. 4

III. RECEPTION-CERTIFIED INTERFERENCE REDUCTION

  • O(κQ log N) rounds provide the amplified distinct-sender reception certificate for closed active contender sets of size at most κ.The count records immediate senders, not the number of original rumors carried in their packets.Source: §III · p. 5, C. Common tests and selection · p. 5
  • O(K[Q log N + r log^(3/2) N]) rounds provide a packet-union certificate for receivers with dA(v) + 1 ≤ K.The construction separates desired packets from final knowledge and uses weak selection on a small residual sender set.Source: §III · p. 5

A. Why final knowledge is the right separating set

Separating a missing packet from a receiver’s final knowledge lets the packet-union certificate avoid assuming that the full neighboring packet union is small. Adaptive pruning then uses the resulting reception guarantees to limit repeated successful selections.

A. Why final knowledge is the right separating set

  • When final knowledge is small, a packet-selector row separates a missing packet from that knowledge, silencing already-heard senders whose entry sets it contains.Weak selection can then isolate a remaining sender; if final knowledge is large, the certificate’s threshold alternative applies.Source: A. Why final knowledge is the right… · p. 5
  • The receiver’s own entry set lies in its final knowledge, so it is inactive in the separating row when it belongs to the active sender set.This is the point that makes the construction valid under half-duplex reception.Source: A. Why final knowledge is the right… · p. 5

B. Adaptive probing and pruning

  • PRUNE(D) makes at most ρD successful selections, costs O((1 + ρD)B) rounds, and returns with dA(v) < 2D for every receiver.The selection charge combines source-budget, receiver, and identical closed-neighborhood-class bounds.Source: B. Adaptive probing and pruning · pp. 6–7
  • Each receiver or identical closed-neighborhood class justifies only O(log log n) selections because adaptive accuracy yields a two-step quadratic contraction.The common contender cap decreases after a winning selection, allowing greater amplification at the same padded probe cost.Source: B. Adaptive probing and pruning · pp. 6–7

C. Why closed-neighborhood classes can share a charge

The section bounds pruning charges through two-step contraction and shared closed-neighborhood classes, then connects quasi-gossiping to exact replay for completion. It also compares degree-profile guarantees with an adaptive handoff that needs only common n and N.

C. Why closed-neighborhood classes can share a charge

  • Two-step contraction limits qualifying selections per receiver or identical closed-neighborhood class to O(log log n), while grouping replaces receiver multiplicity with distinct neighborhoods.The receiver's own rumor remains in its closed neighborhood even when half-duplex operation prevents self-reception.Source: C. Why closed-neighborhood classes can… · p. 7

IV. COMPLETION AND EXACT TEMPORAL REPLAY

  • Quasi-gossiping holds when each rumor is globally known or held by a vertex whose own original rumor is globally known.This holder condition supports completion by exact replay.Source: §IV · p. 7
  • After spreading along a path and collecting its endpoint's inventory, at least one target holder has its own rumor secured, establishing quasi-dissemination.The collection argument relies on overlap between target holders and the original sources represented at the endpoint, not just on counting holders.Source: §IV · pp. 7–8

A. Endpoint choices in completion

B. Temporal closure and complete recording

  • Complete recording preserves the temporal order needed for replay, since a vertex can disseminate its own rumor before receiving another rumor.During replay, the protocol reproduces recorded transmit/listen actions rather than recomputing selection predicates or stopping decisions.Source: B. Temporal closure and complete… · p. 8

V. PROFILE BOUND AND ADAPTATION

  • The degree-profile theorem gives a bound for every common threshold D, while the adaptive protocol compares pruning and completion without learning the degree profile.The adaptive protocol retains O(n^4/3) rounds generally and O((mn)^3/5) for linear identifiers, without knowing m.Source: §V · pp. 8–9

VI. PATH SELECTORS AND SURVIVING SOURCES

Completion can exploit the number of sources still outside the secured ledger through path selection, spreading and collection, or a balanced pruning-and-doubling branch. Permutation selectors support path delivery at a scale determined by the path's closed carrier neighborhood.

VI. PATH SELECTORS AND SURVIVING SOURCES

  • The completion-entry population can be handled by direct path selection, spreading followed by collection, or second pruning with path doubling.These branches trade off remaining sources, local interference, and selector scale.Source: §VI · pp. 9–10
  • A schedule delivers entry rumors to the endpoint of every carrier path whose closed carrier neighborhood has size at most k.Only the fixed carrier set sends data during the invocation.Source: §VI · p. 9
  • Spreading for q periods and collecting costs O(qσ + B(1 + a/(q + 1))).The collection secures a holder for rumors held at q + 1 active vertices along a source path.Source: §VI · p. 10
  • When k is at least a, direct selection costs O(a^2g); otherwise second pruning reduces contender sets before path selection and doubling.The second pruning stage has at most floor(a/h) successful broadcasts, each securing h distinct sources from the entry population.Source: §VI · p. 10
  • The balanced branch costs O(B + (Ba)^(2/3)g^(1/3)) by sharing selection charges across second pruning and later collections.Each successful selection secures sources from the same completion-entry population.Source: §VI · p. 10
  • The balanced branch uses only a, n, and N for its internal threshold, and its control operates over the physical graph without requiring connectivity of the active induced graph.Source: §VI · p. 10

A. Interpreting the completion menu

The completion menu compares complete procedures using the surviving-source population, and adaptive pruning stops when elapsed pruning time reaches its completion budget. Its bounds apply without a threshold search, using only common n and N.

A. Interpreting the completion menu

  • Suppressing logarithms, direct completion costs a^2 and the balanced branch costs (na)^(2/3); a ≤ √n permits nearly linear completion regardless of original degrees.The handoff population does not replace n in physical-network control costs.Source: A. Interpreting the completion menu · p. 10
  • Permutation selectors reduce the balanced budget by log^(2/3)(a + 1) relative to interleaved path selectors.This compares the two upper-budget constructions with the same control primitive; another branch or the additive B term can dominate total time.Source: A. Interpreting the completion menu · pp. 10–11
  • Pruning and later collections share a charge because their successful selections secure disjoint sources from the same completion-entry population.The accounting is not reset after a path-doubling iteration.Source: A. Interpreting the completion menu · p. 11
  • With a active sources and no residual-degree input bound, the third completion branch gives quasi-gossiping in O(B + E(a)), where E(a) = min{a^2Λ, J(a)}.The standalone bound is e O(n + min{a^2, (na)^(2/3)}).Source: A. Interpreting the completion menu · p. 11

VII. ADAPTIVE PRUNING AND PATH COMPLETION

  • Only common n and N are needed; total time is bounded by max_j max{jU, Cj} + 2U, with no threshold-search slowdown.The budgets Cj are nonincreasing along the reference trace.Source: §VII · p. 11
  • For comparator D, the adaptive profile specialization is O(U(1 + ρD) + C(aD, D)), using the active count at the first below-D search.The comparator and its active count are analytical parameters, not inputs.Source: §VII · p. 11

VIII. UNIFORM PATH COVERS AND PRUNING COMPOSITION

A geometric execution exploits path-cover witnesses without knowing the paths, weights, or exceptions, and pruning can supply a fixed residual carrier set. For an original path cover, its bound is e O(k^2 + nτ + min{u^2, (nu)^(2/3)}).

Geometric execution

  • The geometric construction fixes the carrier set so that inventory growth preserves witness paths, even as secured carriers remain available as relays.The affordable path scale and number of maximum-inventory selections grow together in doubling-budget phases.Source: §VIII · p. 12

Inventory selection

  • At most Γ(a − u, τ) maximum-inventory selections reduce a population of a unsecured sources to at most u when a > u.Integer gains sharpen the fractional contraction, including the final unit gains.Source: §VIII · p. 12

Uniform guarantee

  • One deterministic branch using only n and N simultaneously attains the uniform path-cover guarantee without a path-scale pool.The protocol uses geometric phases and a completion controller, then replays the full history to obtain full gossiping.Source: §VIII · pp. 12–13

Pruning composition

  • Pruning can feed the geometric construction by fixing its returned carrier set; full gossiping then costs twice the combined pruning and first-pass time.If pruning has already secured every source, it completes gossiping directly.Source: §VIII · p. 13

Uniform path-cover bound

  • e O(k^2 + nτ + min{u^2, (nu)^(2/3)}) rounds suffice for an original path cover of scale k, weight τ, and u exceptions.The witnesses are analytical, not protocol inputs.Source: §VIII · pp. 12, 14

Scope and conditions

  • At linear density, sufficient residual conditions are ρD + τ = e O(n^(1/5)), k = e O(n^(3/5)), and u = e O(n^(4/5)); a sparsity-only guarantee is not proved.A direct cover need not have small path scale, so the separate direct-reception branch remains useful.Source: §VIII · p. 14

IX. RECEPTION COVERS AND STRUCTURAL IMPROVEMENTS

Reception covers turn certified neighbor counts into progress on the remaining source population, with adaptive stopping comparing the execution against reference prefixes. This yields bounds for residual covers and structural cases such as minimum out-degree and near-universal receivers.

Residual-cover contraction

  • A residual reception cover of weight τ with u exceptions after j broadcasts gives e O(n(j + τ) + (nu)^(2/3)) rounds, simultaneously for such witnesses.Only n and N are inputs; covers and later reference prefixes are analytical witnesses.Source: §IX · p. 14

Successive residual covers

  • Successive residual covers compose along one unchanged execution, yielding e O(n Σ_{i<q} τ_i + (ns)^(2/3)) in soft notation.No stage, cover, or target is supplied to the protocol.Source: §IX · p. 14

Minimum and quantile out-degree

  • Minimum out-degree δ+ gives e O(n^2/δ+) rounds even when δ+ is unknown.More generally, the result uses an out-degree quantile and its number of exceptions.Source: §IX · pp. 14–15

Near-universal receiver

  • A receiver missing at most u incoming neighbors gives a structural bound, with neither its identity nor u required by the protocol.The supplied result states the bounds in Corollary 18, while the proof gives population contraction and completion branches.Source: §IX · p. 15

A. Why a cover gives a different amortization

Reception covers offer a different amortization from weighted degree-tail charging: they use a population-based score witness and can support fast pruning even with many large-degree receivers. The results extend to joint coverage and show that cover bounds apply beyond near-universal-receiver and degree-concentration settings.

A. Why a cover gives a different amortization

  • Reception-cover scores can yield fast pruning even when many receivers have large original degrees, unlike weighted degree-tail charging.The contraction remains valid if the winner is dormant, exceptions are already secured, or the maximum-scoring receiver changes between iterations.Source: A. Why a cover gives a different… · p. 15

B. Interpretation and scope of reception covers

  • The cover inequality counts arcs from each source to weighted receivers, so the corollary uses minimum out-degree; minimum in-degree alone is insufficient.Equality of minimum in- and out-degree is not required.Source: B. Interpretation and scope of… · p. 15
  • A cover criterion transfers the e O((mn)^3/5) density benchmark to polynomial identifiers when a reference prefix has a sufficiently small residual cover and exception count.For m = Θ(n), sufficient conditions are j + τ = e O(n^1/5) and u = e O(n^4/5).Source: B. Interpretation and scope of… · p. 16
  • A reception cover is an analytical witness, not a protocol input: the envelope bound compares one execution with every cover without searching exception sets.Its bound is e O(n(j + τ) + (nu)^2/3) for a cover of weight τ leaving u exceptions after j broadcasts.Source: B. Interpretation and scope of… · pp. 15–16
  • For every fixed h ≥ 2, sparse strongly connected graphs with linear diameter and no near-universal receiver admit polynomial-identifier gossiping in O(nL2ℓ2) rounds.Unit weights on h receivers cover all but at most h sources; the graph has Θ(n) arcs and an Ω(n) lower bound.Source: B. Interpretation and scope of… · p. 16
  • For s = ⌊n^1/2⌋ and u = ⌊n^7/10⌋, the two-parameter family gives e O(n^17/15) rounds, saving 14/75 against the density exponent 33/25.When s = u, the time is O(nL2ℓ2) with an Ω(n) lower bound; at s = u = ⌊n^7/10⌋, m = Θ(n^7/5) and the time exponent is one.Source: B. Interpretation and scope of… · p. 16

X. CONDENSING ON A FROZEN ACTIVE SET

Frozen-active-set condensing completes gossiping after freezing the data sender set while control still uses the physical graph. Aligned packet certificates, class-based collection, and an exact frontier schedule yield a finite phase budget without assuming that the active subgraph is connected.

A. Proof strategy and delivery requirements

B. Interpreting the path witness

The path-witness argument turns delayed delivery into forced collection: an unresolved target identifies a holder with too many packets from one owner class. Collection can establish quasi-dissemination even when the collected entry snapshot predates the target.

B. Interpreting the path witness

  • A bounded route delivers within the unpaid travel budget, so an unresolved target yields an overrepresented owner class whose persistent eligibility forces collection.At an unprocessed frontier, this threshold argument is unavailable and the appended exact schedule supplies prescribed delivery.Source: B. Interpreting the path witness · p. 20
  • An owner’s entry packet need not contain a later target; collecting it still disseminates the owner’s own rumor while the owner retains that target.That is sufficient for quasi-dissemination and subsequent exact replay.Source: B. Interpreting the path witness · p. 20

XI. PRUNED DENSITY TRANSFER

Pruned density transfer combines a pruning threshold, exact residual-frontier coverage, and frozen-set condensing, then removes unknown edge-budget and threshold inputs through verified trials. It yields a uniform bound using only n and N, while the density benchmark for polynomial identifiers still depends on graph density and identifier range.

XI. PRUNED DENSITY TRANSFER

  • For a threshold D, the pruned density-transfer bound combines pruning cost, exact residual coverage, and mixed-scale condensing cost.The theorem defines ED = min{N, D^2}, HD = n + mD, and PD = n(1 + ρD) + ED.Source: §XI · pp. 20–21
  • The e O((mn)^3/5) bound of [3] holds with polynomial identifiers when some threshold D satisfies the stated pruning and residual-edge budget conditions.For m = Θ(n), D = e O(n^3/5) with hD = e O(n^1/5) suffices, without restricting original maximum in-degree.Source: §XI · p. 21
  • Verified edge-budget trials and dyadic threshold branches remove m and D as inputs while preserving correct completion.Each trial starts from genuine initial rumors and accepts only a verified complete state; an underestimated guess cannot falsely certify all n source values.Source: §XI · p. 21
  • Every graph admits e O(min{n^4/3, N + (mn)^3/5}) rounds using only common n and N.The density benchmark is retained when the additive identifier penalty can be absorbed; for N = n^α+o(1) and m = n^c+o(1), the stated exponent comparison gives the supported range.Source: §XI · p. 21

A. Relation to the unpruned transfer

Pruning extends the transfer beyond bounded original degrees by charging qualifying receivers and classes rather than requiring every degree to be small. The resulting guarantees cover concentrated degree profiles, regular graphs, and sparse examples with large maximum in-degree, while unrestricted density extension remains open.

A. Relation to the unpruned transfer

  • The unpruned transfer is retained as a comparator, but the general density extension for every polynomial identifier range remains unproved.The theorem keeps the pruning-cost versus exact-residual-coverage tradeoff explicit and makes no impossibility claim about other selector or frontier methods.Source: A. Relation to the unpruned transfer · p. 21
  • Pruned-density transfer permits expensive original degrees when their weighted tail charge is small, rather than requiring all receivers to start with bounded degree.The construction with m = Θ(n) and a receiver of in-degree n−1 satisfies the sparse transfer theorem, although it violates the degree-concentration condition and the earlier maximum-degree condition.Source: A. Relation to the unpruned transfer · p. 21, B. A sparse family with linear maximum… · p. 22

B. A sparse family with linear maximum in-degree

  • The pruned-density theorem covers profiles beyond both the average-degree concentration condition and the original maximum-degree sufficient condition.In the grouped sparse family, the q high-degree centers violate (2) for sufficiently large q, while the distinguished receiver is universal and the cover analysis gives O(nL²ℓ²).Source: B. A sparse family with linear maximum… · p. 22

XII. STRUCTURAL CONSEQUENCES AND SCOPE

  • Under (2), common n,N suffice for O(mL²ℓ) rounds when N=O(nL²ℓ); polynomial identifiers give the refined O(mL²ℓ²)-round bound.Source: §XII · p. 22

A. Linear diameter and large maximum in-degree

  • A sparse family with m = Θ(n), linear diameter, and maximum in-degree Θ(n) satisfies degree concentration and realizes the exponent savings.The high-degree vertices are hubs; the construction has d ≥ (h+1)/2 and h ≤ 2d.Source: A. Linear diameter and large maximum… · p. 22

B. Regular graphs with polynomial identifiers

  • For common in- and out-degree Δ, gossiping takes Õ(min{n√Δ, n²/Δ}) rounds with polynomial identifiers, without knowing Δ.The bound extends Wu and Chrobak [3, Theorem 2]; the second branch improves the general exponent when Δ = n^γ+o(1) for γ > 2/3.Source: B. Regular graphs with polynomial… · pp. 22–23

C. Polynomial degree tails

Polynomial degree tails yield a portfolio of bounds whose best branch depends on the tail exponent. Localized tail assumptions allow arbitrary behavior below a threshold, with distinct threshold penalties for profile completion and sparse transfer.

C. Polynomial degree tails

A. Deriving the polynomial-tail portfolio

  • The pruned argument reaches the n^(6/5) guarantee through Δ ≤ e O(n^(3/5)) already at p = 4/3, paying for the number of high receivers rather than their largest individual degree.Source: A. Deriving the polynomial-tail… · p. 23
  • The flat 6/5 regime is a ceiling of the density construction, not a lower bound on gossiping.For p = 2, the profile exponent is 4/3 while density transfer gives 6/5; for p = 5, the profile exponent is 7/6 while density transfer gives 6/5.Source: A. Deriving the polynomial-tail… · p. 23

B. Localized tails

  • Localized tails permit arbitrary degree behavior below threshold k0, while keeping tail parameters as analytical comparators rather than protocol inputs.The adaptive theorem removes H, p, and k0 as inputs.Source: B. Localized tails · pp. 23–24
  • Localized profile completion pays linearly in k0, while exact residual coverage in sparse transfer pays quadratically, so their full bounds must be compared.The shared adaptive portfolio performs that comparison algorithmically; the sparse specialization assumes m = Θ(n).Source: B. Localized tails · p. 24

C. Residual-edge refinement

The residual-edge refinement makes the active-arc cost visible for a fixed pruning threshold, while preserving the full physical-network control cost. The paper also delineates what its certificates do not guarantee and identifies both sparse-class lower bounds and the remaining unrestricted extension problem.

C. Residual-edge refinement

  • For fixed D, the residual-edge-sensitive protocol uses an active-arc quantity μ_D that is not an input, and its bound refines the fixed-D bound because μ_D ≤ m.No node needs to compute μ_D; control still pays for the full n-vertex physical graph.Source: C. Residual-edge refinement · p. 24
  • Rounding an arbitrary threshold need not preserve μ_D within a constant factor, so the all-threshold adaptation instead uses a monotone original-profile bound.A higher threshold can enlarge the residual edge count by more than a constant factor, even with nested active sets.Source: C. Residual-edge refinement · p. 24

D. What the certificates do not imply

  • Count and all-or-threshold certificates do not by themselves guarantee receipt of every neighboring packet or a prescribed packet.Exact coverage is retained at an unprocessed frontier; the proposition does not rule out other protocols that force delivery by additional mechanisms.Source: D. What the certificates do not imply · p. 24

E. A linear-time exponent is unavoidable in the sparse class

  • Strongly connected graphs with m = Θ(n), satisfying (2) and having maximum in-degree n−1, can require Ω(n) rounds.The distance argument matches the linear polynomial exponent on this sparse family, without claiming matching logarithms or an Ω(m) bound at every density.Source: E. A linear-time exponent is… · pp. 24–25

F. The remaining unrestricted extension problem

  • The unrestricted density extension for every graph and polynomial identifier range remains open.The proof identifies frontier cost and pruning charge as targets; approximate neighbor counts alone do not justify the missing worst-case profile inequality.Source: F. The remaining unrestricted… · p. 25, §XIV · p. 25

XIV. CONCLUSION

  • The paper's conclusions are affirmative only within stated regimes: regular-graph identifier extension, specified density ranges, and degree-concentrated nearly edge-linear communication.The protocol requires only n and N; structural assumptions and residual witnesses are analytical, not implementation inputs.Source: §XIV · p. 25

APPENDIX A PROTOCOL REALIZATION AND DETAILED COST

The appendix specifies common decision boundaries, completion accounting, and replay needed to turn local reception guarantees into global dissemination. It also compares the resulting bounds across residual covers, exceptional populations, and out-degree quantiles.

A. A common state at every decision boundary

  • At each pruning boundary, vertices freeze activity, score distinct immediate senders, snapshot inventories, choose a common winner, and credit only its saved inventory.The common ledger makes a = n − |F| common, while freezing prevents search traffic from changing the credited set.Source: A. A common state at every decision… · p. 25

D. Stopping rules, residual witnesses, and complete replay

  • Complete replay repeats the first pass's recorded transmit/listen actions while retaining all knowledge, rather than recomputing scores, gates, or eligibility.The replay preserves the successful-reception opportunities used by the completion proof.Source: A. A common state at every decision… · pp. 25–26

B. Empty tests, shared charges, and threshold rounding

  • The balanced completion choice uses only a, n, and N, with cost O((Ba)^(2/3)g^(1/3)) for g = Λ log(a+1).For polynomial identifiers the budget is O((na)^(2/3)L²ℓ^(2/3)), refining this completion construction.Source: B. Empty tests, shared charges, and… · p. 26

C. Which round-robin obligations have been removed

E. Interpreting the new exponent guarantees

  • At linear density, the cover condition permits Õ(n^(4/5)) exceptional sources without requiring low degrees among them or the weighted receivers.For a two-receiver family, s = u yields O(nL²ℓ²) throughout m = Θ(n + u²), up to quadratic density.Source: E. Interpreting the new exponent… · p. 27

F. A nonregular family for the quantile bound

  • When u = d = ⌊n^(4/5)⌋, the out-degree-quantile bound gives Õ(n^(6/5)) even if minimum out-degree is one.The constructed strongly connected graph has Θ(n^(9/5)) arcs; the bound saves 2/15 against the general upper-bound exponent 4/3, with no matching lower bound asserted.Source: F. A nonregular family for the… · p. 27
Loading 2610.28930v1…