Locality Meets Interference: Structure and Scheduling in Radio Multicasting

Locality Meets Interference: Structure and Scheduling in Radio Multicasting Qin Xin

arXiv:2611.16844v1 [cs.DC] 12 Nov 2026

Faculty of Science and Technology University of the Faroe Islands, Tórshavn, Faroe Islands

Abstract We study multipoint-to-multipoint multicasting in synchronous radio networks with unknown participant locations and unrestricted message aggregation. Let n be the network size, k the number of participants, and d their hop diameter. A supplied distance-two coloring with C colors yields completion within (C − 1)d + 1 slots and at most nk transmissions. In unit disk graphs, coordinates, one-hop neighbor data, and a common degree bound ∆0 suffice for a 15(∆0 + 1)-color schedule. A known fixed separation bound permits optimal deterministic Θ(d) completion from coordinates alone. Without geometric data, strong selectivity gives O(d min{n, (∆0 + 1)2 log n}) slots when n is known. Independent random transmission gives O((∆0 + 1)(d + log(k/η))) slots with failure probability at most η; for fixed ∆0 , this simplifies to O(d + log(1/η)). A star construction shows that the logarithmic term is necessary for this random rule when the degree grows. We extend color schedules to fixed deletions and subgraphs connected over bounded windows of cycles. Separate conditional reductions preserve additive costs under diameter guessing and control parameter-table and cluster preprocessing. Finally, a counterexample shows that pruning and reranking a breadth-first tree can destroy interference-free delivery. For one-hop designated delivery with receiver degree at most b, we prove that the optimal schedule length equals the chromatic number of an associated conflict graph and is at most 2b − 1, with matching examples.

Keywords: Radio networks, Distributed algorithms, Multicasting, Message aggregation, Unit disk graphs, Selective families

1

Introduction

In multipoint-to-multipoint (M2M) multicasting, a set of k participants exchanges its initial messages through an n-vertex radio network. Vertices outside the set may relay messages. The maximum distance d between participants can be much smaller than the diameter D of the whole network, so a bound in terms of d captures the locality of the communication task. The protocol must meet two requirements: move information toward participants whose locations are not known in advance, and arrange transmissions that their intended receivers can decode. Unlimited aggregation removes packet queues while leaving both requirements in place. We therefore state the structural inputs of each scheduling result explicitly, distinguishing a supplied coloring, coordinates, a degree bound, and full topology. The destination set distinguishes several related tasks. Broadcasting delivers one source record to every vertex; gossiping delivers every vertex’s record to every vertex. In k-gathering, the records of k sources must reach a designated sink, whereas multi-broadcast delivers them to the whole network. M2M requires delivery only among the k participants. These distinctions matter when d ≪ D, and packet-size restrictions matter when many records share a route.

1

1.1

Broadcasting and structural advice

For known topology, Kowalski and Pelc [1] obtain deterministic broadcasting in O(D + log2 n) rounds. Without topology knowledge, De Marco [2] gives a deterministic O(n log n log log n) bound even without a supplied network-size bound. Czumaj and Davies [3] subsequently develop universal and block synchronizers, obtaining improved parameter-sensitive deterministic broadcasting and wake-up guarantees when n, maximum in-degree, and source eccentricity are available. These results distinguish arbitrary identifiers from information installed by topologyaware preprocessing. Randomization changes the dependence on network distance. Czumaj and Rytter [4] give broadcasting in O(D log(2n/D) + log2 n) rounds with high probability in unknown networks; for directed graphs, D here denotes source eccentricity. We write log(2n/D) to keep the logarithmic factor bounded below by one. Our degree-based random rule in Section 5 uses a fixed transmission probability and unrestricted aggregation. Its guarantee measures the time for that rule to exchange records among the participants. Gańczorz, Jurdziński and Pelc [5] give deterministic broadcasting in O(D + log2 n) rounds using constant-length labels, and gossiping in O(D +∆ log n+log2 n) rounds using O(log ∆)-bit labels. These fastest bounds use existential labeling schemes; their polynomial-time constructive variants replace the additive log2 n term by min{D, log n} log2 n. Their OPODIS 2025 paper was published in January 2026, following an October 2024 preprint. These results make the content and construction of advice essential comparison parameters. Our color protocol isolates what follows from one supplied distance-two coloring, with a bound in terms of d.

1.2

Gossiping, gathering, and multicasting

Known-topology gossiping has a substantial history [6–9]. In particular, Gąsieniec, Potapov and Xin [6] give an n-slot schedule and linear-diameter schedules for constant maximum degree. Section 3 retains an elementary serial fallback and explains how the published n-slot result can instead be used. For unknown strongly connected directed networks, the SWAT 2004 paper of Gąsieniec, Radzik and Xin [10] gives deterministic gossiping in O(n4/3 log4 n) rounds with polynomially bounded identifiers. This improves the earlier O(n5/3 log3 n) bound for polynomial identifiers and O(n3/2 log2 n) bounds for linear identifiers. Its use of selective families establishes the n4/3 benchmark against which later structural improvements are compared. Throughout this e suppresses polylogarithmic factors. review, O Wu and Chrobak [11] study sparse unknown directed networks. Their 2026 preprint reports √ 3/5 e e O((mn) ) gossiping rounds for m arcs and O(n ∆) rounds for ∆-regular graphs. The first e 4/3 ) benchmark when m = O(nc ) for fixed c < 11/9. These results bound improves the O(n concern all-to-all communication, with k = n, and complement our undirected participantlocal setting. A numerical comparison alone would omit the different graph and information assumptions. Xin [12] studies the same unknown directed setting with polynomial identifiers, unrestricted messages, and no collision detection. Amplified reception certificates, adaptive pruning, and permutation selectors yield bounds sensitive to degree concentration and path covers. For √ e common in- and out-degree ∆, the reported bound is O(min{n ∆, n2 /∆}); only n and the identifier bound N are protocol inputs. This structural approach complements the locality parameter d studied here: its task disseminates all n records globally, whereas M2M requires exchange only among the participants. With message-sized packets, multi-message communication must also account for congestion. Ghaffari and Haeupler [13] construct collision-free layerings in 

Tlay = O D log(2n/D) + log2+ε n 2



rounds for every fixed ε > 0. They obtain gathering of k messages in O(Tlay + k) rounds, single-source k-message broadcasting in O(Tlay + k log n) rounds, and gossiping in O(n log n) rounds, with high probability. Their packets carry one message-sized payload, with headers and coding where needed. This packet model differs from transporting an arbitrary collection of complete records in one slot, as permitted here. Gańczorz and Jurdziński [14], in SOFSEM 2026 with a December 2025 preprint, give kgathering in at most D+k rounds and multi-message k-broadcasting in O(D+k+log2 n) rounds, using O(min{log k, log ∆})-bit advice. Their model permits nodes to wake only upon receiving a message. Comparison with M2M must account for oracle-assigned labels, the destination set, and the distinction between D and d. An application inside Section 7 would additionally require the stated clusters and valid local advice. Krisko and Miller [15] characterize the advice needed for deterministic multi-broadcast. For k, ∆ ≥ 2, the tight worst-case label length is Θ(min{log k, log ∆}) bits; they also characterize optimal gossiping labels for individual trees through the distinguishing number. Their 2026 journal article develops work first available in 2021. Its emphasis is feasibility and label length, rather than participant-local completion under a prescribed coloring. Locality-sensitive M2M was studied by Gąsieniec, Kranakis, Pelc and Xin [16] and by Xin, Manne, Zhang and Wang [17]. Chlebus, Kowalski and Radzik [18] distinguish many-tomany communication models by topology and participant information. The unit-disk O(d + k) bound of [17] uses known topology and participant parameters. Our coordinate-based bounds use different structural inputs. Their comparison therefore concerns both online slots and the information available before communication.

1.3

Local broadcast, selectors, and energy

Strongly selective families are established tools for isolating designated transmitters [19]. Kuschner, Shashwat, Yadav and Chrobak [20] strengthen this perspective with permutation selectors: a probabilistic construction gives size O(r2 log N ) while realizing every order on every r-element subset of an N -element identifier universe. Their ALGOWIN 2024 paper appears in a volume dated 2025; the preprint and online proceedings were available in 2024. The order property improves multi-hop gossiping schedules. Section 5 needs only ordinary strong selectivity, so its existence bound is presented as a self-contained application of an established tool. Garncarek, Jurdzinski, Kowalski, Kutten and Mosteiro [21] study deterministic all-neighbor local broadcast in ISAAC 2025. Let γ2 be the minimum, over dominating sets, of their max2 e imum intersection size with a radius-two ball. They give O(∆γ 2 )-round algorithms trading advice length against adaptivity, and a lower bound (

Ω min

min{∆, γ2 } log n

2

)!

,n

for advice-free quasi-adaptive algorithms. This class permits local stopping of otherwise fixed transmission schedules. The distinction from Section 8 is substantive: our designated-delivery schedule is constructed from known incidence data and has one required receiver per sender. The cited lower bound is for a different input and delivery requirement. Energy is a separate objective from slot count or total transmissions. Banasik et al. [22], in DISC 2025, give a randomized maximal independent set algorithm without collision detection using O(log2 n log log n) awake rounds per vertex and O(log3 n log ∆) rounds overall, with high probability. This result concerns the distributed construction of a coordination structure, illustrating why the cost of obtaining structural inputs should be accounted for separately from a protocol that receives them as advice.

3

Table 1: Completion bounds and their information requirements. Here ∆0 ≥ ∆ is a common known degree bound, 0 < η < 1, and Cϵ is given by (1). The final row is a conditional reduction. Available information or structure

Completion bound

Additional guarantee

Coloring of G2 with C colors Known topology Unit disk coordinates and one-hop neighbor data Separated unit disk graph; coordinates and known ϵ Known n, identifiers, and degree bound Degree bound; independent random coins Subgraphs of a fixed colored graph; union connected over W cycles Timed protocol with budget Aδ + B

(C − 1)d + 1 ∆2 d + 1 15(∆0 + 1)d

At most nk transmissions Polynomial preprocessing Local computation of colors

Cϵ d

Deterministically optimal for fixed ϵ Polynomial construction for fixed ∆0 Success probability at least 1−η All records reach all vertices

O(d min{n, (∆0 + 1)2 log n}) O((∆0 + 1)(d + log(k/η))) CW (n − 1)

5Ad + 2B for unknown d

Known A, B, cap D0 ≥ d; resettable trials

Chang and Guan [23], in SPAA 2026, give randomized aggregation without collision detection using O(log n)-bit messages. With high probability, construction and execution take O(n polylog n) rounds and O(∆∗ polylog n) energy, where ∆∗ is the minimum possible maximum degree of a spanning tree. Their task computes a compact function of the inputs. Energy counts both sending and listening at the most active vertex; our nk transmission bound concerns sending activity and does not bound listening energy.

1.4

Contributions and organization

Our first set of results isolates a common forwarding invariant. A distance-two coloring guarantees all-neighbor reception whenever a vertex transmits; forwarding an aggregate only after it changes then gives a locality-sensitive completion bound and at most nk transmissions. We give two geometric ways to supply such a coloring. One-hop neighbor data permit a palette linear in a known degree bound, whereas a fixed separation bound permits a constant palette from coordinates alone. We then replace the coloring by either a strongly selective identifier schedule or independent random transmissions. The latter analysis tracks records along paths without assuming independent hop-progress indicators. The remaining results identify which parts of this reasoning survive composition or structural changes. Color schedules tolerate deletions and connectivity over bounded windows of cycles, provided edges remain fixed within each cycle and unchanged records are retransmitted. For protocols that instead require parameter bounds, we give conditional reductions for diameter guessing, parameter-table discretization, and cluster composition. These reductions take their base protocols and structural inputs as premises; they do not establish the existence of cluster covers with arbitrary desired parameters. Finally, we examine interference directly. A pruning counterexample separates tree-rank bounds from valid radio schedules, while a conflictgraph characterization yields a tight 2b − 1 bound for one-hop designated delivery with receiver degree at most b. Table 1 summarizes the main completion guarantees and their inputs. Sections 3–5 concern static networks; Section 6 treats changing subgraphs. Section 7 gives the conditional reductions, and Section 8 studies the interference constraints needed by local gathering schedules. Throughout, completion and termination are distinguished explicitly. 4

2

Model and definitions

Let G = (V, E) be a finite simple connected undirected graph with n = |V | ≥ 2, maximum degree ∆, and diameter D. Write N (v) for the neighbors of v and N [v] = N (v) ∪ {v}. Vertices have distinct identifiers in [n] = {1, . . . , n}. The participant set S ⊆ V has k ≥ 2 members. Each s ∈ S initially holds (s, ms ), where ms is an arbitrary finite string known only to s. Nonparticipants initially hold no record. Set d = max distG (s, t), s,t∈S

1 ≤ d ≤ D.

Logarithms are base two unless written ln. In asymptotic complexity bounds, logarithmic factors are truncated below at one; logarithms in exact identities and inequalities have their ordinary values. A degree bound ∆0 , whenever used, is a common known integer satisfying ∆0 ≥ ∆. At the start of each synchronous slot, a vertex chooses its action and packet from its state and any fresh random coins. It either transmits or listens. A listener receives a packet at the slot’s end exactly when one neighbor transmits; transmitters receive nothing, and silence is indistinguishable from collision. All vertices start together and share slot numbering. Packets may contain any finite collection of records and control information. An aggregate of all k records costs one slot; with b-bit payloads, its explicit representation uses O(k(b + log n)) bits. Local computation, preprocessing, and schedule installation are separate from online slot costs. Preprocessing uses only the structural information and parameters explicitly supplied in each theorem, with no additional participant-set or payload information. Completion occurs when every participant holds all k records; global termination also requires every vertex to halt. If k is known, a participant recognizes completion by counting distinct source identifiers but continues the prescribed forwarding. Vertices remain active after local completion unless a stopping rule is given. Records are only copied and combined, singleton receptions are reliable, and no protocol uses collision detection. The square G2 connects distinct vertices at distance at most two in G. A proper coloring c : V → [C] of G2 is a distance-two coloring. The online color protocol uses only c(v), C, the common clock, and the local initial record; known-topology preprocessing can compute and install these values. A unit disk graph has an embedding p : V → R2 in which distinct u, v are adjacent exactly when ∥p(u) − p(v)∥ ≤ 1. A separated unit disk graph additionally satisfies ∥p(u) − p(v)∥ ≥ ϵ > 0 for all distinct vertices. Fixed separation means that ϵ is independent of n. Geometric algorithms use exact coordinates in a shared frame, with exact arithmetic and floor operations for cell indices. Coordinates, neighbor data, and colors are inputs when specified in a theorem. All graph diameters are measured in hops.

3

Color cycles and transmission bounds

We first assume that a distance-two coloring has been supplied. This isolates the forwarding argument from the way the schedule is constructed. Section 4 supplies geometric colorings, while Section 5 replaces coloring by identifier-based or random schedules. A cycle consists of C slots, numbered 1, . . . , C. Vertex v can transmit only in slot c(v). It stores its accumulated set Kv of records and the set Lv sent in its last transmission. Initially Kv = {(v, mv )} for v ∈ S and Kv = ∅ otherwise; every Lv is empty. In its color slot, v transmits Kv if Kv ̸= Lv and then sets Lv := Kv . Otherwise it listens. It also listens in every other slot. A received packet is combined with Kv by taking their union. The accumulated sets never lose records. The assignment to Lv stores a snapshot: later updates of Kv do not change Lv . Consequently Lv ⊆ Kv throughout the execution. 5

Lemma 3.1. Every transmission of the color-cycle protocol is received by all neighbors of its sender. Proof. Adjacent vertices have different colors, so every neighbor of a transmitter listens in that slot. Two neighbors of the same listener are at distance at most two and therefore have different colors. Hence a listener has at most one transmitting neighbor in the slot. Suppressing a transmission cannot violate either property. Theorem 3.2. Given a distance-two coloring with C colors, the color-cycle protocol completes M2M within (C −1)d+1 ≤ Cd slots. Over its entire execution it uses at most nk transmissions. During its first r cycles, for every integer r ≥ 0, it uses at most n min{r, k} transmissions. Neither d nor k is required by the forwarding rule. For every C ≥ 3 and d ≥ C − 1, the slot bound is attained by this protocol on a path using all C colors and with two participating endpoints. Proof. Progress by cycles. Fix a source s. We prove by induction on r that after r cycles every vertex at distance at most r from s knows its record. The assertion is immediate for r = 0. Suppose it holds for r − 1, and let uv be the last edge of a shortest path from s to a vertex v at distance r. At the start of cycle r, vertex u knows the record. If u has transmitted it before, then v already received it by Lemma 3.1. Otherwise the record belongs to Ku \ Lu , so u transmits it in its color slot during cycle r. The same lemma ensures that v receives it. Applying the induction to every ordered pair of participants proves completion within d cycles. Slot bound. Fix a source-to-target path v0 , . . . , vℓ , where 1 ≤ ℓ ≤ d. Let ti be the first slot in which vi transmits the source record, for 0 ≤ i < ℓ. The source sends by its first color slot, so t0 ≤ C. Suppose ti−1 is defined. By Lemma 3.1, vi has the record at the end of that slot. If it sent the record earlier, then ti ≤ ti−1 . Otherwise the record is absent from Lvi , so vi sends it in its next color slot. Adjacent colors differ, and hence that slot occurs at most C − 1 slots later. Inductively, all these times exist and satisfy ti ≤ ti−1 + C − 1

(1 ≤ i < ℓ).

The target receives the record by slot tℓ−1 ≤ C + (ℓ − 1)(C − 1) ≤ (C − 1)d + 1. This proves the sharper bound, including the case ℓ = 1. Tightness. Take the path v0 , . . . , vd , make its endpoints the only participants, and assign c(vi ) = 1 + ((C − 1 − i) mod C). For C ≥ 3, vertices at distance one or two have different colors, so this is a valid distancetwo coloring with palette [C]; all C colors occur when d ≥ C − 1. The record of v0 can reach vd only along the path. Its first transmission occurs in slot C, and at every subsequent relay the next color slot is exactly C − 1 slots later. Thus vd first receives that record in slot C + (d − 1)(C − 1) = (C − 1)d + 1. The upper bound already proved makes this the exact completion time of the instance. This is a tightness statement for the supplied-color protocol, not a lower bound for arbitrary radio algorithms. Transmission count. Since Lv ⊆ Kv , every transmission by a vertex contains a record absent from its previous transmission. The corresponding sets Lv form a strictly increasing sequence of subsets of the k source records. Consequently each vertex transmits at most k times. It also transmits at most once per cycle. Summing the two bounds over the vertices proves the transmission statements. The forwarding rule uses no participant count. Knowledge of k supplies a stopping certificate: after forwarding all k records, a vertex can safely halt.

6

Corollary 3.3. If all vertices know k, each can halt permanently after first transmitting the complete set of records. Let Thalt,S and Thalt,V be the times by which all participants and all vertices, respectively, have halted. Then Thalt,S ≤ (C − 1)(d + 1) + 1,

Thalt,V ≤ (C − 1)(D + 1) + 1.

In particular, the corresponding cycle bounds are d + 1 and D + 1. Neither diameter is required by the stopping rule. Both slot bounds are attained by the path family in Theorem 3.2. Proof. When a vertex sends its final complete aggregate, each neighbor either has already halted with all records or is still active and listens in that slot. Every active neighbor receives the aggregate by the coloring property. Hence, whenever a vertex halts, all its neighbors know all records. A halted relay therefore cannot obstruct a record that its successor still lacks: it has already transmitted that record to the successor. The first-transmission argument in Theorem 3.2 continues to apply, giving completion by slot (C − 1)d + 1 at every participant and by slot (C − 1)D + 1 at every vertex. Because k ≥ 2, no vertex initially holds all records. Each vertex first completes its set at the end of a reception slot, which differs from its own color slot. Its last-sent snapshot is still incomplete, so its next color opportunity produces a transmission of the complete set. That opportunity occurs within C − 1 slots, after which the vertex halts. Adding this delay gives both slot bounds. Since (C − 1)(h + 1) + 1 ≤ C(h + 1) for h ≥ 1, the cycle bounds follow as well. For tightness, use the path and coloring from Theorem 3.2. The endpoint vd first receives the other participant’s record in slot (C − 1)d + 1. Its next color slot is exactly C − 1 slots later, when it first sends the complete set and halts. Here D = d, so both bounds are attained. We next translate the color bound into a known-topology guarantee. Its lower bound is the causal cost of moving a source record across d edges. Corollary 3.4. Known-topology M2M admits polynomial preprocessing and completion within ∆2 d + 1 slots. For fixed maximum degree, the deterministic completion complexity is Θ(d) in the worst case over input records. Proof. A vertex has at most ∆ + ∆(∆ − 1) = ∆2 neighbors in G2 . Greedy coloring therefore uses at most ∆2 +1 colors. The square graph and the coloring can be constructed in polynomial time, and Theorem 3.2 applies. For the lower bound, fix the graph, participants, and payload-independent preprocessing. Choose s, t ∈ S at distance d. Induction on slots shows that after j slots, the state of t depends only on initial states within distance j: a state transition uses only the vertex’s state and its neighbors’ transmissions. Changing only ms therefore leaves the state of t unchanged through slot d−1. Correct outputs must distinguish these payloads, so completion cannot be guaranteed before slot d. The next proposition identifies the palette cost of guaranteeing reception at every neighbor in each assigned slot. Proposition 3.5. A distance-two coloring of a graph of maximum degree ∆ requires at least ∆ + 1 colors. More generally, if every vertex is assigned one slot in a repeated schedule and every scheduled transmission must be received by every neighbor when all vertices transmit in their assigned slots, then the slot assignment is a proper coloring of G2 . Proof. The closed neighborhood of a maximum-degree vertex is a clique of size ∆ + 1 in G2 . For the second assertion, adjacent vertices cannot share a slot because a transmitter does not listen. Vertices with a common neighbor cannot share a slot because their packets collide there. These are exactly the pairs joined in G2 . 7

When the degree is large, a network-size bound can be preferable to a color-based bound. A serial tree schedule supplies a fallback, and interleaving combines any two available protocols. Proposition 3.6. Known-topology M2M can be completed within 2(n − 1) slots. If the inputs required by two correct protocols are available, they can be interleaved to obtain twice the smaller of their completion times. Proof. Choose a rooted spanning tree. In a postorder of its nonroot vertices, let each vertex transmit its accumulated records once, using a separate slot for each transmission. Every child transmits before its parent, so the root obtains all records after n − 1 slots. Then visit the nonleaf vertices in preorder, letting each transmit the complete aggregate in a separate slot. There are at most n − 1 such vertices, and every child receives the complete aggregate before it needs to forward it. Only one vertex transmits in any slot, so other graph edges cause no collisions. For interleaving, give the first protocol odd slots and the second even slots. Maintain separate states, original input copies, and a logical slot counter for each protocol. Each component controls only its allocated slots; halting one component leaves the other simulation active. Each execution therefore sees an exact simulation at half speed. Retain delivered records in an output buffer that does not alter either simulation. This proves the claimed minimum bound. The elementary serial bound above is useful without further scheduling machinery, but is not the best known global fallback. The n-slot gossiping theorem of [6] also solves M2M: every vertex supplies a logical token, participants attach their genuine records, and other tokens are control placeholders discarded from the output. With that theorem available, interleaving yields completion within 2 min{n, (C − 1)d + 1} slots.

4

Geometric schedules

The generic square coloring uses ∆2 + 1 colors. Geometry permits a smaller palette by placing nearby vertices in cells and separating cells that reuse a color. We first allow multiple vertices in a cell and distinguish them by local identifier order; minimum separation will then remove that local-information requirement. Theorem 4.1. In a unit disk graph with a known common degree bound ∆0 , a vertex’s coordinates and its one-hop neighbors’ identifiers and coordinates suffice to compute a distance-two coloring with 15(∆0 + 1) colors. The resulting M2M completion bound is 15(∆0 + 1)d slots. √ Proof. Partition the plane into half-open square cells of side s = 1/ 2. Index the cells by (i, j) ∈ Z2 , with cell (i, j) equal to [is, (i + 1)s) × [js, (j + 1)s). Two points in a cell are at distance strictly less than one. Thus the vertices in each cell form a clique and number at most ∆0 + 1. Each vertex computes its position a in the identifier order of its cell. Every other vertex in that cell is a one-hop neighbor, so the given local information suffices. Assign the cell residue ρ(i, j) = (i − 4j) mod 15 ∈ {0, . . . , 14}, and give the vertex numerical color c(v) = (∆0 + 1)ρ(i, j) + a. Equal numerical colors have equal residues and equal within-cell ranks. Vertices in the same cell therefore have distinct colors. Consider two distinct cells with the same residue, and write (u, v) for the difference of their indices. If |u| ≥ 4 or |v| ≥ 4, the corresponding coordinate gap between any two points in the cells is greater than 3s > 2. Otherwise |u|, |v| ≤ 3 and u − 4v ≡ 0 (mod 15). Since 8

|u − 4v| ≤ 15, we have u − 4v ∈ {−15, 0, 15}. Applying the coordinate bounds to these three equations gives exactly (u, v) = (0, 0), (3, −3), (−3, 3). The first is excluded because the cells differ. In either remaining case, both coordinate gaps are strictly greater p than 2s, using the half-open cell convention. The Euclidean distance is then greater than (2s)2 + (2s)2 = 2. Thus equal-colored distinct vertices are more than two Euclidean units apart and cannot be joined by two unit-length edges. The coloring is proper for G2 and uses at most 15(∆0 + 1) colors. The common degree bound fixes the palette and slot order. Theorem 3.2 gives the claimed completion time and, more precisely, [15(∆0 + 1) − 1]d + 1 slots. For ∆0 = ∆, Proposition 3.5 shows that this palette size is within a factor of fifteen of the smallest possible distance-two palette. This comparison concerns the number of colors, rather than a lower bound on arbitrary M2M protocols. With full topology one may choose the smaller of the geometric and greedy palettes. Theorem 4.2. In a separated unit disk graph, coordinates and a common known separation bound ϵ suffice to assign a distance-two coloring with l √ m 2 Cϵ = 2 2/ϵ + 1 (1) colors. No neighbor information is required. Completion takes at most Cϵ d slots, and for fixed ϵ the worst-case deterministic completion complexity is Θ(d). √ Proof. Use half-open square cells of side s = ϵ/ 2. A cell contains at most one vertex, because the distance between two points in it is strictly less than ϵ. Let M = ⌈2/s⌉ + 1, and assign color 1 + M (i mod M ) + (j mod M ) to the vertex in cell (i, j), with residues in {0, . . . , M − 1}. For distinct cells of one color, at least one cell index differs by a nonzero multiple of M . In that coordinate, every pair of points has a gap strictly greater than (M − 1)s ≥ 2. The strict inequality follows from the half-open upper cell boundary and also covers the case where 2/s is an integer. Equal-colored vertices cannot be joined by a path of at most two edges. The number of colors is M 2 = Cϵ . The upper bound follows from Theorem 3.2. The causal lower-bound argument in Corollary 3.4 still applies when coordinates and a separation bound are supplied, since these inputs contain no source payload. It gives the matching Ω(d) lower bound. For example, ϵ = 1/2 gives M = 7 and Cϵ = 49. Separation also supplies a direct degree bound, independently of the grid construction. Lemma 4.3. For every vertex v in a separated unit disk graph and every integer h ≥ 0, the number of vertices within h graph hops of v is at most (1 + 2h/ϵ)2 . In particular, ∆ + 1 ≤ (1 + 2/ϵ)2 . Proof. Vertices within h hops of v lie within Euclidean distance h of p(v). Place an open disk of radius ϵ/2 at each such vertex. The disks have disjoint interiors by separation and lie in the disk of radius h + ϵ/2 centered at p(v). Comparing areas gives the result. For h = 1, choose a maximum-degree vertex. Because a connected unit disk graph with at least two vertices has ϵ ≤ 1, equation (1) also gives Cϵ = O(ϵ−2 ). The online color rule remains the same as in Section 3, so all geometric bounds retain the nk transmission guarantee.

5

Protocols for unknown topology

When a distance-two coloring and geometric inputs are unavailable, an algorithm can instead arrange isolated receptions directly. We give two alternatives: a deterministic schedule that works for every neighborhood of bounded size, and a random rule whose progress is analyzed along paths. Both use unrestricted aggregation. 9

5.1

A deterministic selective schedule

Definition 5.1. A family F ⊆ 2[n] is strongly r-selective if for every Z ⊆ [n] with 1 ≤ |Z| ≤ r and every z ∈ Z, some F ∈ F satisfies F ∩ Z = {z}. Lemma 5.2. For 2 ≤ r ≤ n there exists a strongly r-selective family of size O(min{n, r2 log n}). For every fixed r, such a family can be constructed deterministically in polynomial time in n. Proof. Generate T rows, including each identifier independently with probability 1/r in each row. A row isolates a specified pair (Z, z) with probability 1 1 1 (1 − 1/r)|Z|−1 ≥ (1 − 1/r)r−1 ≥ . r r er The last inequality follows from (1 + 1/(r − 1))r−1 ≤ e. The number of pairs is r X

n s s s=1

!

=n

r X n−1 s=1

s−1

!

≤ rnr .

Consequently the expected number of pairs isolated by no row is at most rnr exp(−T /(er)). Taking T = 4r(r + 1) ⌈log n⌉ makes this expectation less than one, because T 4 ln r + r ln n ≤ (r + 1) ln n < (r + 1) ⌈log n⌉ = . e er Thus T = O(r2 log n) rows suffice. For the deterministic construction, fix lexicographic orders on all pairs (Z, z) and on the nT membership bits, then expose the bits in that order. For each value of the next bit, compute the conditional expected number of unisolated pairs. For a given pair, its failure probability is the product over rows of one minus that row’s conditional isolation probability. Each row probability is computed from the fixed bits and remaining independent membership probabilities. The expectation before fixing a bit is a convex combination of the expectations for its two values, so some value does not increase it. Choose such a value, using a fixed rule to break ties. When all bits have been fixed, the number of unisolated pairs is an integer below one and hence is zero. Discarding duplicate rows gives the required family. For fixed r, there are polynomially many pairs and bits. All computed probabilities are rational numbers with polynomial bit length: their denominators divide a power of r with exponent at most rT . Thus the construction, including its arithmetic, takes polynomial time for fixed r. Finally, the n singleton subsets form a strongly r-selective family for every r ≤ n. If the prescribed row count T is at least n, use this explicit family instead; otherwise use the construction above. This proves the stated minimum without changing the fixed-r polynomialtime guarantee. When n is known, any larger supplied degree bound may first be replaced by n − 1. We can therefore use the following parameter range without losing generality. Theorem 5.3. Suppose every vertex knows n, its identifier, and a common integer degree bound ∆0 with ∆ ≤ ∆0 ≤ n−1. A topology-independent schedule completes M2M in O(d min{n, (∆0 + 1)2 log n}) slots. Its offline construction is polynomial for fixed ∆0 ; in that case the completion bound is O(d log n). Proof. Use Lemma 5.2 with r = ∆0 + 1. All vertices use the same deterministically chosen family and ordering of its rows. One cycle consists of these rows. Each vertex freezes a copy of its accumulated records at the start of the cycle. In row F , the vertices with identifiers in F 10

transmit their frozen copies, including empty packets, and the others listen. Received records are accumulated for later cycles. For an oriented edge uv, take Z = N [v] and z = u. Since |N [v]| ≤ ∆0 + 1, a row isolates u in Z. In that row u transmits, v listens, and all other neighbors of v listen. Every record known by u at the cycle’s start therefore reaches v during the cycle. By induction on distance, every source record reaches every participant after at most d cycles. Multiplying by the family size proves the bound.

5.2

Independent random transmission

The selective schedule bounds the time for each hop deterministically. For random transmission, we instead track one copy of a record along a fixed path and bound its chance of advancing in each slot. Its position depends on earlier slots, so the analysis needs a tail bound that allows this dependence. Lemma 5.4. Let (Ht )Tt=0 be a filtration and let Xt ∈ {0, 1} be Ht -measurable. Suppose 0 < q ≤ 1 and Pr(Xt = 1 | Ht−1 ) ≥ q almost surely for every 1 ≤ t ≤ T . Put µ = T q. Then Pr

" T X

#

Xt < µ/2 ≤ e−µ/8 .

t=1

Proof. For every t, almost surely, E[e−Xt | Ht−1 ] ≤ 1 − q + q/e ≤ exp[−q(1 − e−1 )]. Since i<t Xi is Ht−1 -measurable, iterating conditional expectation gives E[exp(− exp[−µ(1 − e−1 )]. Markov’s inequality now bounds the stated probability by P

eµ/2 E[e−

P t

Xt

t Xt )] ≤

P

] ≤ exp[−µ(1/2 − e−1 )] ≤ e−µ/8 ,

where e−1 < 3/8. This argument does not assume mutual independence of the Xt . Theorem 5.5. Let a common integer ∆0 ≥ ∆ be known. In each slot, every vertex independently transmits its current set of records with probability p = 1/(∆0 + 1) and otherwise listens. Fresh coins are used in every slot, and empty packets may be transmitted. For every 0 < η < 1, M2M completes with probability at least 1 − η within O((∆0 + 1) [d + log(k/η)]) slots. The rule runs continuously using only the degree bound and fresh random coins. The parameters k, d, and η enter only the completion guarantee; no stopping time is asserted. Proof. Fix distinct participants s, t and a shortest path v0 = s, v1 , . . . , vℓ = t, where ℓ ≤ d. Track a marked copy of the record along this path. The mark starts at v0 and advances by at most one edge per slot. If it is currently at vi , an advance occurs when vi transmits and all vertices in N [vi+1 ] \ {vi } listen. The marked record then reaches vi+1 . Other successful receptions can only make the actual dissemination earlier than this tracked process. Before it reaches t, the marked location is determined by the previous history. Conditional on that history, the probability of an advance is p(1 − p)deg(vi+1 ) ≥ p(1 − p)∆0 =

(1 + 1/∆0 )−∆0 1 ≥ q := . ∆0 + 1 e(∆0 + 1)

Here (1 + 1/∆0 )∆0 ≤ e, and fresh slot coins are independent of the preceding history. Use the filtration Hj generated by the execution through slot j. Let Xj indicate an advance in slot j, 11

and set Xj = 1 in every slot after the mark arrives. The variables Xj are Hj -measurable, and the dummy successes ensure that Pr(Xj = 1 | Hj−1 ) ≥ q for every slot. If the mark has not P arrived by time T , then Tj=1 Xj < ℓ. Set a = ln(k 2 /η) and T = ⌈8(d + a)/q⌉. Then µ = T q ≥ 8(d + a) and ℓ ≤ d ≤ µ/2. Failure P of actual delivery implies that the mark has not arrived, and hence that j Xj < ℓ ≤ µ/2. Lemma 5.4 therefore gives Pr[the record from s has not reached t by T ] ≤ e−µ/8 ≤ η/k 2 . A union bound over the k(k − 1) ordered pairs proves the success guarantee. Since q −1 = e(∆0 + 1) and ln(k 2 /η) ≤ 2 ln(k/η), the stated bound follows. All records share aggregate packets, so they incur no queueing delay. The paths are used only in the analysis. The high-probability bound has two immediate consequences. The first uses the fact that bounded degree also limits the number of participants in a ball of radius d; the second concerns completion time even though the protocol does not detect completion. Corollary 5.6. For fixed ∆0 and every 0 < η < 1, the random-transmission protocol completes in O(d + log(1/η)) slots with probability at least 1 − η. In particular, for fixed c > 0 it completes in O(d + log n) slots with probability at least 1 − n−c . Proof. Fix a participant s. Every participant belongs to its radius-d ball. Counting walks of lengths at most d gives k≤

d X

∆i0 ≤ (∆0 + 1)d .

i=0

The second inequality follows from the binomial expansion, since d ≥ 1. Hence log k ≤ d log(∆0 + 1). Substitute into Theorem 5.5; for fixed ∆0 this proves the first assertion. Take η = n−c for the second. Corollary 5.7. The random-transmission protocol completes almost surely. Its completion time TM2M satisfies E[TM2M ] = O((∆0 + 1)(d + log k)). For fixed ∆0 , the expectation is Θ(d). These are completion-time bounds, not bounds on a locally detected stopping time. Proof. The proof of Theorem 5.5 gives, for every integer T with T q ≥ 2d, Pr(TM2M > T ) ≤ min{1, k(k − 1)e−qT /8 },

q=

1 . e(∆0 + 1)

The right side tends to zero, proving almost-sure completion. Put T0 = ⌈(8/q)(d + 2 ln k)⌉. For every integer u ≥ 0, the same bound gives Pr(TM2M > T0 + u) ≤ e−qu/8 . Summing the tail yields E[TM2M ] ≤ T0 +

X u≥0

e−qu/8 = T0 +

1 ≤ T0 + 16/q = O(q −1 (d + log k)), 1 − e−q/8

where 1−e−q/8 ≥ q/16 for 0 < q ≤ 1. For fixed ∆0 , the ball-counting inequality in Corollary 5.6 gives log k = O(d), proving an O(d) expectation. A record can cross at most one edge per slot, so a pair of participants at distance d cannot complete its exchange earlier than slot d under this forwarding rule. Hence the expectation is also at least d. No stopping rule is used.

12

The fixed-degree conclusion uses the restriction that only exponentially many participants fit within distance d. As the degree grows, even a participant set of diameter two can incur a logarithmic collection cost. The next star example gives a matching lower bound for the independent random rule of Theorem 5.5. Proposition 5.8. On a star with L ≥ 2 participating leaves and a nonparticipant center, use the random-transmission rule with ∆0 = L. Then E[TM2M ] = Θ(L log L). For 0 < η ≤ 1/2, achieving completion probability at least 1 − η requires Ω(L log(L/η)) slots; the upper bound of Theorem 5.5 has the same order on this instance. Proof. Here k = L and d = 2. In a slot, a specified leaf succeeds at the center with probability r = p(1 − p)L ,

p=

1 , L+1

r = Θ(1/L).

The exponent counts the center and the other L − 1 leaves. Every route between distinct leaves passes through the center. Thus a record not yet received by the center is present only at its source leaf, and its first reception must be directly from that leaf. The successful sender identity is independent between slots, and successes of different leaves are disjoint within a slot. If i leaf records have not reached the center, the probability of receiving a new one in the next slot is ir. The expected time to receive all of them is therefore HL /r = Θ(L log L), where P HL = L i=1 1/i. This lower-bounds M2M completion; Corollary 5.7 supplies the upper bound. For the confidence bound, let M count leaf records never received by the center in the first T slots. Then m := E[M ] = L(1 − r)T . For two different leaves, the probability that neither succeeds is (1 − 2r)T ≤ (1 − r)2T , so Var(M ) ≤ m. Cauchy–Schwarz gives Pr(M > 0) ≥

(EM )2 m ≥ . E[M 2 ] 1+m

If completion has probability at least 1 − η, then Pr(M > 0) ≤ η and m ≤ η/(1 − η). Consequently ln(L(1 − η)/η) T ≥ = Ω(L log(L/η)), − ln(1 − r) Specifically, r ≤ 1/3 gives − ln(1 − r) ≤ 3r/2, while L ≥ 2 and η ≤ 1/2 give ln(L(1 − η)/η) ≥ 1 2 ln(L/η). Together with r = Θ(1/L) these inequalities justify the displayed asymptotic lower bound uniformly in L and η. Theorem 5.5 gives the matching upper bound because d = 2.

6

Deletions and changing subgraphs

The static proofs separate collision avoidance from progress. Deleting edges preserves the coloring and therefore preserves collision avoidance. Progress must instead be measured in the surviving graph. When edges change repeatedly, a previously sent record may need to cross a newly available edge, so forwarding only after a state change is no longer sufficient. Proposition 6.1. Let G0 have an installed distance-two coloring with C colors, and let the operating graph H be a fixed connected subgraph obtained by vertex and edge deletions before the protocol starts. Initialize each surviving participant with its original record. If at least two participants survive, the color-cycle protocol completes their exchange within (C − 1)dH + 1 slots, where dH is their diameter in H. It uses at most |V (H)| |S ∩ V (H)| transmissions.

13

Proof. Every path of at most two edges in H is also a path in G0 . The restricted coloring is therefore proper for H 2 . Apply Theorem 3.2 in H with the surviving participants and their records. Its proof uses only identifier distinctness, so the original identifiers can be retained. The forwarding rule needs no participant count; if the stopping rule of Corollary 3.3 is used, the count must be that of the surviving participants. For changes between cycles, use the fixed coloring but transmit in every assigned slot. This lets a newly available edge carry records sent earlier. Theorem 6.2. Let G0 = (V, E0 ) have a distance-two coloring with C colors. In cycle i, let the operating graph be a spanning subgraph Hi ⊆ G0 , fixed throughout that cycle. Suppose that for some integer W ≥ 1 the union of every W consecutive cycle graphs is connected. If every vertex broadcasts its current accumulated records in its color slot in every cycle, then every initial record reaches every vertex within CW (n − 1) slots. The graphs Hi may depend on the preceding execution history, subject to the stated conditions. Neither W nor the connectivity window is used by the forwarding rule. Proof. The coloring remains proper for Hi2 , so every transmission reaches all current neighbors. Fix one source record and partition time into blocks of W cycles. Let I be its informed set at the beginning of one block. If I ̸= V , the connected union of the block’s cycle graphs contains an edge uv with u ∈ I and v ∈ / I. In a cycle containing that edge, u still knows the record and transmits it in its color slot. Vertex v either already knows it or receives it then. Thus the informed set grows by at least one vertex during each unfinished block. It starts nonempty and is monotone, so at most n − 1 blocks suffice. The same argument holds simultaneously for all records. This protocol makes n transmissions per cycle, so its stated deadline uses nW (n − 1) transmissions. The rule continues after completion unless an additional stopping rule is supplied. For W = 1, every cycle graph is connected and the deadline is C(n − 1) slots. Stability within a cycle is a separate assumption, not a consequence of connectivity. For example, take a triangle host with colors 1, 2, 3 and track a record initially at vertex 1. In vertex 1’s slots use the path 1–2–3; in vertex 2’s slots use 2–1–3; in vertex 3’s slots use any connected spanning graph. Vertex 2 learns the record, but vertex 3 never receives it. Every slot graph is connected, yet the edges change before the needed color slot. This example explains why the theorem fixes each operating graph for a whole cycle.

7

Diameter guessing and preprocessing reductions

The preceding forwarding protocols run without knowing d. The following reductions address protocols prepared for supplied parameter bounds or clusters. Each reduction takes its stated base protocols, parameter budgets, and structural data as inputs. These hypotheses are not consequences of the static-network theorems and must be verified in each application. As in Proposition 3.6, combined executions use separate working states and clocks, while delivered records are retained in an output buffer.

7.1

Preserving an additive term when the diameter is unknown

Starting diameter trials at one can repeatedly charge an additive cost that dominates the early trials. Starting near the scale at which the diameter term balances that additive cost avoids this accumulation. Theorem 7.1. Fix all parameters except participant diameter, and let a common integer cap D0 ≥ d be known. Suppose that for every integer 1 ≤ δ ≤ D0 a deterministic protocol P(δ) 14

completes whenever d ≤ δ. Assume that a known sufficient budget is at most Aδ + B, where A ≥ 1 and B ≥ 0 are common known coefficients independent of δ. Trials can be interrupted at their budgets, even when δ < d, and reset to their initial working states while retaining the original source records. No trial fabricates records. Then M2M can be completed within 5Ad + 2B = O(Ad + B) slots without knowledge of d. Proof. Set δ0 = min{D0 , max{1, ⌈B/A⌉}},

δi = min{D0 , 2δi−1 }.

Run the trials consecutively, assigning trial i exactly ⌈Aδi + B⌉ slots. At its common starting boundary, reset every vertex’s working state and set the trial’s local slot counter to zero. A vertex whose component execution halts early sends nothing until the next boundary. Keep received output records in a separate monotone buffer that does not alter a fresh trial’s state transitions. Local completion does not cause a vertex to abandon the prescribed trial execution. Let j be the first index with δj ≥ d; it exists because the guesses reach D0 . This index is used only in the analysis, and earlier trials may already have delivered some records. Since δ0 ≤ 1 + B/A, the case j = 0 gives ⌈Aδ0 + B⌉ ≤ A + 2B + 1 ≤ 2(Ad + B) ≤ 5Ad + 2B. Suppose j ≥ 1. The initial guess is not clipped at D0 , so B ≤ Aδ0 . Before the final trial the guesses double, and clipping can only decrease the last guess. Therefore j X

δi ≤ (2j+1 − 1)δ0 ,

d ≥ 2j−1 δ0 + 1,

i=0

where the second inequality uses integer diameters and δj−1 < d. The total rounded budget is at most U := A(2j+1 − 1)δ0 + (j + 1)B + (j + 1). Using the preceding inequalities, A ≥ 1, and δ0 ≥ 1, we obtain 5Ad + 2B − U ≥ Aδ0 (2j−1 + 1) − (j − 1)B + 5A − (j + 1) ≥ Aδ0 (2j−1 − j + 2) + 5A − (j + 1) ≥ 2j−1 − 2j + 6 ≥ 0. For the last step, the values at j = 1, 2, 3 are 5, 4, 4, and thereafter the expression increases; also 2j−1 − j + 2 > 0. Hence the total budget is at most 5Ad + 2B. Trial j succeeds by assumption. Resetting prevents earlier trials from changing its execution, and the output buffer preserves all genuine records delivered by any trial. The theorem bounds completion. Continuing through the trial at D0 also gives a finite protocol with a common final stopping time. The bound on that final stopping time may be larger. One may take D0 = n − 1 when n is known and the base family is defined for every guess in [1, n − 1].

7.2

Geometric discretization of parameter tables

Diameter guessing controls online completion time. We next consider the separate offline cost of preparing a family of protocols. If each protocol accepts parameter upper bounds, it suffices to prepare a geometric grid of those bounds rather than every integer pair.

15

Theorem 7.2. Suppose n and D are supplied to preprocessing, and a protocol family accepts upper bounds (δ, κ) on participant diameter and count. Each member must be correct for every participant set with diameter at most δ and size at most κ, and must have preprocessing cost at most P (n). Let F (n, δ, κ) be an upper bound on online time. Suppose there is a constant c such that for all valid parameter pairs in [1, D] × [2, n], F (n, δ ′ , κ′ ) ≤ cF (n, δ, κ)

whenever

δ ≤ δ ′ ≤ 2δ,

κ ≤ κ′ ≤ 2κ.

Preparing only geometric grids of δ ∈ [1, D] and κ ∈ [2, n] costs O(P (n) log(D + 1) log n) and preserves the online bound up to the factor c, when the requested parameter bounds are rounded to those grids. Proof. For the diameter grid use the powers of two not exceeding D, together with D. For the count grid use the powers of two in [2, n], together with n. Each requested integer parameter rounds upward to a grid point less than twice its value, or to itself. The grids contain O(log(D+ 1)) and O(log n) values, respectively. Preprocess every pair. Correctness follows because the rounded values are upper bounds, and the displayed stability condition bounds the online cost. Multiplying the number of pairs by P (n) proves the preprocessing bound. A routine valid for a count upper bound must also finish when fewer participants are present; waiting for exactly κ distinct records does not satisfy this premise. For example, P (n) = O(n3 ) yields O(n3 log(D+1) log n) total preprocessing under the theorem’s hypotheses. The requested bounds are inputs to the selection of a table entry. In particular, this preprocessing reduction does not by itself give an online protocol for discovering an unknown participant count.

7.3

Composing cluster schedules

The geometric grid controls how many parameter choices are prepared. To use such protocols inside clusters, we must also control interference between concurrent executions. The following composition theorem states that extra requirement explicitly. A cluster may contain zero or one participant; its exchange is then complete initially, but its execution must still obey the prescribed slot schedule. The intrinsic diameter of a connected cluster U ⊆ V is the diameter of its induced subgraph G[U ], so paths used by its local protocol remain inside the cluster. Theorem 7.3. Fix a participant-diameter bound δ. Suppose a supplied family of connected clusters, partitioned into β classes, has the following properties: every cluster has intrinsic diameter at most αδ; clusters in a common class are vertex-disjoint with no edge between them; and every participant set of size at most k and diameter at most δ is contained in some cluster. Cluster memberships, class labels, and the protocol’s required structural inputs are supplied before the online execution. Suppose a within-cluster protocol is defined for every local participant set of size at most k, is interruptible at class boundaries, and completes every such exchange within a supplied common integer budget τ = O(αδ + Q(n, k)) slots. Then M2M for every such participant set can be completed in O(β[αδ + Q(n, k)]) slots. If all vertices know the exact global count k, it suffices that the local protocol complete within τ slots whenever its cluster contains all k participants, provided every execution is interruptible after τ slots and never fabricates records. Proof. Run each class for τ slots, in sequence; local completion does not remove a vertex from later classes. At each class boundary, initialize every cluster protocol with its original local source records and a local clock set to zero. Execute the class’s cluster protocols concurrently, with all other vertices silent. Earlier outputs are retained separately and do not change the new 16

working states. A receiver has no neighbor transmitting for another cluster of that class, by the separation assumption. Each cluster execution is therefore identical to its isolated execution. The separate states also accommodate vertices shared by clusters in different classes. Choose a cluster that contains the entire actual participant set. Its local protocol completes their exchange within τ slots. All participants retain its output. The β classes take βτ slots in total, giving the claimed bound. The schedule need not identify in advance which cluster contains all participants. In the exact-count case, the containing cluster has all k participants and succeeds within τ slots. Interrupt every other execution after τ slots. Isolation protects the containing execution, while the monotone output buffer retains only genuine source records. The exact-count variant retains the supplied value of k; count gridding still requires the upper-bound correctness hypothesis of Theorem 7.2. Corollary 7.4 (Conditional substitutions). Under the hypotheses of Theorem 7.3, with δ = d and Q(n, k) = k log2 n/ log k, each indicated pair of cover parameters gives the following completion bound: α β completion bound O(log n) O(log n) O(d log2 n + k log3 n/ log k) O(1) O(log n) O(d log n + k log3 n/ log k) O(log n) O(1) O(d log n + k log2 n/ log k) O(1) O(1) O(d + k log2 n/ log k). Proof. Substitute the indicated values of α, β, and Q into Theorem 7.3. Each row is conditional on both the indicated cover and a local protocol with the specified Q(n, k); no existence claim for either is made here. Moreover, the substitution δ = d supplies the diameter parameter. Removing that knowledge requires a base family and common budgets satisfying Theorem 7.1, in addition to the hypotheses above. Proposition 7.5. For a cluster family partitioned as in Theorem 7.3, write nU = |U | and N = maxU nU . If preprocessing one cluster costs O(n2U log(nU + 1)) with a uniform implicit constant, the total cost of these computations, excluding cover construction and partitioning, satisfies Tprep = O(βnN log(N + 1)) . Proof. A vertex belongs to at most one cluster of each class, so U nU ≤ βn. Since nU log(nU + 1) ≤ N log(N +1), the sum of the individual cost bounds is at most a constant times N log(N + P 1) U nU . P

8

Ranks and designated delivery

The cluster reduction makes the local communication guarantee an explicit premise. To justify that premise through a tree-based gathering argument, one must control both progress in the tree and interference in the full radio graph. Tree ranks can organize progress, but non-tree edges may invalidate the proposed simultaneous transmissions. We first bound the ranks of the subtree formed by participant-to-root paths. We then examine the additional interference condition needed for simultaneous transmissions. Throughout this section, pruning means deleting tree branches and recomputing ranks. The counterexample concerns that operation and the specified parent-transmission schedule: the interfering radio edges remain in place. Definition 8.1. For a rooted tree and an integer x ≥ 2, define rankx (v) recursively. Leaves have rank one. If the largest child rank of an internal vertex is r, the vertex has rank r + 1 when at least x children have rank r, and rank r otherwise. 17

Lemma 8.2. If the subtree rooted at v has ℓv leaves, then ℓv ≥ xrankx (v)−1 . Consequently, the union of the root paths from k selected vertices has maximum x-rank at most 1 + ⌊logx k⌋ when ranks are computed in that union. Proof. Induct upward from the leaves. A leaf satisfies the assertion with equality. If a vertex inherits rank r, a child of rank r already has at least xr−1 leaves. If its rank increases from r to r + 1, at least x disjoint child subtrees each have at least xr−1 leaves. In either case the inequality follows. For the second assertion, let S be the selected set and let TS be the union of its root paths. Recompute ranks using only the tree edges of TS . Every leaf of TS is selected: an unselected vertex on one of these paths has a successor toward the selected endpoint and hence is not a leaf. Thus TS has at most k leaves. Applying the first inequality within TS gives xrankx (v)−1 ≤ k for every vertex of that tree, proving the stated bound. Using the rank bound for communication also requires accounting for non-tree edges in the radio graph. For binary ranks, call an edge from a nonroot vertex v to its parent fast when their ranks are equal. A same-layer fast class consists of the vertices of one depth whose fast edges have one specified rank. The class has the designated-delivery property when simultaneous transmissions by its vertices, with all other vertices listening, reach all of their respective parents. The 2-height-respecting trees of Gańczorz, Jurdziński and Pelc [5] impose an explicit graphlevel condition: equal-height fast vertices in one layer have no common neighbor in the preceding layer. The next example identifies why pruning and recomputing ranks require rechecking this type of interference condition. Proposition 8.3. Pruning a breadth-first tree to the union of selected root paths and recomputing binary ranks can destroy the designated-delivery property of same-layer fast classes, even when it held for every class before pruning. Proof. Use the tree edges rA, rB, Aa, Bb, aa1 , aa2 , rooted at r, and include one further radio edge Ba. Every radio edge joins consecutive tree layers, so the tree is breadth-first. The binary ranks are rank2 (r) = rank2 (A) = rank2 (a) = 2,

rank2 (B) = rank2 (b) = rank2 (a1 ) = rank2 (a2 ) = 1.

The nonempty same-layer fast classes are the singleton classes {A}, {a}, and {b}, so each has the designated-delivery property. Now select only a and b and retain their root paths. The leaves a1 , a2 disappear, and the recomputed ranks of A, a, B, b are all one. Thus a and b form a same-layer fast class. Their simultaneous transmissions collide at B, which is adjacent to both of them, so b does not deliver to its parent. The interfering edge Ba remains in the radio graph, as shown in Figure 1. r

a1

A

B

a

b a2

Figure 1: The tree and additional radio edge used in Proposition 8.3. Pruning a1 , a2 puts a, b in one fast class, whose transmissions collide at B.

18

One-hop designated delivery The pruning example raises a simpler question: how many slots are sufficient when the receiving side has bounded degree? Consider a finite bipartite radio graph with sender set A and receiver set R. Each sender a ∈ A has a record and one designated adjacent receiver ρ(a) ∈ R. Only senders transmit, receivers always listen, and every designated receiver must obtain its sender’s record directly from that sender. Senders may retry. The schedule below is constructed from the bipartite incidence graph and the designated assignments. Define the conflict graph J on A by joining distinct senders a, a′ whenever a is adjacent to ρ(a′ ) or a′ is adjacent to ρ(a). This graph records exactly when two designated transmissions cannot both succeed in one slot. Theorem 8.4. The minimum number of slots for one-hop designated delivery is χ(J), even when retries are allowed. If every receiver has at most b ≥ 1 neighboring senders, then χ(J) ≤ 2b − 1, and a schedule using at most 2b − 1 slots can be constructed in polynomial time from the supplied incidence data. For every integer b ≥ 1, there is an instance with 2b − 1 senders and 2b − 1 receivers requiring exactly 2b − 1 slots. Proof. Exact characterization. The senders whose designated transmissions succeed in a particular slot form an independent set in J. If two were adjacent, one would interfere at the other’s designated receiver. From any successful T -slot schedule, choose one successful slot for each sender. These choices give a proper T -coloring, so T ≥ χ(J), regardless of retries. Conversely, transmitting one color class of a proper coloring in each slot makes every designated reception succeed. Thus the optimum is χ(J). Upper bound. Direct an interference arc from a to a′ whenever a ̸= a′ and a is adjacent to ρ(a′ ). Each sender a′ has at most b − 1 incoming arcs. Every edge of the induced conflict graph J[U ], for U ⊆ A, is represented by at least one such arc with endpoints in U . Hence |E(J[U ])| ≤ (b − 1)|U |. Every nonempty induced subgraph therefore has a vertex of degree at most 2b − 2. Repeatedly remove such a vertex, then greedily color in the reverse removal order. At most 2b − 1 colors are needed. Constructing J and performing this elimination takes polynomial time. Sharpness. Let m = 2b − 1, index senders ai and receivers Ri modulo m, designate ai → Ri , and set N (Ri ) = {ai , ai+1 , . . . , ai+b−1 }. For any distinct i, j, exactly one of the two cyclic differences j − i and i − j lies in {1, . . . , b − 1}. Thus the associated conflict graph is Km . Its chromatic number is m, and m singleton slots attain the lower bound. The case b = 1 is immediate from a single sender and receiver. For b = 2, the construction has three senders a, b, c with designated receivers A, B, C and neighborhoods N (A) = {a, b}, N (B) = {b, c}, and N (C) = {c, a}. At most one designated delivery succeeds per slot, so three slots are necessary. This recovers the three-sender obstruction and attains 2b − 1.

9

Conclusion

The results separate the information needed to prevent collisions from the information needed to recognize completion. A supplied distance-two coloring gives completion within (C − 1)d + 1 slots and at most nk transmissions without knowing the participant set, its size, or its diameter. Geometric inputs produce explicit palettes, including 15(∆0 +1) colors from one-hop data and a constant palette for fixed separation. Without those inputs, selective schedules and independent random transmission provide alternatives under a common degree bound. The random rule has 19

finite expected completion time, and its logarithmic cost on high-degree stars is unavoidable for that rule. For changing subgraphs, a fixed coloring still prevents collisions, while unconditional retransmission and connectivity over bounded cycle windows ensure progress. The parameter reductions address a separate issue: how to reuse already-correct protocols when diameter guesses, table entries, or clusters are supplied. Their guarantees remain conditional on the stated base protocols and structural data. Finally, the pruning example and the exact designated-delivery theorem show why local progress measures must be accompanied by an interference argument. Improving locality-sensitive protocols beyond these bounds will require combining stronger progress mechanisms with equally explicit scheduling invariants.

References [1] Dariusz R. Kowalski and Andrzej Pelc. Optimal deterministic broadcasting in known topology radio networks. Distributed Computing, 19(3):185–195, 2007. doi: 10.1007/s00446-006-0007-8. [2] Gianluca De Marco. Distributed broadcast in unknown radio networks. SIAM Journal on Computing, 39(6):2162–2175, 2010. doi: 10.1137/080733826. [3] Artur Czumaj and Peter Davies. Deterministic communication in radio networks. SIAM Journal on Computing, 47(1):218–240, 2018. doi: 10.1137/17M1111322. [4] Artur Czumaj and Wojciech Rytter. Broadcasting algorithms in radio networks with unknown topology. Journal of Algorithms, 60(2):115–143, 2006. doi: 10.1016/j.jalgor.2004.08.001. [5] Adam Gańczorz, Tomasz Jurdziński, and Andrzej Pelc. Optimal-length labeling schemes for fast deterministic communication in radio networks. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025), volume 361 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1–14:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. doi: 10.4230/LIPIcs.OPODIS.2025.14. Published 7 January 2026; preprint arXiv:2410.07382 first posted in 2024. [6] Leszek Gąsieniec, Igor Potapov, and Qin Xin. Time efficient gossiping in known radio networks. In Structural Information and Communication Complexity (SIROCCO 2004), volume 3104 of Lecture Notes in Computer Science, pages 173–184. Springer, 2004. doi: 10.1007/978-3-540-27796-5_16. [7] Leszek Gąsieniec, Igor Potapov, and Qin Xin. Time efficient centralized gossiping in radio networks. Theoretical Computer Science, 383(1):45–58, 2007. doi: 10.1016/j.tcs.2007.03.059. [8] Ferdinando Cicalese, Fredrik Manne, and Qin Xin. Faster centralized communication in radio networks. In Algorithms and Computation (ISAAC 2006), volume 4288 of Lecture Notes in Computer Science, pages 339–348. Springer, 2006. doi: 10.1007/11940128_35. [9] Ferdinando Cicalese, Fredrik Manne, and Qin Xin. Faster deterministic communication in radio networks. Algorithmica, 54(2):226–242, 2009. doi: 10.1007/s00453-007-9136-0. [10] Leszek Gąsieniec, Tomasz Radzik, and Qin Xin. Faster deterministic gossiping in directed ad hoc radio networks. In Algorithm Theory – SWAT 2004, volume 3111 of Lecture Notes in Computer Science, pages 397–407. Springer, 2004. doi: 10.1007/978-3-540-27810-8_34. [11] Chao Wu and Marek Chrobak. A gossiping protocol for sparse ad-hoc radio networks. arXiv preprint arXiv:2606.29152, 2026. URL https://arxiv.org/abs/2606.29152. [12] Qin Xin. Amplified pruning and path selectors for deterministic radio gossiping. arXiv preprint arXiv:2610.28930, 2026. URL https://arxiv.org/abs/2610.28930. First posted 20 October 2026. [13] Mohsen Ghaffari and Bernhard Haeupler. Fast structuring of radio networks for multi-message communications. In Distributed Computing (DISC 2013), volume 8205 of Lecture Notes in Computer Science, pages 492–506. Springer, 2013. doi: 10.1007/978-3-642-41527-2_34.

20

[14] Adam Gańczorz and Tomasz Jurdziński. Optimal-length labeling schemes and fast algorithms for k-gathering and k-broadcasting. In SOFSEM 2026: Theory and Practice of Computer Science, volume 16448 of Lecture Notes in Computer Science, pages 648–662. Springer, 2026. doi: 10.1007/ 978-3-032-17801-5_47. Preprint arXiv:2512.02252 first posted in December 2025. [15] Colin Krisko and Avery Miller. Labeling schemes for deterministic radio multi-broadcast. Theoretical Computer Science, 1071:115857, 2026. doi: 10.1016/j.tcs.2026.115857. Journal version of work first available as arXiv:2104.08644 in 2021. [16] Leszek Gąsieniec, Evangelos Kranakis, Andrzej Pelc, and Qin Xin. Deterministic M2M multicast in radio networks. Theoretical Computer Science, 362(1–3):196–206, 2006. doi: 10.1016/j.tcs.2006. 06.017. [17] Qin Xin, Fredrik Manne, Yan Zhang, and Xin Wang. Almost optimal distributed M2M multicasting in wireless mesh networks. Theoretical Computer Science, 439:69–82, 2012. doi: 10.1016/j.tcs.2012. 03.015. [18] Bogdan S. Chlebus, Dariusz R. Kowalski, and Tomasz Radzik. Many-to-many communication in radio networks. Algorithmica, 54(1):118–139, 2009. doi: 10.1007/s00453-007-9123-5. [19] Andrea E. F. Clementi, Angelo Monti, and Riccardo Silvestri. Selective families, superimposed codes, and broadcasting on unknown radio networks. In Proceedings of the Twelfth Annual ACM– SIAM Symposium on Discrete Algorithms, pages 709–718, 2001. [20] Jordan Kuschner, Yugarshi Shashwat, Sarthak Yadav, and Marek Chrobak. On permutation selectors and their applications in ad-hoc radio networks protocols. In Algorithmics of Wireless Networks (ALGOWIN 2024), volume 15026 of Lecture Notes in Computer Science, pages 106–116. Springer, 2025. doi: 10.1007/978-3-031-74580-5_8. Volume dated 2025; online proceedings published 26 December 2024; preprint arXiv:2402.10783. [21] Pawel Garncarek, Tomasz Jurdzinski, Dariusz R. Kowalski, Shay Kutten, and Miguel A. Mosteiro. Deterministic local problems in radio networks: On the impact of local domination and a bit of advice. In 36th International Symposium on Algorithms and Computation (ISAAC 2025), volume 359 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1–34:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi: 10.4230/LIPIcs.ISAAC.2025.34. [22] Dominick Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Thomas P. Hayes, and Gopal Pandurangan. Energy-efficient maximal independent sets in radio networks. In 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1–14:24. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi: 10.4230/LIPIcs.DISC.2025.14. [23] Yi-Jun Chang and Yang Ze Guan. Energy-efficient aggregation and minimum-degree spanning trees in radio networks. In Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2026). ACM, 2026. doi: 10.1145/3816782.3819229. Full version: arXiv:2605.30546.

21

Related documents

• The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach#1049065
• Distributed Marginal Return: A Communication-Efficient Algorithm for Multi-Agent Weapon Target Assignment#1588655
• Communication as Voting#1122925
• Administratively Scoped IP Multicast#137047
• Proper conflict-free choosability of sparse graphs with girth at least seven#998793