Energy-Efficient Aggregation and Minimum-Degree Spanning Trees in Radio Networks
arXiv:2605.30546v1 [cs.DC] 28 May 2026
Yi-Jun Chang∗
Yang Ze Guan†
Abstract We study the aggregation problem in synchronous multi-hop radio networks with O(log n)bit messages and no collision detection. Each node initially holds a value, and the goal is to compute a global aggregate such as the sum of all values. Aggregation tasks arise naturally in wireless sensor networks, where nodes are often battery-powered and radio activity is the dominant source of energy consumption. Accordingly, our main objective is to minimize the energy complexity, defined as the maximum number of rounds in which any node is awake. Our main result is a randomized distributed algorithm that, with high probability, constructs and executes an aggregation schedule in O(n polylog n) rounds and using O(∆∗ polylog n) energy, where ∆∗ is the minimum possible maximum degree of a spanning tree of the network graph. This guarantee is nearly optimal: for any aggregation schedule and any graph, there exists a node that must be awake for at least ∆∗ rounds. As a by-product, the algorithm also computes a spanning tree whose maximum degree is within an O(log n) factor of ∆∗ , with the same round and energy guarantees. For every tree edge, both endpoints learn that the edge belongs to the tree.
∗ †
National University of Singapore. ORCID: 0000-0002-0109-2432. Email: [email protected] National University of Singapore. ORCID: 0009-0008-0426-5926. Email: [email protected]
Contents 1 Introduction 1.1 Our Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 3 4 5
2 Technical Overview 2.1 Communication Primitive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Ingredients From Prior Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 New Ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Aggregation Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 5 6 7 9
3 Component–Node Matchings
10
4 Clustering 12 4.1 Metadata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Subroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5 Main Algorithms 14 5.1 Minimum-Degree Spanning Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.2 Aggregation Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 6 Slow Matching Algorithm 6.1 The Matching Subroutine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Degree Reduction Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27 28 29 30
7 Fast Matching Algorithm 7.1 The Matching Subroutine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Degree Reduction Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34 35 36 37
8 Conclusions
43
A Algorithms and Analysis for the Subroutines A.1 Down-Cast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Up-Cast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Across-Matching Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.4 Merge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.5 Approximate Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.6 Loneliness Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47 49 49 50 51 53 54
1
Introduction
Radio network model. We consider a synchronous multi-hop radio network model [CK85; CK87], where the network is modeled as an undirected graph G = (V, E) with |V | = n. Time is divided into discrete rounds. In each round, every node may either transmit, listen, or sleep. A node that sleeps consumes no energy in that round, and a node cannot transmit and listen simultaneously. When a node u transmits a message m in a given round, the message m is received by all neighbors v ∈ N (u) that are listening in that round, provided that no other neighbor of v transmits simultaneously. We emphasize that a node cannot send different messages to different neighbors. We assume that the network does not support collision detection: if two or more neighbors of a listening node transmit in the same round, the node receives nothing and cannot distinguish a collision from silence. Let RADIO[b] denote the radio network model with b-bit messages, where RADIO[O(log n)] is often known as the RADIO-CONGEST model and RADIO[∞] is often known as the RADIO-LOCAL model. All our algorithms work in the RADIO-CONGEST model. There are two main complexity measures of a distributed algorithm in the radio network model. The round complexity of an algorithm is the number of communication rounds needed by the algorithm. The energy complexity of an algorithm is the maximum energy cost of a node, where the energy cost of a node is defined as the number of rounds in which it is awake (i.e., either transmitting or listening). Energy-aware distributed computing. Energy efficiency is a fundamental concern in wireless sensor networks and has received extensive attention in networking and systems research. Many commercial sensor devices support multiple operating modes, typically including active and sleep states, with energy consumption in sleep mode being significantly lower [TKW+ 12]. For example, smart meters and distributed grid sensors can remain in a low-power state when energy consumption patterns are stable, and wake up only to report significant deviations or at predefined reporting intervals. A substantial body of applied research has focused on exploiting such sleep modes to enhance energy efficiency. To prolong network lifetime, a common strategy is to dynamically schedule sensors’ active and sleep periods. Numerous energy-aware scheduling mechanisms have been proposed to satisfy application-specific requirements while reducing overall energy usage. In cluster-based networks, for instance, cluster heads are often selected to minimize total energy consumption, and this role is periodically rotated among nodes to balance energy expenditure. A comprehensive survey can be found in [WX06]. It is noteworthy that listening to the communication channel costs energy even if no message is heard: This is known as idle listening, which has been identified as a major reason for energy loss [AMC07]. Aggregation task. Each node initially holds a value, and the goal of the aggregation task is to compute a single global value that summarises all node values. We focus on decomposable aggregation functions, which capture many natural operations such as count, sum, minimum, and maximum. Formally, an aggregation function f maps a multiset of values to a single output. We say that f is decomposable if there exists an associative operator ⋄ such that, for any two disjoint multisets X and Y , f (X ⊎ Y ) = f (X) ⋄ f (Y ),
1
where ⊎ denotes multiset union. Throughout the paper, we assume that all input values, intermediate aggregates, and final outputs can be represented within a single message of O(log n) bits. With a slight abuse of notation, we write f (v) to denote the result of applying f to the value held by node v ∈ V , and f (S) to denote the result of applying f to the multiset of values held by the nodes in S ⊆ V . Aggregation schedules. A common way to perform aggregation is to select a spanning tree T rooted at a node r and carry out a convergecast along T . Each node waits until it has received partial aggregates from its children, combines them with its own value using the operator ⋄, and forwards the resulting aggregate to its parent. At the end of this process, the root r obtains the correct aggregate value f (V ). More generally, an aggregation schedule specifies, for each round and each node, whether the node transmits a message, listens for messages, or remains idle, as well as the message it sends when it is active. At the end of the process, some node obtains the correct aggregate value f (V ). We require that the pattern of sending, listening, and idling across rounds is fixed in advance and does not depend on the aggregation function f or on the input values. Furthermore, whenever a node sends a message, that message should be formed by combining some of the messages it has received from its neighbors, optionally incorporating its own value, using the associative operator ⋄. Energy-optimal schedules. When aggregation is carried out along a spanning tree T , a key factor determining the energy cost is the maximum degree of T . Intuitively, a node of high degree must receive messages from many neighbors and therefore needs to remain awake in many rounds. Let ∆∗ = min{∆(T ) | T is a spanning tree of G}, where ∆(T ) denotes the maximum degree of T . In other words, ∆∗ is the maximum degree of a minimum-degree spanning tree of G. Fix a spanning tree T with ∆(T ) = ∆∗ . There is a simple aggregation schedule based on T that achieves energy O(∆∗ ) using O(n) rounds. For instance, we can assign each tree edge a dedicated time slot according to a post-order traversal and let each node transmit exactly once to its parent after it has collected all aggregates from its children. Since each edge of T is used once, the total number of rounds is n − 1, and each node is awake for degT (v) ≤ ∆∗ rounds. Thus, there exists an aggregation schedule whose energy matches the smallest possible maximum degree among all spanning trees of G. We now show that ∆∗ is not merely achievable by schedules based on minimum-degree spanning trees, but is in fact a universal lower bound that applies to every aggregation schedule. This bound is universal in the sense that it holds for every graph topology, rather than only for carefully constructed worst-case graph families. Observation 1.1 (Universal energy lower bound for aggregation). For any aggregation schedule, there exists a node that is awake for at least ∆∗ rounds. Proof. Consider an arbitrary aggregation schedule and construct a directed graph G→ on the node set V as follows. For every successful message transmission from a node u to a node v at any time during the execution, add a directed edge u → v to G→ . By construction, the energy cost incurred by a node due to listening is at least its indegree in G→ . At the end of the schedule, some node r has obtained the correct aggregate value f (V ). It follows that every node can reach r in G→ , since otherwise the initial value of some node could not influence the final aggregate at r. Therefore, there exists a directed spanning tree of G→ rooted at r in which all edges are oriented toward the root. 2
Let v be a node of maximum degree in T , so that degT (v) = ∆(T ). If v ̸= r, then it must listen in at least degT (v) − 1 rounds to receive messages from its children and transmit at least once to its parent; if v = r, then it must listen in at least degT (v) rounds to receive messages from all its children. In either case, v is awake for at least ∆(T ) rounds. Finally, since ∆∗ is the minimum possible maximum degree over all spanning trees of G, we have ∆(T ) ≥ ∆∗ . Therefore, some node is awake for at least ∆∗ rounds, completing the proof. The tree-based aggregation schedule, together with Observation 1.1, shows that a universally energy-optimal aggregation schedule exists. However, such a schedule relies on the availability of a minimum-degree spanning tree, or the ability to compute one efficiently. It remains unclear how to compute such a tree, or even a good approximation to it, in the radio network model. Moreover, even given a minimum-degree spanning tree, it is not obvious how to transform it into an aggregation schedule that is itself energy-efficient. The goal of this paper is to bridge this gap by designing an efficient distributed algorithm that simultaneously constructs a nearly optimal aggregation schedule and an O(log n)-approximation to a minimum-degree spanning tree.
1.1
Our Contribution
Our main result is a nearly universally energy-optimal algorithm for aggregation schedule in radio networks with O(log n)-bit messages. Throughout the paper, we say that an event occurs with high probability if it occurs with probability 1 − 1/ poly(n), where the exponent in poly(n) can be arbitrarily high. Theorem 1 (Energy-efficient aggregation). There exists a randomized algorithm that computes an aggregation schedule such that, with high probability, both the construction of the schedule and its execution take O(n polylog n) rounds and using O(∆∗ polylog n) energy in the RADIO-CONGEST model. While our definition of an aggregation schedule only requires a single node to obtain the final result, this result can be broadcast to all nodes in O(n polylog n) rounds and O(polylog n) energy with high probability [CDH+ 18]. This additional step does not affect the overall asymptotic round or energy complexities stated in Theorem 1. In fact, our aggregation schedule behind Theorem 1 already disseminates the final result to all nodes. As an additional outcome of the algorithm in Theorem 1, we obtain an efficient distributed algorithm for computing an approximately minimum-degree spanning tree. Theorem 2 (Energy-efficient minimum-degree spanning tree). There exists a randomized algorithm that computes a spanning tree T with maximum degree ∆(T ) ∈ O(∆∗ log n) with high probability in O(n polylog n) rounds and using O(∆∗ polylog n) energy in the RADIO-CONGEST model. An important feature of the algorithm in Theorem 2 is that, for every tree edge e = {u, v} ∈ T , both endpoints learn that e belongs to T , meaning that the knowledge of each tree edge is bidirectional. In particular, regardless of which spanning tree is produced, this implies that some node must learn the identifiers of at least ∆∗ distinct neighbors. Informally and intuitively, unless time-encoding techniques are used, this information-theoretically requires Ω(∆∗ ) awake rounds in the RADIO-CONGEST model. For both Theorem 1 and Theorem 2, the round complexity O(n polylog n) is also existentially optimal up to polylogarithmic factors. Indeed, even in a star graph, accomplishing either task requires the center node to successfully communicate with each of its n − 1 neighbors, which necessarily takes Ω(n) rounds, even in the RADIO[∞] model. 3
1.2
Related Work
The study of energy-aware distributed algorithms dates back to 2000 [NO00]. Early theoretical work [BKP+ 16; CKP+ 19; JKZ02; LMR07; NO00] primarily focused on single-hop radio networks, where all devices communicate over a shared channel, i.e., the communication graph forms a clique. Beginning around 2018, this line of research expanded to multi-hop radio networks with arbitrary topologies, addressing fundamental tasks such as broadcasting [CDH+ 18], breadth-first search [CDH+ 20; DH22], and maximal matching [DGH+ 23]. More recently, the scope has broadened further to encompass the LOCAL and CONGEST models [AMP24; BM21; CGP20; DH22; DMP23; GP22; GP23; GT24], covering a wide range of distributed graph problems, including maximal independent set, maximal matching, shortest paths, and minimum spanning tree. The MDST problem has also been extensively studied, initially in the sequential setting, where it is known to be NP-hard. Consequently, much of the literature focuses on approximation algorithms. A landmark result by Fürer and Raghavachari [FR94] shows that an additive-one approximation can be achieved in polynomial time, producing a spanning tree of maximum degree ∆∗ +1. The running time of this classical algorithm has been improved very recently [BFW26]. In the distributed domain, Blin and Butelle [BB03] adapted the Fürer–Raghavachari algorithm to an asynchronous distributed model. Dinitz, Halldórsson, Izumi, and Newport [DHI+ 19] developed an O(log n)√ approximation algorithm for MDST in the CONGEST model running in Õ(D + n) rounds. In the same paper, they also showed an improved deterministic algorithm achieving maximum degree √ O(∆∗ + log n) within the same round complexity, along with a matching Ω̃( n) lower bound. To the best of our knowledge, there is no prior work in algorithms and theory on the MDST problem in the RADIO model. While some previous works study other forms of spanning tree construction, such as BFS trees [CDH+ 20; GH16] or arbitrary spanning trees for broadcasting messages to the entire network [CDH+ 18; CD21; HW16], these results are not directly comparable to ours because they address different objectives. BFS in the RADIO model is well studied. It is known [GH16] that BFS can be constructed in O(D polylog n) rounds, where D is the diameter of the network. More recent works [CDH+ 20; DH22] also show that this can be achieved with O(polylog n) energy. However, these algorithms are not suitable for our purposes: they do not minimize the maximum degree of the tree, and therefore do not yield energy-efficient aggregation algorithms. Another key difference is that, in these BFS algorithms, knowledge of the tree edges is one-sided: children know their parent, but not vice versa. In contrast, our MDST algorithm provides a two-sided guarantee, where each tree edge is known to both endpoints. The notion of universal optimality, introduced in [GKP98], has attracted significant attention in recent years within distributed computing. In the CONGEST model, the low-congestion shortcut framework has enabled algorithms with almost universally optimal round complexity for several fundamental problems, including minimum spanning tree, (1 + ϵ)-approximate single-source shortest paths, and (1 + ϵ)-approximate minimum cut. Recent works achieves a round complexity of Õ(OPT) when the network topology is known in advance [HWZ21], or poly(OPT) without this assumption [HRG22, Theorem 1.4]. Data aggregation is a fundamental primitive in wireless sensor networks, underpinning applications such as environmental monitoring, and has therefore been widely studied in applied research [BSL+ 04; IEG+ 02; MFH+ 02; SBY06]. It also plays a central role in theoretical distributed computing, particularly in the design of universally optimal algorithms; see, e.g., [CHL+ 24; RGH+ 22].
4
1.3
Roadmap
In Section 2, we present an overview of our proofs. In Section 3, we introduce component–node matchings and prove the key structural properties. In Section 4, we discuss how we maintain a clustering and introduce the basic subroutines related to clustering. In Section 5, we combine these tools to obtain our main results: energy-efficient minimum-degree spanning tree and aggregation schedule. In Section 6, we show a slower matching algorithm for component–node matchings with near-optimal energy but suboptimal round complexity. In Section 7, we show a faster matching algorithm for large d. Appendix A provides the detailed algorithms and analyses for the clustering subroutines.
2
Technical Overview
In this section, we provide an overview of our proofs. In Section 2.1, we begin by reviewing a basic communication primitive for radio networks. In Section 2.2, we review the two main ingredients from prior work. In Section 2.3, we present the main new ideas underlying our O(log n)approximation algorithm for MDST in Theorem 2. Finally, in Section 2.4, we explain how these ideas are extended to obtain the energy-efficient aggregation schedule of Theorem 1.
2.1
Communication Primitive
We review a basic randomized communication primitive for radio networks that allows us to run many subroutines in parallel while keeping congestion low. Local broadcast. Consider a graph G = (V, E) with maximum degree ∆ and two disjoint node sets S, R ⊆ V , where each sender u ∈ S holds an O(log n)-bit message mu . The goal of local broadcast, denoted by Local-broadcast(S, R), is to ensure that every receiver v ∈ R with at least one sender neighbor (N (v)∩S ̸= ∅) receives a message mu from at least one neighbor u ∈ N (v)∩S. The primitive does not specify which sender succeeds when several senders are adjacent to the same receiver; it only guarantees delivery of at least one message to each eligible receiver. Lemma 2.1 (Local broadcast). There exists an O(log ∆ · log n)-round algorithm that accomplishes Local-broadcast(S, R) with high probability in the RADIO-CONGEST model. Proof. We use the standard decay procedure [BGI92]. Let L = ⌈log2 ∆⌉. One phase consists of L rounds indexed by i = 1, 2, . . . , L. In round i, each sender u ∈ S transmits its message mu independently with probability 2−i (and otherwise sleeps), while each receiver in R listens. ⋆ ⋆ Fix any receiver v ∈ R with k = |N (v) ∩ S| ≥ 1. Choose i⋆ such that 2i −1 ≤ k ≤ 2i . In round i⋆ , the probability that exactly one of the k sender neighbors transmits is ⋆
⋆
k · 2−i · (1 − 2−i )k−1 ∈ Ω(1). Hence, in one phase, v receives some message with constant probability. By repeating the phase c log n times (for a sufficiently large constant c), the failure probability for this fixed v becomes at most n−Θ(c) . Applying a union bound over all v ∈ R yields success with high probability. The total number of rounds is O(log ∆ · log n).
5
2.2
Ingredients From Prior Work
Our algorithm combines two ingredients from prior work. The first is the distributed approximation algorithm for the minimum-degree spanning tree (MDST) problem in the CONGEST model due to Dinitz, Halldórsson, Izumi, and Newport [DHI+ 19]. The second is an energy-efficient maximal matching algorithm for radio networks due to Dani, Gupta, Hayes, and Pettie [DGH+ 23]. Ingredient 1: Minimum-degree spanning trees. The algorithm of [DHI+ 19] computes an √ O(log n)-approximation for MDST in Õ( n + D) rounds in the CONGEST model, where the Õ(·) notation suppresses any O(polylog n) factor. As the optimum value ∆∗ is not known in advance, it guesses a parameter d by exponential search; once d ≥ ∆∗ , the construction succeeds with high probability. The main task is therefore the following: assuming d is an upper bound of ∆∗ , construct a spanning tree whose maximum degree is only O(d log n). To achieve this, [DHI+ 19] uses a Borůvka-style cluster-merging process. Initially, every node forms a singleton cluster. In each iteration, many clusters are merged in parallel using inter-cluster edges, while ensuring that no node gains too many new incident edges. If each iteration reduces the number of clusters by a constant factor, then after O(log n) iterations only one cluster remains, and the union of all chosen edges forms a spanning tree. Thus, the key issue in each iteration is to obtain enough merges while keeping the degree increase at every node under control. For our purposes, it is convenient to formulate the merging step using a random red–blue coloring of the current clusters. Each cluster independently becomes red or blue with probability 1/2. We then seek a set of inter-cluster edges such that each red cluster is incident to at most one selected edge, and each blue node is incident to at most d selected edges; that is, a 1-to-d matching between red clusters and blue nodes. While [DHI+ 19] does not rely on this red–blue formulation, it is convenient for us, as it allows us to focus on matchings over a bipartite graph. Assuming d ≥ ∆∗ , to see the existence of such a 1-to-d matching that can reduce the number of clusters by a constant factor, just fix any spanning tree of maximum degree at most d and restrict this tree to inter-cluster edges. Restricting further to edges whose endpoints lie in opposite colors loses only a constant factor in expectation. Hence, after the red–blue coloring, there is still a large feasible matching. Therefore, if we compute a maximal 1-to-d matching, then by a standard charging argument we obtain a constant-factor approximation to the largest such matching, and so one iteration still merges a constant fraction of the clusters. Repeating this for O(log n) iterations yields a spanning tree, and since each node gains at most d new incident edges per iteration, the final maximum degree is O(d log n). In our algorithm, we relax this matching primitive slightly. Instead of computing an exact maximal 1-to-d matching, we compute a d-almost-maximal (1, 2d)-component–node matching. Here, each red cluster is incident to at most one selected edge, and each blue node is incident to at most 2d selected edges. In addition, every unmatched red cluster sees only blue neighbors that already have at least d selected edges, and every blue node with fewer than d selected edges sees only matched red clusters. This slack between d and 2d makes the matching problem significantly easier in the radio network model, while still being sufficient for the same O(log n)-approximation framework. Thus, once such component–node matchings can be computed efficiently, the outer Borůvkastyle construction goes through. The main challenge is therefore not the clustering framework itself, but the design of an energy-efficient matching routine in the radio network model. Ingredient 2: Maximal matching. We now turn to the second ingredient, namely the energyefficient maximal matching algorithm of Dani, Gupta, Hayes, and Pettie [DGH+ 23]. At a high level, 6
their result shows that even in the radio network model, one can compute a maximal matching without paying linear energy in the maximum degree. The basic idea is a randomized degree-reduction process. In each round, every node independently decides whether to participate. If both endpoints of an edge e = {u, v} participate, while no other neighbor of u or v participates, then e can be safely added to the matching. The challenge is to choose the participation probability so that such isolated edges appear often enough, while keeping the amount of contention low. To balance these two requirements, [DGH+ 23] starts with a very small participation probability, on the order of 1/∆, and gradually increases it over time until it reaches a constant. Intuitively, when the participation probability is too small, very few edges are sampled; when it is too large, collisions dominate. By sweeping through this range, the algorithm guarantees that every node eventually experiences a regime in which its local degree is well matched to the current sampling probability, and hence it has a good chance to get matched. This yields a maximal matching in O(∆ log n) rounds using only O(log ∆ log n) energy. We consider a variant of this procedure in a more discrete form. Instead of changing the sampling probability continuously, we proceed in stages with parameters ∆, ∆/2, ∆/4, . . .. At the stage with parameter d, every node participates with probability Θ(1/d) for O(d log n) rounds. The guarantee of this stage is degree reduction: assuming the current maximum degree is at most d, after the stage, the remaining maximum degree drops to at most d/2 with high probability. Indeed, as long as a node still has degree larger than d/2, each round gives it a Ω(1/d) probability that one of its incident edges is safely added to the matching, so O(d log n) rounds suffice to eliminate such nodes with high probability.
2.3
New Ideas
Substantial new difficulties arise when we try to implement the matching algorithm of [DGH+ 23] over a cluster graph, and overcoming them is the main technical work in our matching algorithm. There are two main obstacles. Obstacle 1: Intra-cluster communication. First, even simulating one round of the bipartite matching process is expensive in our setting: some nodes of the graph are now clusters, and determining whether a red cluster should participate, whether it has a unique sampled blue neighbor, or which edge should be kept, requires communication inside the cluster. Such intra-cluster communication already costs O(n polylog n) rounds in the radio network model. Thus, a direct simulation of the O(∆ log n)-round process from [DGH+ 23] would introduce an additional multiplicative overhead of up to O(n polylog n), which is far too expensive for our target complexity. Obstacle 2: Higher node capacity. Second, our goal is not merely a maximal matching, but a d-almost-maximal (1, 2d)-component–node matching. A naive way to obtain this from a maximal matching routine is to repeat the process O(d) times, allowing blue nodes with remaining capacity to continue participating. While this is acceptable when d is very small, in general it would introduce an unacceptable extra factor of O(d) in both the round and energy complexities. Resolving the first obstacle: Big-rounds and unmatching phases. We resolve the first obstacle by grouping many ordinary matching rounds into a single big-round. During a big-round, nodes communicate only across inter-cluster edges, without any intra-cluster communication. Intuitively, this lets the matching process run for many local trials before paying the high cost of
7
synchronizing within each cluster. As a result, the total number of expensive intra-cluster coordination steps drops from O(∆ log n) to only O(polylog n). This batching creates a new issue: within one big-round, multiple nodes of the same red cluster may independently match to different blue nodes, since they are no longer coordinating in real time. To restore the required constraint that each red cluster contributes at most one edge, we add an unmatching phase. After the batched inter-cluster trials finish, each red cluster locally selects one incident matched edge to keep, and cancels the rest. Informally, we first allow the cluster to “over-match” in order to save rounds, and then repair this over-matching using one carefully placed coordination step. The main challenge is then the analysis, since the unmatching phase creates dependencies that are absent in an ordinary matching process. To handle this, we classify red clusters as small or large based on the expected number of incident matched edges they create during a big-round. We then split the analysis into two parts. First, we show that after O(log n) big-rounds, every active red cluster becomes inactive or small. The intuition is that any large red cluster is likely to create some matched edge and hence become inactive. Second, conditioned on all remaining active red clusters are small, we show that every high-degree blue node gets matched within another O(log n) big-rounds. Here the key point is that when the cluster is large, a newly created matched edge is unlikely to be canceled in the subsequent unmatching phase. Making this argument work requires careful probabilistic estimates, including second-moment bounds, to cope with the fact that the relevant random events are not fully independent. Resolving the second obstacle: Adjusting the sampling rate. We resolve the second obstacle, i.e., extending maximal matching to a d-almost-maximal (1, 2d)-component–node matching, by using different strategies in two regimes. When d is only polylogarithmic, we can afford the simple approach: we repeat the big-round procedure O(d) times, always allowing blue nodes that still have remaining capacity to participate. This already gives the desired guarantee at the right asymptotic cost in this regime. The more interesting case is when d is large. At a high level, since a blue node is allowed to accept many incident edges, one would like to increase the sampling rate on the red side by a factor of Θ(d), thereby creating many candidate matches in parallel without increasing the number of big-rounds. The difficulty is that this makes the acceptance rule at blue nodes much more complicated: unlike in ordinary matching, a blue node may now need to accept many incident edges simultaneously, and an overly aggressive sampling rate could force us to add yet another repair mechanism on the blue side. To avoid this, we use a more conservative boost. Instead of increasing the red-side sampling probability by a factor of Θ(d), we increase it by only Θ(d/ log n). This is still large enough to exploit the higher capacity of blue nodes, but small enough that a Chernoff bound guarantees that, in one big-round, each blue node receives at most d incident selected edges with high probability. In particular, we never need a second unmatching mechanism for blue nodes. This is exactly where the slack in our target, i.e., the gap between the saturation threshold d and the capacity bound 2d, becomes essential: it gives enough room to absorb random fluctuations while keeping the algorithm simple. These ideas yields a matching routine with the right guarantees for the outer Borůvka-style framework: it computes a d-almost-maximal (1, 2d)-component–node matching in O(n polylog n) rounds using O(d polylog n) energy. This allows us to prove Theorem 2.
8
2.4
Aggregation Schedule
It remains to explain how we turn the MDST construction into an energy-efficient aggregation schedule to prove Theorem 1. A natural first idea is to use the spanning tree directly and aggregate along it. However, the two most obvious approaches both run into difficulties in the radio network model. On the one hand, the earlier proof of the existence of an efficient aggregation schedule uses a sequential post-order traversal of the tree, but it is not clear how to compute such a global ordering efficiently in a radio network. On the other hand, a naive layer-by-layer aggregation is also problematic: the tree may have linear depth, and even within a single layer the contention can be large, so the resulting schedule can easily be too slow. Thus, although a low-degree spanning tree guarantees the existence of an efficient aggregation schedule, extracting such a schedule algorithmically is itself a challenging task. Our solution is to exploit the hierarchical decomposition already produced by the Borůvka-style MDST construction. Recall that the MDST algorithm does not build the final tree all at once; instead, it repeatedly merges clusters, thereby creating a hierarchy H in which each cluster is formed from a small star of clusters from the previous level. We use this hierarchy, rather than the final spanning tree alone, as the backbone of the aggregation schedule. Intuitively, the hierarchy gives us a decomposition of the global aggregation task into smaller subtasks, each attached to one merge step of the MDST construction. High-level ideas. The high-level plan is recursive. For each cluster C in the hierarchy, we construct an aggregation schedule that computes the aggregate over all nodes of C and then disseminates the result to all nodes in C. To realize this approach, we first have each cluster compute a coarse approximation to its size. We then prove, by induction over the hierarchy, that every cluster C of size s admits an aggregation schedule of length O(s polylog n) while using low energy per node. Since the root cluster has size n, this immediately yields a global schedule of length O(n polylog n). Every cluster C at level ℓ arises from a star of clusters at level ℓ − 1: one “center” cluster and several “leaf” clusters attached to it by the matching edges chosen in the corresponding Borůvka step. This suggests a natural four-step recursive construction. First, we execute the aggregation schedules of the leaf clusters, so that each leaf computes its own aggregate. Second, we use the matching edges of the star to transmit these partial aggregates to the center cluster. Third, we execute the aggregation schedule of the center cluster, now incorporating the values received from the leaves. Fourth, we disseminate the resulting aggregate of C to all nodes of C. Repeating this bottom-up through the hierarchy ensures that the root cluster eventually computes the global aggregate. Technical challenges. The main technical difficulty is to make the above first step efficient. In principle, the schedules of the leaf clusters could be run either sequentially or in parallel, but neither extreme works well. A fully sequential execution is too slow and, more importantly, difficult to coordinate globally in a radio network. A naive parallel execution is also problematic, because the resulting radio contention can be excessive: if one adds random delays independently at every level to spread out this contention, then the overhead can accumulate across the hierarchy and lead to an extra polylogarithmic factor per level. To handle this, we introduce a slightly more abstract notion of an aggregation schedule in which time is partitioned into slots, and congestion is measured per slot rather than per round. This slot-based view lets us separate two concerns. The recursive construction determines which communication events belong to the same slot, while a later transformation converts each slot into 9
actual rounds. As a result, we can analyze random delays cleanly at the level of slots, without having to commit immediately to a detailed round-by-round execution. The eventual conversion from slotbased schedules to standard round-based schedules incurs only a polylogarithmic overhead. Even in the slot-based setting, however, random delays must be used carefully. Delaying a child schedule adds overhead proportional to the maximum child schedule length. If we applied random delays to all children at every level, then each level could incur a constant-factor inflation, and over O(log n) levels this would make the total schedule too long. We avoid this by splitting the children of each cluster into large and small ones. The schedules of the large children are run sequentially, without random delays. Random delays are used only for the small children, whose schedules are guaranteed to be much shorter than that of their parent. This ensures that the extra overhead introduced by delaying the small children is only a small fraction of the parent schedule length. In this way, the recursion remains efficient across all levels of the hierarchy. The remaining issue is congestion. After introducing random delays, many child schedules may overlap, so we need a way to show that no slot becomes too crowded. For this purpose, we analyze the congestion in each slot using a recursively defined family of random variables that captures exactly how overlaps arise across the hierarchy. We show that every such random variable has expectation at most 1 and satisfies a strong concentration bound: with high probability, every slot in the resulting randomized schedule has congestion at most O(log n) with high probability. Putting everything together, we obtain an aggregation schedule whose construction and execution both take O(n polylog n) rounds and use O(∆∗ polylog n) energy with high probability. Thus, the same hierarchical structure that lets us build a low-degree spanning tree also provides the right scaffold for turning that tree into a nearly energy-optimal aggregation schedule.
3
Component–Node Matchings
Let F ⊆ E be a subset of edges of a graph G = (V, E). For any node v ∈ V , we write degF (v) = |{e ∈ F | v ∈ e}| to denote the number of edges in F incident to v. For any node subset S ⊆ V , we write degF (S) = |{e ∈ F | S ∩ e ̸= ∅}| to denote the number of edges in F incident to S. A clustering V = {V1 , V2 , . . . , Vs } of a graph G = (V, E) is a partitioning of the node set into non-empty parts V = V1 ∪ V2 ∪ · · · ∪ Vs . Throughout the paper, every cluster C in a clustering V is required to be connected. Component–node matching. Let V be a clustering of a graph G = (V, E), and suppose that the clusters are 2-colored red and blue. A node is called red (respectively, blue) if it belongs to a red (respectively, blue) cluster. A (1, k)-component–node matching is a set of edges M ⊆ E between red and blue nodes satisfying the following conditions: • For every red cluster C, we have degM (C) ≤ 1. • For every blue node v, we have degM (v) ≤ k. Almost-maximal component–node matching. Let s be an integer such that 1 ≤ s ≤ k. A (1, k)-component–node matching M is said to be a s-almost-maximal if it additionally satisfies the following conditions: • If degM (C) = 0 for a red cluster C, then every blue node u adjacent to C satisfies degM (u) ≥ s. • If degM (v) < s for a blue node v, then every red cluster C adjacent to v satisfies degM (C) = 1.
10
The proof of the following lemma is essentially identical to the proof of Lemma 4 in the arXiv:1806.03365v1 version of [DHI+ 19], except that we replace maximal (1, d)-component–node matching with an d-almost-maximal (1, 2d)-component–node matching. For completeness, we reproduce the proof here. Lemma 3.1 (Approximation ratio). Let M be an d-almost-maximal (1, 2d)-component–node matching, and let M ∗ be any (1, d)-component–node matching. Then |M | ≥ |M ∗ |/2. Proof. Consider any edge e ∈ M ∗ \ M . Suppose e connects a blue node v with a red cluster C. Since M is an d-almost-maximal (1, 2d)-component–node matching, at least one of the following conditions must hold: • degM (C) = 1. • degM (v) ≥ d. If degM (C) = 1, we assign e to C; otherwise we assign e to v. We claim that each red cluster or blue node is assigned at most as many edges from M ∗ \ M as its degree in M \ M ∗ . This implies |M ∗ \ M | ≤ 2 |M \ M ∗ |, and therefore |M ∗ | = |M ∗ ∩ M | + |M ∗ \ M | ≤ |M | + |M \ M ∗ | ≤ 2|M |, which proves the lemma. It remains to justify the claim. Red clusters. Each red cluster has degree at most one in both M and M ∗ . Thus, a red cluster C can be assigned at most one edge from M ∗ \ M . Moreover, if C is assigned such an edge, then C has exactly one incident edge in M \ M ∗ and exactly one incident edge in M ∗ \ M . Hence, the number of edges assigned to C is at most degM \M ∗ (C). Blue nodes. Suppose a blue node v is assigned k edges from M ∗ \ M . By definition of a (1, d)component–node matching, we have degM ∗ (v) ≤ d. Thus, k ≤ degM ∗ \M (v) ≤ d − degM ∩M ∗ (v). Since v is assigned only when degM (v) ≥ d, it follows that k ≤ degM (v) − degM ∩M ∗ (v) = degM \M ∗ (v), as required. Lemma 3.2 (Matching size). Let V be any clustering with |V| > 1. Color each cluster with red or blue with probability 1/2 independently. Let M be any d-almost-maximal (1, 2d)-component–node matching. If ∆∗ ≤ d, then |V| 1 Pr |M | ≥ ≥ . 16 7
11
Proof. Let T be an arbitrary spanning tree of G with maximum degree ∆∗ ≤ d, and let F be the set of inter-cluster edges of T . Since G is connected and there is more than one cluster, degF (C) ≥ 1 for each cluster C ∈ V. For each cluster C ∈ V, select one edge eC ∈ F whose one endpoint is in C. Let C ′ be the cluster of the other endpoint of eC . Let EC be the event that C is red and C ′ is blue. We have Pr[EC ] = 1/4. Let M ∗ be the set of edges eC such that EC happens, over all clusters C ∈ V. By construction, M ∗ is a (1, d)-component–node matching. Let X = |V| − |M ∗ |. By linearity of expectations, EX = 3|V|/4. By Markov inequality, we have 7|V| 7EX Pr X ≥ = Pr X ≥ ≤ 6/7. 8 6 Therefore, we have |V| |V| 7|V| 1 ∗ Pr |M | ≥ ≥ Pr |M | ≥ ≥ Pr X ≤ ≥ , 16 8 8 7 where the first inequality follows from the fact that |M | ≥ |M ∗ |/2, which is due to lemma 3.1.
4
Clustering
In this section, we discuss how we maintain a clustering V and introduce the basic subroutines related to clustering.
4.1
Metadata
In our algorithm, we maintain a clustering V of G = (V, E) together with auxiliary information that supports efficient communication inside clusters and controlled parallelism across clusters. Good labeling. A labeling L : V → {0, 1, . . . , n − 1} respects a clustering V if it satisfies the following properties: • For every cluster C ∈ V, there is exactly one node c(C) ∈ C with L(c(C)) = 0. We call c(C) the center of C. • For every cluster C ∈ V and every node v ∈ C with L(v) > 0, there exists a neighbor p(v) ∈ N (v) ∩ C with L(p(v)) = L(v) − 1. Following [CDH+ 18], we call such a labeling good. Intuitively, the parent pointers p(·) define a rooted spanning tree T (C) for each cluster C, rooted at c(C), of depth at most maxv∈C L(v). Cluster identifier, coloring, and shared randomness. For each cluster C ∈ V, its identifier is ID(C) = ID(c(C)). Each cluster is colored independently and uniformly at random; we write Color(C) ∈ {red, blue}, and require Color(C) to be known to all nodes in C. Finally, all nodes in C share a common random string r(C) of polylog n bits. For each node v ∈ C, define its basic information as I(v) = L(v), ID(C), Color(C), r(C) . Global parameters.
We write D ≤ n − 1 for a known upper bound on the maximum label: D ≥ max L(v). v∈V
12
4.2
Subroutines
We use the following subroutines throughout the paper, each implemented using the communication primitive Local-broadcast (Lemma 2.1) as a building block. As these subroutines are folklore or rely on standard techniques, we defer their implementations and proofs to Appendix A. In particular, the procedures Down-cast, Up-cast, and Merge are from [CDH+ 18]. For each subroutine, the set of participating clusters may be any subset of V. (1) Down-cast (Down-cast). • Input: For each cluster C, the center c(C) holds an O(log n)-bit message M (C). • Task: Deliver M (C) to all nodes of C. • Complexity: The cost is O((D + ∆) polylog n) rounds and O(polylog n) energy, with high probability. • Single-cluster complexity: If Down-cast is run on a single cluster C only, then the round complexity can be improved to O(D polylog n). (2) Up-cast (Up-cast). • Input: Some nodes in each cluster C may hold an O(log n)-bit message. • Goal: The center c(C) receives one arbitrary message originating from C if any exists; otherwise, c(C) learns that no message exists in C. • Complexity: The cost is O((D + ∆) polylog n) rounds and O(polylog n) energy, with high probability. • Single-cluster complexity: If Up-cast is run on a single cluster C only, then the round complexity can be improved to O(D polylog n). (3) Across-matching communication (Across-matching-comm). • Input: A (1, k)-component–node matching M is given. For each blue node v, the node v itself and all red nodes u with {u, v} ∈ M are provided with the following information: – ID(v). – A shared random string r(v) of length O(polylog n). In addition, all nodes know k and an upper bound M ≥ |M |. • Goal: For each edge e = {u, v} ∈ M , the endpoints u and v exchange O(polylog n) bits of information in both directions. • Complexity: The cost is O(M polylog n) rounds and O(k polylog n) energy, with high probability.
13
(4) Merge (Merge). • Input: A (1, k)-component–node matching M is given. For each blue node v, the node v itself and all red nodes u with {u, v} ∈ M are provided with the following information: – ID(v). – A shared random string r(v) of length O(polylog n). In addition, all nodes know k. • Goal: Construct a new clustering V ′ obtained by merging clusters according to the edges of M as follows. For each edge {u, v} ∈ M , let C(u) ∈ V and C(v) ∈ V denote the current clusters containing u and v, respectively. Define a graph H with node set V and edge set E(H) = {C(u), C(v)} : {u, v} ∈ M . Then V ′ is obtained by contracting each connected component of H into a single cluster, i.e., each new cluster is the union of all old clusters in one connected component of H, and clusters not incident to any edge of M remain unchanged. In addition, compute the required metadata for V ′ (good labeling, cluster identifiers, coloring, and shared randomness). • Complexity: The cost is O(n polylog n) rounds and O(k polylog n) energy, with high probability. (5) Approximate counting (Approx-count). • Input: Each node v holds a nonnegative integer xv such that
O(1) . v∈C xv ∈ n
P
P b • Goal: Each node in a cluster C learns an estimate X(C) of X(C) = v∈C xv such that b X(C) ≤ X(C) ≤ (1 + ϵ) X(C), i.e., the estimate never underestimates and overestimates by at most a factor (1 + ϵ). • Complexity: The cost is O(nϵ−3 polylog n) rounds and O(ϵ−3 polylog n) energy, with high probability. (6) Loneliness testing (Loneliness-test). • Goal: Determine whether V consists of exactly one cluster C = V , and ensure that all nodes learn the outcome. • Complexity: The cost is O(n polylog n) rounds and O(polylog n) energy, with high probability.
5
Main Algorithms
In this section, we prove Theorems 1 and 2. We need the following lemma, whose proof is deferred to Section 7. Lemma 5.1 (Matching algorithm). Given a clustering V, one can construct a d-almost-maximal (1, 2d)-component–node matching M in O(n polylog n) rounds and O(d polylog n) energy with high probability. Moreover, for every edge e = {u, v} ∈ M , the endpoints u and v exchange O(polylog n) bits of information. 14
5.1
Minimum-Degree Spanning Tree
Our main theorems are proved using a hierarchical clustering procedure, denoted Decomposition(d), which is defined as follows. We initialize the clustering V (1) to be the singleton clustering (i.e., each node forms its own cluster). For ℓ = 1, 2, . . ., we perform the following steps: 1. Compute a d-almost-maximal (1, 2d)-component–node matching M (ℓ) with respect to the current clustering V (ℓ) (and its random red/blue coloring). 2. Apply Merge to M (ℓ) to obtain the next clustering V (ℓ+1) . 3. If V (ℓ+1) consists of a single cluster, set t∗ = ℓ + 1 and terminate the process. Lemma 5.2 (Number of levels). If d ≥ ∆∗ , then t∗ ∈ O(log n) with high probability. Proof. Let Zℓ = |V (ℓ) | denote the number of clusters at the beginning of iteration ℓ. Conditioned on Zℓ > 1, Lemma 3.2 (which requires d ≥ ∆∗ ) implies that, with probability at least 1/7, the matching M (ℓ) has size at least Zℓ /16. Whenever this event occurs, the subsequent call to Merge reduces the number of clusters by |M (ℓ) |, since each edge of M (ℓ) connects two distinct clusters and merges them into one. Therefore, with probability at least 1/7, we have Zℓ+1 = Zℓ − |M (ℓ) | ≤ Zℓ −
Zℓ 15 = Zℓ . 16 16
In other words, in each iteration, with constant probability the number of clusters decreases by a constant factor. 15 We call iteration ℓ good if Zℓ+1 ≤ 16 Zℓ . By the above discussion, conditioned on Zℓ > 1, we have Pr[iteration ℓ is good] ≥ 1/7. By a Chernoff bound over t ∈ Θ(log n) iterations, with high probability the number of good iterations is at least Θ(log n). Since each good iteration multiplies the cluster count by at most 15/16, after Θ(log n) good iterations we obtain Zt = 1. Hence, t∗ ∈ O(log n) with high probability. Lemma 5.3 (Spanning tree). If t∗ ∈ O(log n), then the edge set F =
∗ −1 t[
M (ℓ)
ℓ=1
induces a spanning tree of maximum degree O(d log n). Proof. We first show that F induces a spanning tree. Throughout the process, we maintain the invariant that, for each cluster C, the edges added so far within C induce a spanning tree of C. Fix an iteration ℓ. Every edge in M (ℓ) connects two distinct clusters of V (ℓ) . Let H (ℓ) be the auxiliary graph whose nodes correspond to the clusters in V (ℓ) and whose edges correspond to the edges of M (ℓ) . Since M (ℓ) is a (1, 2d)-component–node matching, the graph H (ℓ) is a disjoint union of stars. Consequently, for each connected component of H (ℓ) containing r clusters, the corresponding r − 1 edges of M (ℓ) merge the spanning trees of these r clusters into a single spanning tree and cannot create a cycle. Thus, adding all edges of M (ℓ) preserves the invariant, exactly as in Borůvka’s algorithm. Starting from n singleton clusters and terminating when a single cluster remains, the union F =
∗ −1 t[
ℓ=1
15
M (ℓ)
is therefore a spanning tree of G. We now bound the maximum degree of F . Fix any iteration ℓ and any node v ∈ V . By definition of a (1, 2d)-component–node matching, in M (ℓ) each blue node has degree at most 2d, and each red node has degree at most 1. Thus, in any iteration, a node gains at most 2d incident edges. Since t∗ ∈ O(log n), we have degF (v) =
∗ −1 tX
degM (ℓ) (v) ≤ 2d (t∗ − 1) ∈ O(d log n),
ℓ=1
which completes the proof. We are now ready to prove Theorem 2. Proof of Theorem 2. We do not know ∆∗ a priori, so we construct Decomposition(d) for geometrically increasing values d ∈ {1, 2, 4, 8, . . .}. However, if d < ∆∗ , there is no guarantee that t∗ ∈ O(log n). Therefore, during the construction of Decomposition(d), we invoke Loneliness-test to ∗ check whether the clustering V (t ) consists of a single cluster within O(log n) iterations. If so, we St∗ −1 output the edge set F = ℓ=1 M (ℓ) and terminate. By Lemma 5.2, any d ≥ ∆∗ is guaranteed to pass this test, and hence the smallest value of d that passes satisfies d < 2∆∗ . By Lemma 5.3, the output is a spanning tree whose maximum degree is O(∆∗ log n). It remains to analyze the complexity. The construction of Decomposition(d) consists of O(log n) iterations. Each iteration invokes the matching algorithm of Lemma 5.1 once and the subroutine Merge once, and the construction concludes with a call to Loneliness-test. By Lemma 5.1, the matching algorithm requires O(n polylog n) rounds and O(d polylog n) ⊆ O(∆∗ polylog n) energy. Both Merge and Loneliness-test require O(n polylog n) rounds and O(polylog n) energy. Therefore, the algorithm computes a spanning tree T with ∆(T ) ∈ O(∆∗ log n) in O(n polylog n) rounds using O(∆∗ polylog n) energy with high probability.
5.2
Aggregation Schedule
The proof of Theorem 2 can be extended to yield an aggregation schedule and thereby prove Theorem 1. In this subsection we focus on this extension. We assume that a hierarchical clustering H = Decomposition(d) has already been constructed for some d ≤ 2∆∗ , with t∗ ∈ O(log n) levels. From the proof of Theorem 2, we know that such a hierarchy can be computed in O(n polylog n) rounds and O(∆∗ polylog n) energy with high probability. Hierarchical view of the decomposition. We regard H as a rooted tree whose nodes are ∗ clusters. The unique cluster in V (t ) is the root, and the clusters in V (1) are the leaves. For each level ℓ ∈ {2, . . . , t∗ } and each cluster C ∈ V (ℓ) that is formed by merging clusters from V (ℓ−1) , we say that C is the parent of those lower-level clusters. If the same cluster C appears in multiple levels, we still treat it as a single node in the tree H. For each ℓ > 1, recall that V (ℓ) is obtained by merging clusters in V (ℓ−1) along the matching (ℓ−1) M . In particular, if C ∈ V (ℓ) is formed by merging children C0 , C1 , . . . , Cs ∈ V (ℓ−1) , then the edges of M (ℓ−1) between these children form a star: exactly one child C0 is blue, the remaining children are red, and the matching edges connect each red child to C0 . 16
Our aggregation schedule uses coarse size estimates that are both locally known and monotone along the hierarchy. We obtain these estimates using the approximate counting primitive Approx-count. d Lemma 5.4 (Size approximation). We can compute a size estimate size(C) for every cluster C in H in O(n polylog n) rounds and O(polylog n) energy with high probability such that the following properties hold. d • For every cluster C, the estimate satisfies |C| ≤ size(C) ≤ 2|C|. d d ′ ) over all children C ′ • For every cluster C, the estimate size(C) is at least the sum of size(C of C in H. d • For every cluster C, all nodes in C know the value size(C). Proof. We prove a slightly stronger invariant. There exists a fixed ϵ ∈ Θ(1/ log n) such that for every level ℓ ∈ {1, . . . , t∗ } and every cluster C ∈ V (ℓ) we have d |C| ≤ size(C) ≤ (1 + ϵ)ℓ−1 |C|.
(1)
∗
Since t∗ ∈ O(log n), we can choose ϵ small enough so that (1 + ϵ)t −1 ≤ 2, which implies the desired 2-approximation for all clusters. Base level. At level ℓ = 1, every cluster C ∈ V (1) consists of a single node. Each such cluster d sets size(C) = 1. Then (1) holds with equality. Inductive step. Assume that (1) holds for all clusters in V (ℓ−1) for some ℓ ≥ 2. We now define the estimates for clusters in V (ℓ) . We run a single invocation of Approx-count with parameter ϵ on the clustering V (ℓ) as follows. Each node v chooses an integer input ( d ′ ) if v is the center of some cluster C ′ ∈ V (ℓ−1) , size(C xv = 0 otherwise. For every cluster C ∈ V (ℓ) , define X(C) =
X
xv .
v∈C
P d ′ ). If C is formed at level ℓ by merging children C1′ , . . . , Cq′ ∈ V (ℓ−1) , then X(C) equals qj=1 size(C j b By the guarantee of Approx-count, each node in C learns an estimate X(C) satisfying b X(C) ≤ X(C) ≤ (1 + ϵ) X(C). d If a cluster C ∈ V (ℓ) already appears in V (ℓ−1) , we keep its existing estimate size(C). Otherwise, C is newly formed at level ℓ, and we set b d size(C) = X(C).
17
Monotonicity along children. Consider a cluster C that is newly formed at level ℓ by merging children C1′ , . . . , Cq′ . By definition, X(C) =
q X
d j′ ), size(C
j=1
and hence b d size(C) = X(C) ≥ X(C) =
q X
d j′ ). size(C
j=1
This proves the second item of the lemma. Lower bound. therefore
d ′ ) for each child C ′ , and Using the induction hypothesis, we have |Cj′ | ≤ size(C j j |C| =
q X
|Cj′ |
j=1
Upper bound.
≤
q X
b d j′ ) = X(C) ≤ X(C) d size(C = size(C).
j=1
Again by the induction hypothesis, we have d j′ ) ≤ (1 + ϵ)ℓ−2 |Cj′ | size(C
Thus X(C) =
q X
d j′ ) ≤ (1 + ϵ)ℓ−2 size(C
j=1
q X
for all j.
|Cj′ | = (1 + ϵ)ℓ−2 |C|.
j=1
Consequently, b d size(C) = X(C) ≤ (1 + ϵ) X(C) ≤ (1 + ϵ)ℓ−1 |C|, which establishes (1) at level ℓ. Complexity. We invoke Approx-count once per level, for O(log n) levels, with parameter ϵ ∈ Θ(1/ log n). By the complexity of Approx-count, each invocation takes O(n poly(1/ϵ) polylog n) = O(n polylog n) rounds and O(poly(1/ϵ) polylog n) = O(polylog n) energy per node, with high probability. Summing over all levels gives a total of O(n polylog n) rounds and O(polylog n) energy with high probability. Recursive aggregation along the hierarchy. We now describe the conceptual structure of the aggregation procedure on H. Fix a level ℓ > 1 and a cluster C ∈ V (ℓ) formed by merging children C0 , C1 , . . . , Cs ∈ V (ℓ−1) , where C0 is the unique blue child and C1 , . . . , Cs are red. As noted earlier, the edges of M (ℓ−1) between these children form a star centered at C0 . For each such cluster C, we perform the following four steps. 1. We run the recursive aggregation schedules inside the red children C1 , . . . , Cs so that each Ci computes the aggregate value f (Ci ) of all inputs in Ci . 2. We use Across-matching-comm on the matching edges of M (ℓ−1) between {C1 , . . . , Cs } and C0 to send each value f (Ci ) to some node in C0 . 3. We run the recursive aggregation schedule for C0 , combining the received values {f (Ci )}si=1 with the local inputs of nodes in C0 using the operator ⋄, and obtain f (C). 18
4. We run a Down-cast within C so that all nodes in C learn the value f (C). Executing this construction bottom-up along H ensures that the root cluster eventually obtains f (V ) and that the final aggregate is disseminated to all nodes. Random delays and congestion. In Step 1 above, the aggregation schedules inside the red children C1 , . . . , Cs can be carried out either in parallel or sequentially. However, a naive parallel execution would cause excessive contention in the radio network; in particular, a naive use of random delays at every level could introduce an additional polylogarithmic blow-up per level. On the other hand, a fully sequential ordering of the schedules of all clusters is also not a viable option: in a radio network, computing such a global ordering in a distributed fashion becomes non-trivial when there are many clusters. To control both the contention and the total length of the schedule, we therefore introduce a slightly more abstract notion of aggregation schedules in which time is partitioned into slots and congestion is measured per slot. This slot-based view allows us to analyze random delays uniformly across all levels of H and later convert the resulting randomized slot-based schedule into a standard round-based schedule with only a polylogarithmic overhead. Slot-based aggregation schedules. To reason about random delays without committing to a specific round-by-round execution, we use a slightly abstracted notion of aggregation schedules. A slot-based aggregation schedule is a finite sequence of slots S = (S1 , S2 , . . . , St ), where t = |S| is the length of the schedule. Each slot Si consists of a finite collection of message transmission events. In a given message transmission event, each node chooses one of three actions: listening, transmitting, or staying idle. We assume that each message transmission event has a unique O(log n)-bit identifier that is known to all nodes that participate in that event as listeners or transmitters. The semantics of the schedule are as follows. Consider any total ordering of all message transmission events that respects the slot order, in the sense that all events in Si occur before all events in Sj whenever i < j. The requirement is that, for every such ordering, if the radio network executes the events in that order, then by the end of the process the correct global aggregate value f (V ) is obtained (and, in our final construction, known to all nodes). The congestion of the schedule S is defined as max |Si |, i∈{1,...,t}
i.e., the maximum number of message transmission events contained in any slot. Randomized slot-based schedules. We also consider a randomized variant of the above notion. A randomized slot-based aggregation schedule still has a fixed length t, but the assignment of message transmission events to slots is performed randomly, using shared randomness available in the network. More precisely, the set of all message transmission events is determined in advance, and the schedule is specified by a random mapping that sends each event to one of the slots S1 , . . . , St . The correctness requirement is worst-case over the randomness: for every realization of the random mapping, and for every ordering of the message transmission events that respects the resulting slot order, executing the events in that order must produce the correct aggregate. The randomness only affects the congestion profile of the schedule. In our construction we will design randomized slot-based schedules in such a way that, for each slot, the congestion is distributed like a random variable from a recursively defined class with good concentration properties. 19
The class Zd of random variables. For each integer d ≥ 0, we define a class Zd of nonnegative integer-valued random variables. Intuitively, variables in Zd are built in at most d layers from simpler pieces and will model the congestion contributed to a single slot after combining randomness across several levels of the hierarchy. Base layer (d = 0).
A random variable Z belongs to Z0 if Z ∈ {0, 1}
and Z is deterministic. Recursive layer (d ≥ 1). A random variable Z belongs to Zd if it can be obtained from independent random variables X1 , . . . , Xk ∈ Zd−1 , for some k ≥ 1, using one of the following two constructions, and satisfies E[Z] ≤ 1. 1. Parallel sum: Z=
k X
Xi .
i=1
2. Random selection: Z = XJ , where J is a random index in {1, . . . , k}, and J is independent of (X1 , . . . , Xk ). In the random selection construction, the index J does not need to be uniformly distributed over {1, . . . , k}. The two constructions are chosen to reflect how congestion builds up in our randomized slot-based schedules. We write [ Z = Zd . d∈{0,1,2,...}
By definition, every Z ∈ Z satisfies E[Z] ≤ 1. Lemma 5.5 (Concentration bound for Zd ). For any Z ∈ Z, we have Z ∈ O(log n) with high probability. P Proof. We can represent Z as a sum Z = j Yj of {0, 1}-valued leaf indicators arising from P the underlying sum/selection tree. The family {Yj } is negatively associated, and µ := E[Z] = E[ j Yj ] ≤ 1 by assumption. By a Chernoff bound for negatively associated Bernoulli variables [PS97; DR98], for all δ > 0, δ2 µ
Pr[Z ≥ (1 + δ)µ] ≤ e− 2+δ , which matches the independent case. Thus Pr[Z ≥ t] ≤ e−Ω(t) for all t ≥ 0, and in particular Pr[Z ≥ c log n] ∈ n−Ω(c) . Hence Z ∈ O(log n) with high probability. By Lemma 5.5, if the congestion in each slot of a randomized slot-based aggregation schedule of polynomial length is distributed as a random variable in Z, then with high probability the congestion of every slot is O(log n). This will allow us later to convert such schedules into standard round-based schedules while incurring only a polylogarithmic overhead.
20
Lemma 5.6 (Slot-based schedules → standard schedules). Let S = (S1 , S2 , . . . , St ) be any slotbased aggregation schedule with t ∈ nO(1) such that the congestion is at most O(log n), and each node participates in at most E message transmission events. There is an O(n polylog n)-round and O(polylog n)-energy procedure that transforms S into a standard aggregation schedule S ⋆ that uses O(t log2 n) rounds and O(E log n) energy with high probability. Proof. Let κ ∈ Θ(log n) be an upper bound on the congestion of S, i.e., every slot Si contains at most κ message transmission events. For each slot Si , we create R ∈ Θ(κ log n) consecutive rounds, which we view as a block associated with Si . For each message transmission event e in Si , and for each of the R rounds in the block of Si , we independently decide that e joins that round with probability p ∈ Θ(1/κ) and otherwise e is inactive in that round. In any round, all events that join that round are executed simultaneously. If a round ends up containing exactly one event e, then the transmission pattern prescribed by e is realized without interference from other events in the same slot. The resulting collection of rounds, over all slots, defines a standard round-based schedule S ⋆ . Analysis. We now analyze the properties of S ⋆ . Fix a slot Si and an event e ∈ Si . The number of rounds in which e joins is distributed as Binomial(R, p), with expectation E[#joins of e] = Rp ∈ Θ(κ log n) · Θ(1/κ) = Θ(log n). By a Chernoff bound, for a suitable choice of constants in R and p, with probability at least 1 − n−Θ(1) we have that e joins in Θ(log n) rounds. Taking a union bound over all events, at most tκ ∈ nO(1) in total, with high probability every event joins in O(log n) rounds. Next, we show that every event e has at least one round in which it is the unique joining event among the at most κ events in its slot. In any fixed round of the block for Si , the probability that e joins while all other events in Si do not join is p(1 − p)m−1 , where m ≤ κ is the number of events in Si . For p ∈ Θ(1/κ) and m ≤ κ, this probability is Θ(1/κ). Therefore, the probability that e does not have a round in which it is the only joining event among the R ∈ Θ(κ log n) rounds in the block is at most (1 − Θ(1/κ))Θ(κ log n) ∈ n−Θ(1) . Again, by a union bound over all events, with high probability every event e has at least one round in which it is the only joining event in its slot and hence is successfully executed. Thus, once we fix a choice of randomness for the allocation, the resulting schedule S ⋆ is a valid standard aggregation schedule: every message transmission event from S is realized at least once without intra-slot interference. The total number of rounds used by S ⋆ is t · R ∈ t · Θ(κ log n) = Θ(t log2 n). Moreover, since each event is active in O(log n) rounds with high probability, and each node participates in at most E events, each node is awake in at most O(E log n) rounds during the execution of S ⋆ . 21
Construction. It remains to argue that we can implement the random allocation of events to rounds using only O(n polylog n) rounds and O(polylog n) energy. For this, it suffices to provide all nodes with a succinct description of a hash function that, given the identifier of an event e and a round index within its slot block, determines whether e joins that round. We let the center of the root cluster of the hierarchical clustering H locally sample the description of a κ-wise independent hash function h : U × [R] → {0, 1}, where U is the universe of message-transmission-event identifiers. The hash function is chosen so that Pr[h(e, j) = 1] = p for each event e and each round index j ∈ [R]. Such a hash family has a description of length Θ(polylog n) bits. The center then disseminates this description to all nodes using Down-cast, which costs O(n polylog n) rounds and O(polylog n) energy. After this dissemination, every node can locally determine, for every event it participates in and every round index in the corresponding block, whether that event joins that round by evaluating h. This completes the construction of S ⋆ within the claimed time and energy bounds. We briefly explain a key idea behind the proof of the following lemma. Adding random delays to child schedules incurs an additive overhead proportional to the maximum child schedule length. If we did this for all children at every level, this could cause a constant-factor blow-up per level and make the overall schedule too long. To control this, we split the children of each cluster into large and small ones. The schedules for the large children are run sequentially without random delays, while random delays are used only for the small children, whose schedules are guaranteed to be much shorter than that of the parent. This way, the per-level overhead from random delays stays a small fraction of the parent schedule length. Lemma 5.7 (Constructing randomized slot-based schedules). We can compute a randomized slotbased aggregation schedule in O(n polylog n) rounds using O(∆∗ polylog n) energy with high probability such that the following conditions are met. • The length of the schedule is O(n polylog n). • Each node participates in O(∆∗ polylog n) message transmission events. • For each slot, the congestion is a random variable in Z. Proof. As in the proof of Theorem 2, we construct a hierarchical clustering H = Decomposition(d) for some d ≤ 2∆∗ with t∗ ∈ O(log n) levels in O(n polylog n) rounds using O(∆∗ polylog n) energy with high probability. d We then apply the algorithm of Lemma 5.4 to compute a size estimate size(C) for every cluster C in H in O(n polylog n) rounds and O(polylog n) energy with high probability. For ease of notation, write T (n, d) ∈ O(n polylog n) and E(n, d) ∈ O(d polylog n) for the round and energy upper bounds of running both single-cluster Down-cast and Across-matching-comm with D = n, M = n, and the matching M for Across-matching-comm is a (1, d)-component–node matching. We assume that T (·, d) is superadditive, that is, T (x, d) + T (y, d) ≤ T (x + y, d) for all x, y.
22
Recursive randomized schedules for clusters. We define, by induction on the level ℓ, for every cluster C ∈ V (ℓ) a randomized slot-based aggregation schedule SC with the following properties: d • The length of SC is at most 2ℓ · T (size(C), d). d • Each node participates in at most ℓ · E(size(C), d) message transmission events. • For each slot of SC , the congestion is a random variable in Z. For the root cluster at level t∗ ∈ O(log n), we obtain the desired schedule. Base case. For ℓ = 1, each cluster consists of a single node. We let SC be the empty schedule. All three properties hold trivially. Inductive step. Assume ℓ > 1, and let C ∈ V (ℓ) be a cluster at level ℓ. Let C0 , C1 , . . . , Cs denote its children, where C0 is the unique blue child and C1 , . . . , Cs are red. Recall that C is formed by connecting the children into a star with center in C0 . We construct SC in four steps. Step 1: Aggregation in the red children. We first apply the schedules SCi for all red children C1 , . . . , C s . Fix a sufficiently large constant α > 0 and declare a red child Ci to be large if d i) ≥ size(C
1 d · size(C), α log n
d and small otherwise. Since the children are disjoint and their size estimates sum to at most size(C), there are at most O(log n) large children. We treat large and small children differently. Large red children. For each large child Ci , we run its schedule SCi sequentially, one after another, in any fixed order. The slots of SCi are kept intact and are reinterpreted as slots of SC in contiguous segments dedicated to the large children. By the induction hypothesis, every slot of SCi has congestion in Z, so the same holds for these slots once they are placed into SC by a deterministic reindexing. Small red children and random delays. After all large children have finished, we schedule the small children in parallel with random delays. By the induction hypothesis, d i ), d) |SCi | ≤ 2(ℓ − 1) · T (size(C for every child Ci . For a small child Ci we have d i) ≤ size(C
1 d · size(C), α log n
and hence, using monotonicity of T (·, d), |SCi | ≤ 2(ℓ − 1) · T
1 d · size(C), d . α log n
23
Define Lthresh (C, ℓ) := 2(ℓ − 1) T
1 d · size(C), d . α log n
Then |SCi | ≤ Lthresh (C, ℓ) for every small child Ci . Next, use the induction hypothesis and superadditivity of T to bound the total length of all child schedules: s X i=0
|SCi | ≤ 2(ℓ − 1)
s X
d i ), d) ≤ 2(ℓ − 1) T (size(C), d T (size(C d).
i=0
Let the large red children be indexed by a set L and the small children by a set S. Define X d |SCi |. Y := 2(ℓ − 1) T (size(C), d) − |SC0 | − i∈L
Then X
|SCi | ≤ Y,
i∈S
and Y ≥ 0. If S is empty we omit the random-delay block entirely. For the small children, we create a dedicated block of slots of length B(C, ℓ) := Y + Lthresh (C, ℓ) in SC . For each small child Ci ∈ S, independently choose a delay τi ∈ {0, 1, . . . , Y − 1} uniformly at random, and shift the entire schedule SCi by τi slots. Since |SCi | ≤ Lthresh (C, ℓ) for every small Ci , the shifted schedule of each small child fits entirely inside this block. The random delays τi are the only new source of randomness at level ℓ. Step 2: Across-matching communication. We transmit the aggregated results from all red children to the star center in C0 by running Across-matching-comm with matching M equal to d M (ℓ−1) restricted to edges between C1 , . . . , Cs and C0 . Clearly, |M | ≤ size(C), so we realize this d with M = size(C). Step 3: Aggregation in the center. We continue the aggregation inside C0 as follows. Each node v ∈ C0 that receives aggregated values from red children first locally combines them with its own input f (v) using the operator ⋄. We then run the schedule SC0 inside C0 . By the induction hypothesis, SC0 is a slot-based schedule in which each slot has congestion in Z. The resulting value at the designated output node of C0 is the aggregate f (C). Step 4: Disseminating the final result. Finally, we disseminate f (C) to all nodes in C by a d d Down-cast with parameters D = size(C) and ∆ = size(C).
24
Length and number of events per node. We now bound the length of SC and the number of message transmission events per node. For Steps 2 and 4, the Across-matching-comm and Down-cast together cost d T (size(C), d) rounds, and each node participates in at most d E(size(C), d) message transmission events. We view each of these rounds as one slot of SC . For Steps 1 and 3, the child schedules SC0 , SC1 , . . . , SCs together contribute s X
d |SCi | ≤ 2(ℓ − 1) T (size(C), d),
i=0
and the small children use an additional block of length B(C, ℓ) = Y + Lthresh (C, ℓ). By the definition of Y , X d |SC0 | + |SCi | + Y = 2(ℓ − 1) T (size(C), d), i∈L
so Steps 1 and 3 together use at most d 2(ℓ − 1) T (size(C), d) + Lthresh (C, ℓ) slots. As ℓ ∈ O(log n), by choosing the constant α sufficiently large, we can ensure that d Lthresh (C, ℓ) ≤ T (size(C), d) for all clusters C and levels ℓ. Hence Steps 1 and 3 use at most d (2ℓ − 1) T (size(C), d) slots, and including Steps 2 and 4 we obtain d length of SC ≤ 2ℓ · T (size(C), d). Since C0 , . . . , Cs are disjoint, the induction hypothesis implies that, across all child schedules, each node participates in at most d (ℓ − 1) · E(size(C), d) events during Steps 1 and 3. Adding the contribution from Steps 2 and 4, we get the desired bound d events per node ≤ ℓ · E(size(C), d). Congestion and membership in Z. We next verify that the congestion in every slot of SC is a random variable in Z. Since Steps 1–4 are executed sequentially in time, each slot of SC belongs to exactly one of these steps, and we can analyze them one by one. Slots from Step 2 and Step 4: In Across-matching-comm and Down-cast, for the purpose of defining SC , we fix an arbitrary realization of their internal randomness. Then every slot arising 25
from Step 2 or Step 4 has deterministically bounded congestion (say, congestion 0 or 1). Such a slot congestion is a deterministic {0, 1}-valued variable, and hence belongs to Z. Slots from Step 3: Slots belonging to Step 3 correspond exactly to the slots of SC0 , reindexed in a deterministic way. By the induction hypothesis, each slot of SC0 has congestion in Z. Therefore, the congestion of each slot of SC coming from Step 3 is also in Z. Slots for large red children in Step 1: For each large child Ci , we run SCi in its own contiguous segment. Again by the induction hypothesis, every slot of SCi has congestion in Z. Since we only reindex these slots deterministically when embedding them into SC , their congestion distributions remain in Z. Slots for small red children in Step 1: Fix any slot σ in the random-delay block for small children. For a given small child Ci , let Xi,1 , Xi,2 , . . . , Xi,|SC | i
denote the congestion random variables in the slots of SCi in their original local order. By the induction hypothesis, each Xi,j is in Z, and in particular E[Xi,j ] ≤ 1. After the random delay τi is chosen, either no slot from SCi is aligned with σ, or exactly one of the slots from SCi is aligned with σ. Thus the contribution of Ci to the congestion in σ is a random variable Yi that is either 0 or equal to one of the Xi,j . We can view this as follows: consider the multiset {0, Xi,1 , Xi,2 , . . . , Xi,|SC | }, i
where 0 is interpreted as a deterministic element of Z. The random delay τi induces a random index Ji into this multiset, and Yi = Xi,Ji , with the convention Xi,0 = 0. By the random selection rule in the definition of Z, Yi ∈ Z provided that E[Yi ] ≤ 1. For each local slot j of SCi , there is at most one value of τi that maps this slot to σ, and τi is uniform in {0, . . . , Y − 1}. Therefore, each Xi,j is mapped to σ with probability at most 1/Y , and |SC |
1 Xi |SCi | E[Yi ] ≤ . E[Xi,j ] ≤ Y Y j=1
P Since |SCi | ≤ h∈S |SCh | ≤ Y , we obtain E[Yi ] ≤ 1 and hence Yi ∈ Z. The total congestion in slot σ coming from small children is X Zsmall := Yi . i∈S
The random variables Yi are independent across i, because they depend on the independent delays τi and on independent randomness used in the lower-level schedules SCi . Each Yi belongs to Z, and P X X |SC | i∈S |SCi | i E[Zsmall ] ≤ E[Yi ] ≤ ≤ ≤ 1. Y Y i∈S
i∈S
By the parallel sum rule in the definition of Z, this implies Zsmall ∈ Z. We have now covered all slots: each slot of SC belongs to exactly one of the four steps, and in each case its congestion is a random variable in Z, with expectation at most 1. This completes the inductive construction of the schedules SC . 26
Construction cost and fixing randomness. It remains to argue that all the schedules SC can be constructed in O(n polylog n) rounds using O(∆∗ polylog n) energy. The additional work, beyond building H and computing size estimates, consists of identifying the large children of each cluster and assigning them disjoint time intervals, and choosing and disseminating the random delays for small children. Since each cluster C has only O(log n) large children, we can identify them using O(log n) iterations of Up-cast and Down-cast inside C. The center of each child Ci can locally decide whether d i ) with size(C). d Ci is large by comparing size(C In each iteration, centers of large children that are d i )). The center not yet assigned a time interval participate in an Up-cast, sending (ID(Ci ), size(C c(C) selects one such child and assigns it an interval, then disseminates this via a Down-cast inside C. After O(log n) iterations, all large children are assigned disjoint intervals. Each small child Ci then locally samples its delay τi and uses a Down-cast inside Ci to inform all nodes of this choice. These procedures can be run in parallel for all clusters in the same level. Processing the levels from t∗ down to 2 therefore costs O(n polylog n) rounds and O(polylog n) energy. Finally, we must fix the randomness of all Across-matching-comm and Down-cast executions and ensure that each message transmission event has a unique O(log n)-bit identifier known to all participating nodes. As in the proof of Lemma 5.6, we can define the identifier of an event using the round number of the underlying execution together with the cluster identifier ID(C). The subtlety is that, without actually running the protocols, nodes do not know in advance which rounds they will participate in. To resolve this, we execute the slot-based schedule once, thereby fixing the randomness of all Across-matching-comm and Down-cast executions in the construction and letting each node learn exactly which rounds it participates in, so that the corresponding event identifiers can be assigned consistently. This execution can be implemented using the transformation procedure of Lemma 5.6: the procedure only requires that, immediately before each slot is run, all nodes that must transmit or listen in that slot are aware of this fact, which is guaranteed by our construction. The additional round and energy costs incurred by this execution are again bounded by Lemma 5.6, namely O(n polylog n) rounds and O(∆∗ polylog n) energy. Putting everything together, we obtain a randomized slot-based aggregation schedule S with the claimed bounds on length, number of message transmission events per node, and slot congestion. Proof of Theorem 1. We first run the algorithm of Lemma 5.7 to compute a randomized slot-based schedule S in O(n polylog n) rounds using O(∆∗ polylog n) energy with high probability. By Lemma 5.5, for every random variable Z ∈ Z we have Z ∈ O(log n) with high probability. In particular, for each slot of S, the number of message transmission events is O(log n) with high probability. We then apply Lemma 5.6 to transform the slot-based schedule S into a standard round-based aggregation schedule. Since S has length O(n polylog n) and congestion O(log n) per slot with high probability, Lemma 5.6 yields a standard aggregation schedule that uses O(n polylog n) rounds and O(polylog n) energy with high probability.
6
Slow Matching Algorithm
In this section, we establish the following result. 27
Lemma 6.1 (Slow matching algorithm). Given a clustering V, one can construct a d-almostmaximal (1, d)-component–node matching M in O(nd polylog n) rounds and O(d polylog n) energy with high probability. Moreover, for every edge e = {u, v} ∈ M , the endpoints u and v exchange O(polylog n) bits of information. The algorithm of Lemma 6.1 is slow in the sense that its round complexity has an additional linear dependence on d compared to Lemma 5.1. Since any (1, d)-component–node matching is also a (1, 2d)-component–node matching, Lemma 6.1 already implies Lemma 5.1 in the case where d ∈ O(polylog n). Our goal is to construct a d-almost-maximal (1, d)-component–node matching M . Initially, we set M = ∅. A blue node is active if its degree in M is smaller than d. A red cluster is active if its degree in M is zero. A red node is active if it belongs to an active red cluster. Let Gactive denote the bipartite subgraph of G induced by all edges between active blue nodes and active red nodes. Observation 6.2 (d-almost-maximality). If the maximum degree of Gactive is zero and degM (C) ≤ 1 for every red cluster C, then M is d-almost-maximal. Proof. We verify the two defining conditions of a d-almost-maximal matching. • If degM (C) = 0 for a red cluster C, then every blue node u adjacent to C satisfies degM (u) ≥ d. • If degM (v) < d for a blue node v, then every red cluster C adjacent to v satisfies degM (C) = 1. Consider a red cluster C with degM (C) = 0. Then C is active, and no node in C has an active blue neighbor in Gactive . Hence, every blue node adjacent to C must satisfy degM (u) ≥ d, establishing the first condition. Next, consider a blue node v with degM (v) < d. Then v is active and has no active red neighbor in Gactive . Therefore, every red cluster adjacent to v must satisfy degM (C) = 1, establishing the second condition.
6.1
The Matching Subroutine
The basic building block of our algorithm is the procedure match(k), parameterized by an integer k ≥ 1. The procedure is executed on the current active subgraph Gactive and consists of a matching phase followed by an unmatching phase. Matching phase: The following steps are repeated for k iterations. 1 • Each node samples itself independently with probability 10k .
• Add an edge e = {u, v} to the matching if all of the following conditions hold: 1. u is a sampled red node; 2. v is a sampled blue node; 3. no other blue neighbor of u is sampled; 4. no other red neighbor of v is sampled. • Once a blue node is matched, it does not participate in the remaining iterations of the matching phase. Unmatching phase: For each red cluster C, if more than one edge incident to C has been added to the matching, then C keeps exactly one such edge. 28
Lemma 6.3 (Implementation of match(k)). The procedure match(k) can be implemented in O((n+ k) polylog n) rounds and O(polylog n) energy with high probability. Moreover, for every edge e = {u, v} added to the matching, the endpoints u and v exchange O(polylog n) bits of information. Proof. Each iteration of the matching phase is implemented using a three-round handshake. • In the first round, each sampled blue node v transmits ID(v), while each sampled red node u listens. • In the second round, each sampled red node u that receives a message in the first round transmits ID(u), while each sampled blue node v listens. If v receives ID(u), then v knows that {u, v} is added to the matching. • In the third round, each sampled blue node v that receives a message in the second round transmits ID(v) again, while each sampled red node u that receives a message in the first round listens. If u receives ID(v), then u knows that {u, v} is added to the matching. To allow the endpoints of each matched edge to exchange O(polylog n) bits of information, each round can be replaced by O(polylog n) rounds. Thus, the matching phase costs O(k polylog n) rounds. Each node is sampled in at most O(log n) iterations with high probability by a Chernoff bound, implying O(polylog n) energy consumption. For the unmatching phase, we perform an Up-cast within each red cluster to its cluster center, which selects one incident edge if any exist, followed by a Down-cast to disseminate the decision. This costs O(n polylog n) rounds and O(polylog n) energy with high probability. Finally, to notify blue nodes of unmatched edges, we repeat the matching phase using the same randomness, allowing red endpoints to communicate the unmatching decisions.
6.2
Degree Reduction Framework
The algorithm for Lemma 6.1 is based on a degree reduction framework. Lemma 6.4 (Degree reduction). Suppose the maximum degree of the current Gactive is at most k. Then running match(k) for O(d log n) iterations reduces the maximum degree of Gactive to at most k/2 with high probability. We first show how to derive Lemma 6.1 from Lemma 6.3 and Lemma 6.4. Proof of Lemma 6.1. We initialize M = ∅. For k = n, n/2, n/4, . . ., we run match(k) for O(d log n) iterations, stopping once k < 1. By Lemma 6.4, at termination, Gactive has maximum degree zero. By Observation 6.2, the resulting matching M is d-almost-maximal. Throughout the algorithm, we maintain degM (v) ≤ d for every blue node v and degM (C) ≤ 1 for every red cluster C, so M is a (1, d)-component–node matching. Moreover, the required information exchange occurs during the execution of the matching phase in which each edge is added. There are O(log n) values of k, and for each we execute match(k) for O(d log n) iterations. By Lemma 6.3, each execution costs O(n polylog n) rounds and O(polylog n) energy. Thus, the overall round and energy complexities are O(nd polylog n) and O(d polylog n), respectively.
29
6.3
Analysis
We now prove Lemma 6.4. For this purpose, we consider the following quantity of a red cluster C: 1 X degGactive (u). 100k u∈C
Intuitively, this quantity estimates the expected number of matched edges incident to C during one 1 P 1 execution of match(k). A red cluster is called small if 100k u∈C degGactive (u) ≤ 10000 ; otherwise, it is large. We clarify that since Gactive changes across iterations, a cluster that is currently large may become small after a few iterations. Observation 6.5 (Small → degGactive (u) ≤ k/2). If a red cluster C is small, then every node u ∈ C has degree at most k/2 in Gactive . Proof. Since 1 X 1 , degGactive (u) ≤ 100k 10000 u∈C
we have degGactive (u) ≤
100k k k = < 10000 100 2
for every u ∈ C. Structure of the analysis. Throughout, assume that the maximum degree of Gactive is at most k. The analysis proceeds in two parts. In Part 1, we show that after O(log n) executions of match(k), all active red clusters become small or inactive with high probability. In Part 2, assuming all active red clusters are small, we show that further O(d log n) executions of match(k) reduce the degrees of active blue nodes to at most k/2 with high probability. Lemma 6.6 (Part 1). Suppose the maximum degree of Gactive is at most k. There exists a constant c1 > 0 such that for every red cluster C that is active and large at the beginning of an execution of match(k), with probability at least c1 , cluster C becomes inactive or small by the end of match(k). Proof. Fix an active red cluster C that is large at the beginning of an execution of match(k). Let EC be the set of edges in the current Gactive with exactly one endpoint in C, so that X |EC | = degGactive (u). u∈C
Since C is large, we have |EC | >
k . 100
(2)
Restricting to a bounded-weight subset of edges. We will show that in a single iteration of the matching phase, cluster C gains an incident matched edge with probability Ω(1/k), and then amplify this over the k independent iterations of match(k). To obtain the Ω(1/k) bound we use a second-moment argument for a sum of indicator variables. For this purpose, it is convenient to ensure that the relevant expectation is bounded by a constant. If we sum over all edges in EC , the expectation may exceed 1, as |EC | can be large. We therefore restrict attention to a subset of edges whose size is only Θ(k), which already suffices to witness that C is large. Formally, choose any subset F ⊆ EC with k 101 k < |F | ≤ +k ≤ k, (3) 100 100 100 which exists by (2). 30
Random variables for one iteration. Consider one fixed iteration of the matching phase. Let 1 p := 10k . For each edge e = {u, v} ∈ F , let Xe be the indicator variable of the event that e is added to the matching in this iteration, i.e., 1. u and v are both sampled, and 2. no other neighbor of u or v is sampled. P Let X := e∈F Xe . Whenever X ≥ 1, cluster C gains an incident matched edge in this iteration. First moment.
Fix e = {u, v} ∈ F . Since Gactive has maximum degree at most k, Pr[Xe = 1] = p2 · (1 − p)(deg(u)−1)+(deg(v)−1) ≥ p2 · (1 − p)2k−2 .
1 2k−2 Using (1 − 10k ) ≥ e−1/5 for all k ≥ 1, we obtain
Pr[Xe = 1] ≥
e−1/5 . 100k 2
(4)
e−1/5 1 e−1/5 > · , 2 100k 104 k
(5)
Let µ := E[X]. Then µ=
X
Pr[Xe = 1] ≥ |F | ·
e∈F
where the strict inequality uses |F | > k/100. Moreover, by (3) and (4), 101 1 2 1 k· < · < 1. 2 100 100k 100 k
µ ≤ |F | · p2 ≤ Second moment.
(6)
We bound E[X 2 ]. For two distinct edges e, f ∈ F :
• If e and f share an endpoint, then Pr[Xe = Xf = 1] = 0. • Otherwise, e and f are node-disjoint, and thus Pr[Xe = Xf = 1] ≤ p4 (since all four endpoints must be sampled). Hence, E[X 2 ] =
X
E[Xe ] +
e∈F
X
E[Xe Xf ] ≤ µ + |F |2 · p4 = µ +
e,f ∈F e̸=f
|F |2 . 104 k 4
Using (5), we have µ ≥ |F | · e−1/5 /(100k 2 ), i.e., |F | ≤ 100e1/5 µ. k2 Plugging this into (7) gives E[X 2 ] ≤ µ +
(100e1/5 µ)2 = µ + e2/5 µ2 < (1 + e2/5 )µ, 104
where the last inequality uses µ < 1 from (6). 31
(7)
A success in one iteration.
By the second-moment bound Pr[X ≥ 1] ≥ E[X]2 /E[X 2 ],
Pr[X ≥ 1] ≥
c′ µ2 µ ≥ = , k (1 + e2/5 )µ 1 + e2/5
for a constant c′ > 0 by (5). Over k iterations. The k iterations of the matching phase use independent randomness. Let q ≥ c′ /k be the lower bound on the probability that C gains an incident matched edge in a fixed iteration. Then ′
Pr[C gains no incident matched edge during the matching phase] ≤ (1 − q)k ≤ e−qk ≤ e−c . ′
Thus, with probability at least 1 − e−c , cluster C gains at least one incident edge by the end of the matching phase. In the subsequent unmatching phase, cluster C keeps exactly one incident edge if it has more than one. Therefore, whenever C gains at least one edge in the matching phase, it ends match(k) ′ with degM (C) = 1 and hence is inactive. This establishes the lemma with c1 := 1 − e−c . Lemma 6.7 (Part 2). Suppose the maximum degree of Gactive is at most k, and all active red clusters are small. There exists a constant c2 > 0 such that for every active blue node v with degGactive (v) ≥ k/2 at the beginning of match(k), with probability at least c2 , node v gains a new incident edge in the matching by the end of match(k). Proof. Fix an active blue node v with degGactive (v) ≥ k/2 at the beginning of match(k), and let 1 p := 10k . Focusing on one active iteration for v. Let Ev be the event that v is sampled in exactly one of the k iterations of the matching phase. Then Pr[Ev ] = k · p · (1 − p)k−1 1 1 k−1 ≥ 1− 10 10k 1 1 9 ≥ 1− = =: c0 , 10 10 100 where c0 > 0 is a constant. Condition on Ev . Under this conditioning, there is a unique iteration, which we call the v-iteration, in which v is sampled; in all other iterations v is not sampled and hence cannot be matched. We show that, conditioned on Ev , with constant probability v gets matched in the v-iteration and the corresponding edge survives the unmatching phase. Partitioning neighbors by clusters. Let Cv be the set of active red clusters adjacent to v at the beginning of match(k). For each C ∈ Cv , let xC be the number of neighbors of v in C. Since degGactive (v) ≥ k/2, X k xC ≥ . (8) 2 C∈Cv
Fix a cluster C ∈ Cv . Let R(C) ⊆ C be the set of relevant nodes in C, defined as R(C) := {w ∈ C : degGactive (w) > 0}. 32
Observe that |R(C)| ≤ |E(C)|, where E(C) is the set of edges in Gactive with exactly one endpoint in C. We define the event FC in the v-iteration as follows: 1. Exactly one neighbor u ∈ C of v is sampled. 2. No other red neighbor of v is sampled. 3. No other blue neighbor of u is sampled. 4. u is the only sampled node in R(C). If FC occurs, then {u, v} is added to the matching in the v-iteration, and moreover C cannot gain any additional matched edge in the same iteration. Lower bounding Pr[FC | Ev ]. Conditioned on Ev , there is a unique iteration in which v is sampled. In that iteration, the sampling decisions of all nodes other than v remain independent and each node is sampled with probability p. Fix C ∈ Cv . Recall that FC is the event that in the v-iteration there exists a unique neighbor u ∈ C of v that is sampled, no other red neighbor of v is sampled, no other blue neighbor of u is sampled, and u is the only sampled node in R(C) := {w ∈ C : degGactive (w) > 0}. There are xC choices for u. Fix one such u. The event FC requires: (i) u is sampled (probability p); (ii) all other red neighbors of v are not sampled (at most k − 1 nodes); (iii) all other blue neighbors of u are not sampled; since C is small, Observation 6.5 implies degGactive (u) ≤ k/2, so there are at most k/2 − 1 such P nodes; and (iv) all nodes in R(C) \ {u} are not sampled. Since C is small, we have |E(C)| = w∈C degGactive (w) ≤ k/100, and hence |R(C)| ≤ |E(C)| ≤ k/100, so |R(C) \ {u}| ≤ k/100 − 1. By independence, k
k
Pr[FC | Ev ] ≥ xC · p · (1 − p)(k−1)+( 2 −1)+( 100 −1) 3k
k
≥ xC · p · (1 − p) 2 + 100 .
(9)
k 1 and m = 3k Finally, using (1 − p)m ≥ 1 − mp for mp ≤ 1 and substituting p = 10k 2 + 100 , we obtain 3k k k 1 3 1 849 3k + (1 − p) 2 100 ≥ 1 − + =1− + = . 2 100 10k 20 1000 1000 1 Combining with (9) and p = 10k gives
Pr[FC | Ev ] ≥ xC ·
1 849 xC · =: c4 · , 10k 1000 k
849 where c4 := 10000 is a constant.
Node v gets matched in the v-iteration with constant probability. The events {FC }C∈Cv are mutually exclusive: each requires that all red neighbors of v outside C are not sampled, hence two different clusters cannot simultaneously satisfy the requirement that a neighbor in that cluster is sampled. Thus, X Pr[v is matched in the v-iteration | Ev ] ≥ Pr[FC | Ev ] C∈Cv
≥ c4 ·
c4 1 X xC ≥ =: c3 , k 2 C∈Cv
where we used (8). Hence c3 > 0 is a constant. 33
The matched edge survives the unmatching phase. Fix C ∈ Cv and condition on FC , so that {u, v} is added to the matching in the v-iteration with u ∈ C. By the extra requirement in FC that u is the only sampled node in R(C), cluster C cannot gain any additional matched edge in the same v-iteration. Thus, {u, v} can be removed in the unmatching phase only if C gains at least one additional incident matched edge in some other iteration. Since |E(C)| ≤ k/100, in any fixed iteration t ̸= the v-iteration, Pr[C gains an incident matched edge in iteration t] ≤
1 . 104 k
By a union bound over the remaining k − 1 iterations, Pr[C gains an incident matched edge in some iteration t ̸= v-iteration] ≤ 10−4 . Therefore, conditioned on FC , with probability at least 1 − 10−4 , cluster C has no other incident matched edges, and hence the edge {u, v} survives the unmatching phase. Conclusion. Conditioned on Ev , the probability that v is matched in the v-iteration and the edge survives unmatching is at least c3 − 10−4 . Unconditioning on Ev yields Pr[v gains a new incident edge by the end of match(k)] ≥ Pr[Ev ]·(c3 −10−4 ) ≥ c0 ·(c3 −10−4 ) =: c2 , where c2 > 0 is a constant. We now prove Lemma 6.4 by combining Lemma 6.6 and Lemma 6.7. Proof of Lemma 6.4. Assume that the maximum degree of Gactive is at most k. By Lemma 6.6 and a Chernoff bound, after O(log n) executions of match(k), all active red clusters are small with high probability. By Observation 6.5, this implies that every active red node u satisfies degGactive (u) ≤ k/2. Next, consider any active blue node v with degGactive (v) ≥ k/2. As long as v remains active and has degree at least k/2, Lemma 6.7 guarantees that each execution of match(k) adds a new incident edge to v in the matching with constant probability. By a Chernoff bound, over O(log n) executions, with high probability, v gains a new incident matching edges unless it becomes inactive earlier. Since v can receive at most d incident edges in the matching before it becomes inactive, it follows that after O(d log n) executions of match(k), with high probability, every blue node that is still active must satisfy degGactive (v) ≤ k/2.
7
Fast Matching Algorithm
In this section, we establish the following result. Lemma 7.1 (Fast matching algorithm). Suppose d ∈ ω(log2 n). Given a clustering V, one can construct a d-almost-maximal (1, 2d)-component–node matching M in O(n polylog n) rounds and O(d polylog n) energy with high probability. Moreover, for every edge e = {u, v} ∈ M , the endpoints u and v exchange O(polylog n) bits of information. Compared with the algorithm of Lemma 6.1, the algorithm of Lemma 7.1 eliminates the linear dependence on d in the round complexity. This improvement comes at the cost of requiring d ∈ ω(log2 n). Together with Lemma 6.1, this immediately implies Lemma 5.1. 34
Proof of Lemma 5.1. The proof follows by combining Lemma 6.1 and Lemma 7.1. If d ∈ O(log2 n), we run the algorithm of Lemma 6.1; otherwise, we run the algorithm of Lemma 7.1. Our goal is to construct a d-almost-maximal (1, 2d)-component–node matching M . As in the proof of Lemma 6.1, we initialize M = ∅ and use the same definitions of active nodes and the active subgraph Gactive . In particular, Observation 6.2 continues to hold.
7.1
The Matching Subroutine
The basic building block of our algorithm is the procedure match(d′ , k), which is parameterized by two integers d′ and k satisfying 1 ≤ d′ < k (and hence k ≥ 2). The procedure is executed on the current active subgraph Gactive . Similar to the subroutine match(k) used in the algorithm of Lemma 6.1, the procedure match(d′ , k) consists of a matching phase followed by an unmatching phase. Matching phase: The following steps are repeated for k iterations. • Each blue node v samples itself independently with probability k1 . ′
• Each red node u samples itself independently with probability dk . • If a sampled red node u has exactly one sampled blue neighbor v, add the edge {u, v} to the matching. Unmatching phase: For each red cluster C, if more than one edge incident to C has been added to the matching, then C keeps exactly one such edge. We now discuss the selection of the parameters k and d′ and briefly compare match(d′ , k) with the subroutine match(k) used in Lemma 6.1. In both cases, the parameter k serves as an upper bound on the maximum degree of Gactive . The parameter d′ is chosen to satisfy d′ ∈ Θ(d/ log n) ⊆ ω(log n) so that the following claim holds. Claim 7.2 (Selection of d′ ). Suppose the maximum degree of Gactive is at most k. There exists a choice of d′ ∈ Θ(d/ log n) such that, with high probability, every blue node gains at most 0.01 · d matched edges during the matching phase of match(d′ , k). Since d + 0.01 · d < 2d and our goal is a (1, 2d)-component–node matching, unlike in match(k), we do not need a mechanism that prevents a matched blue node from continuing to participate in the subsequent iterations during the matching phase of match(d′ , k). Proof. By a Chernoff bound, each blue node v is sampled in at most s ∈ O(log n) iterations with high probability. In each iteration in which v is sampled, among its at most k red neighbors, the ′ expected number of sampled nodes is k · dk = d′ ∈ ω(log n). Another Chernoff bound implies that this number is at most 2d′ with high probability. Therefore, during the matching phase of match(d′ , k), node v gains at most s · 2d′ ∈ O(d′ log n) matched edges with high probability. Choosing d′ ∈ Θ(d/ log n) ensures that this quantity is at most 0.01 · d. We now describe the implementation of match(d′ , k), assuming that k is an upper bound on the maximum degree of Gactive and that d′ ∈ Θ(d/ log n). Lemma 7.3 (Implementation of match(d′ , k)). The procedure match(d′ , k) can be implemented in O(n polylog n) rounds and O(d polylog n) energy with high probability. Moreover, for every edge e = {u, v} added to the matching, the endpoints u and v exchange O(polylog n) bits of information. 35
Proof. To implement a single iteration of the matching phase, each sampled blue node v transmits ID(v) and some random string r(v) of O(polylog n) bits using O(polylog n) rounds in parallel, while each sampled red node u listens. The transmitted information is needed for running Across-matching-comm later. If a listening red node u receives a message, then it must come from its unique sampled blue neighbor v. In this case, node u learns that the edge {u, v} is added to the matching and also obtains I(v). At this point, however, the blue node v is not yet aware that {u, v} has been added. Over all k iterations, this implementation costs O(k polylog n) ⊆ O(n polylog n) rounds and O(d polylog n) energy with high probability. The energy bound follows from the fact that, by a Chernoff bound, each blue node is sampled in O(log n) iterations with high probability, and each red node is sampled in O(d′ ) = O(d/ log n) iterations. Next, to implement the unmatching phase, we follow the same approach as in the proof of Lemma 6.3. Specifically, we perform an Up-cast followed by a Down-cast within each red cluster to select one incident edge in the matching, if any exist. This step costs O(n polylog n) rounds and O(polylog n) energy with high probability. To inform the blue endpoints of the matched edges and to allow the endpoints of each such edge to exchange O(polylog n) bits of information, we run Across-matching-comm over these edges with M = n. By Claim 7.2, these edges induce a (1, 0.01 · d)-component–node matching, so this step costs O(n polylog n) rounds and O(d polylog n) energy with high probability. We emphasize that, because each matched edge exchanges O(polylog n) bits of information, Lemma 7.3 implicitly guarantees that every blue node v learns its set of incident edges in M . In particular, node v knows degM (v) and can therefore determine whether it is active or inactive.
7.2
Degree Reduction Framework
As in the proof of Lemma 6.1, the algorithm underlying Lemma 7.1 is based on a degree-reduction framework. Lemma 7.4 (Degree reduction). Suppose the maximum degree of the current Gactive is at most k. Then running match(d′ , k) for O(log2 n) iterations reduces the maximum degree of Gactive to at most k/2 with high probability. A limitation of the procedure match(d′ , k) is that it requires k ≥ d′ . Consequently, once the maximum degree of the current Gactive drops below d′ , we switch to a different approach. Specifically, when this occurs, we invoke the algorithm guaranteed by the following lemma with parameter s = d′ . Lemma 7.5 (Small degree). Suppose the maximum degree of the current Gactive is at most s. Then a (1, s)-component–node matching M ′ of Gactive such that degM ′ (C) = 1 for every active red cluster C with degGactive (C) > 0 can be computed using O(n polylog n) rounds and O(s polylog n) energy with high probability. Moreover, for every edge e = {u, v} ∈ M ′ , the endpoints u and v exchange O(polylog n) bits of information. Proof. We run Local-broadcast for O(polylog n) iterations using the same randomness, where every active blue node v transmits and every active red node u listens. Using the same randomness guarantees that each listening node u receives messages from the same transmitting node v across all O(polylog n) iterations. These iterations allow each transmitter v to send both ID(v) and some random string r(v) of O(polylog n) bits, which are needed for running Across-matching-comm later. If a red node u receives a message from a blue node v, then we add the edge {u, v} to the matching. This step costs O(polylog n) rounds and energy. By the guarantee of Local-broadcast, 36
for every active red cluster C with degGactive (C) > 0, at least one edge incident to C is added to the matching. The remainder of the proof follows the same structure as that of Lemma 7.3. We first perform an Up-cast followed by a Down-cast within each red cluster to select exactly one incident edge in the matching, if any exist. The remaining edge set M ′ satisfies the requirement degM ′ (C) = 1 for every active red cluster C with degGactive (C) > 0. This step costs O(n polylog n) rounds and O(polylog n) energy with high probability. Finally, to inform the blue endpoints of the matched edges and to allow the endpoints of each such edge to exchange O(polylog n) bits of information, we run Across-matching-comm over these edges. Since the maximum degree of Gactive is at most s, the resulting edges form a (1, s)component–node matching. Consequently, this step costs O(n polylog n) rounds and O(s polylog n) energy with high probability. We now show how to derive Lemma 7.1 from Lemmas 7.3 to 7.5. Proof of Lemma 7.1. The algorithm proceeds as follows. 1. Initialize M = ∅. 2. For k = n, n/2, n/4, . . ., run match(d′ , k) for O(log2 n) iterations, stopping once k ≤ d′ . 3. Compute a (1, d′ )-component–node matching M ′ such that degM ′ (C) = 1 for every active red cluster C with degGactive (C) > 0 using Lemma 7.5. 4. Return M ∪ M ′ . By Lemma 7.5, we have degM ′ (C) = 1 for every active red cluster C with degGactive (C) > 0. Therefore, when treating M ∪ M ′ as the current matching, all such red clusters become inactive, and the maximum degree of Gactive becomes zero. By Observation 6.2, this implies that M ∪ M ′ is d-almost-maximal. We next verify that M ∪ M ′ is a (1, 2d)-component–node matching. By the description of match(d′ , k) and Claim 7.2, throughout the execution we maintain degM (v) ≤ d + 0.01d < 2d for every blue node v and degM (C) ≤ 1 for every red cluster C. Since only active nodes participate in the construction of M ′ , we further maintain degM ∪M ′ (v) ≤ d + max{0.01d, d′ } = 1.01d < 2d for every blue node v, while still ensuring degM ∪M ′ (C) ≤ 1 for every red cluster C. Thus, M ∪ M ′ is a (1, 2d)-component–node matching. Moreover, the required information exchange occurs either during the matching phase in which edges are added or during the construction of M ′ . There are O(log n) values of k, and for each we execute match(d′ , k) for O(log2 n) iterations. By Lemma 7.3, each execution costs O(n polylog n) rounds and O(d polylog n) energy. By Lemma 7.5, the construction of M ′ also costs O(n polylog n) rounds and O(d polylog n) energy. Hence, the claimed round and energy complexities follow.
7.3
Analysis
We now prove Lemma 7.4. Similar to the proof of Lemma 6.4, we consider the following quantity of a red cluster C: d′ X degGactive (u). k u∈C
37
Intuitively, this quantity estimates the expected number ofP matched edges incident to C during one d′ 1 execution of match(k). A red cluster is called small if k u∈C degGactive (u) ≤ 100 ; otherwise, it is large. Observation 7.6 (Small → degGactive (u) ≤ k/2). If a red cluster C is small, then every node u ∈ C has degree at most k/2 in Gactive . Proof. Since
d′ X 1 degGactive (u) ≤ , k 100 u∈C
we have degGactive (u) ≤
k k ≤ ′ 100d 2
for every u ∈ C. Structure of the analysis. Throughout, assume that the maximum degree of Gactive is at most k. Similar to the proof of Lemma 6.4, the analysis proceeds in two parts. In Part 1, we show that after O(log n) executions of match(k), all active red clusters become small or inactive with high probability. In Part 2, assuming all active red clusters are small, we show that further O(log2 n) executions of match(k) reduce the degrees of active blue nodes to at most k/2 with high probability. Lemma 7.7 (Part 1). Suppose the maximum degree of Gactive is at most k. There exists a constant p0 > 0 such that for every red cluster C that is active and large at the beginning of an execution of match(d′ , k), with probability at least p0 , cluster C becomes inactive or small by the end of match(k). Proof. Fix an active red cluster C that is large at the beginning of an execution of match(d′ , k). Let X S := degGactive (u), u∈C
i.e., the number of edges of Gactive with exactly one endpoint in C. By the definition of largeness, d′ 1 ·S > k 100
=⇒
S >
k . 100 d′
(10)
Easy case. We first consider the case in which C contains a node of very high degree in Gactive . Suppose there is a node u⋆ ∈ C with du⋆ := degGactive (u⋆ ) ≥
k . 100d′
Then, in any fixed iteration of the matching phase, the probability that u⋆ is sampled and has exactly one sampled blue neighbor is at least d′ du⋆ d′ du⋆ 1 du⋆ −1 e−1 · · 1− ≥ e−1 · 2 ≥ , k k k k 100k where we used (1 − k1 )du⋆ −1 ≥ (1 − k1 )k−1 ≥ e−1 .
k −1 e−1 Hence over the k independent iterations, with probability at least 1− 1 − 100k ≥ 1−e−e /100 , some edge incident to u⋆ is added during the matching phase. In this case, after the unmatching phase, C keeps one such edge and becomes inactive. Thus the lemma follows in this case. 38
Restricting to a bounded-weight subset. u ∈ C satisfies
It remains to consider the case in which every node
k . 100d′ We first explain the structure of the argument. Our goal is to show that in a single iteration of the matching phase, cluster C gains an incident matched edge with probability Ω(1/k). The k iterations of match(d′ , k) then amplify this probability to a constant. To prove the single-iteration bound, we use a second-moment argument on the number of matched edges incident to C. For this purpose, it is convenient to work with a collection of indicator variables whose total expectation is bounded by a constant. If we consider all nodes of C, this expectation could be larger than 1, which would complicate the analysis. We therefore restrict attention to a carefully chosen subset of nodes whose total degree already witnesses that C is large, while keeping the aggregate expectation under control. Formally, order the positive-degree nodes of C arbitrarily and let U ⊆ C be the minimum prefix such that X k degGactive (u) ≥ SU := . (11) 100 d′ degGactive (u) <
u∈U
k Such a set exists by (10). Moreover, since every node in the present case has degree less than 100d ′, the minimality of U implies k k k SU < + = . (12) ′ ′ 100 d 100 d 50 d′ Since all nodes in U have positive degree, we also have
|U | ≤ SU .
(13)
Random variables for one iteration. Fix one iteration t of the matching phase. In this iteration, each blue node is sampled independently with probability pB := 1/k, and each red node is sampled independently with probability pR := d′ /k. For each red node u ∈ U , let Yu be the indicator variable of the event that 1. u is sampled, and 2. among the degGactive (u) blue neighbors of u in Gactive , exactly one is sampled in this iteration. If Yu = 1, then the unique sampled blue neighbor v forms an edge {u, v} that is added to the matching in iteration t. Let X X := Yu . u∈U
Whenever X ≥ 1, cluster C gains an incident matched edge in iteration t. First moment. Fix u ∈ U and write du := degGactive (u) ≤ k. Conditioned on u being sampled, the number of sampled blue neighbors of u is distributed as Binomial(du , pB ). Therefore, Pr[Yu = 1] = pR · Pr Binomial(du , pB ) = 1 = pR · du · pB (1 − pB )du −1 d′ du 1 k−1 d′ du ≥ · · 1− ≥ e−1 · 2 , k k k k where we used (1 − k1 )k−1 ≥ e−1 . 39
(14)
Let µ := E[X]. Summing (14) over u ∈ U gives µ=
X
Pr[Yu = 1] ≥ e−1 ·
u∈U
e−1 1 d′ · S ≥ · , U k2 100 k
(15)
using (11). On the other hand, by (12), µ ≤
X
pR · du · pB =
u∈U
d′ 1 · SU < < 1. k2 50k
Second moment. For distinct u, w ∈ U , the event {Yu = Yw = 1} requires that both u and w are sampled and that each has exactly one sampled blue neighbor. A necessary condition for this event to occur is the following: first, both u and w are sampled, which happens with probability ′ 2 d ; second, among the blue neighbors of u in Gactive , at least one is sampled, which happens k with probability at most dku by a union bound. Therefore, ′ 2 d du Pr[Yu = Yw = 1] ≤ · . k k Therefore, E[X 2 ] =
X u∈U
≤µ+
X
E[Yu ] +
E[Yu Yw ]
u,w∈U u̸=w
d′2 X du k3 u,w∈U u̸=w
≤µ+
d′2 |U | SU . k3
Using (12) and (13), we obtain E[X 2 ] ≤ µ +
1 1 d′2 2 SU ≤ µ + 2 · . 3 k 50 k
By (15), we have k1 ≤ 100eµ. Consequently, E[X 2 ] ≤ µ + A success in one iteration.
1 e · 100eµ = 1 + µ ≤ 2µ. 502 25
By the second-moment bound, Pr[X ≥ 1] ≥
E[X]2 µ e−1 ≥ ≥ . E[X 2 ] 2 200k
Thus, setting c := e−1 /200, we have Pr[X ≥ 1] ≥ c/k.
40
Over all k iterations.
The k iterations of the matching phase are independent. Hence,
Pr[C gains no incident matched edge during the matching phase] ≤ (1 − kc )k ≤ e−c . Thus, with probability at least 1 − e−c , cluster C gains at least one incident matched edge during the matching phase. In the unmatching phase, cluster C keeps exactly one such edge whenever it has at least one, so C ends match(d′ , k) with degM (C) = 1 and becomes inactive. Setting p0 := 1 − e−c completes the proof. Lemma 7.8 (Part 2). Suppose the maximum degree of Gactive is at most k, and all active red clusters are small. For every active blue node v with degGactive (v) ≥ k/2 at the beginning of match(d′ , k), node v gains Ω(d′ ) incident edges in the matching in expectation by the end of match(d′ , k). Proof. Fix an active blue node v with degGactive (v) ≥ k/2 at the beginning of an execution of match(d′ , k). We prove that after the entire procedure (including the unmatching phase), node v gains Ω(d′ ) incident edges in expectation. Let Cv be the set of active red clusters adjacent to v at the beginning of this execution. For each C ∈ Cv , let xC := |{u ∈ C : {u, v} ∈ E(Gactive )}| be the number of neighbors of v inside C. Clearly, X k xC = degGactive (v) ≥ . 2
(16)
C∈Cv
For each cluster C, define the set of relevant red nodes R(C) := {u ∈ C : degGactive (u) > 0}. Since all active red clusters are small, we have d′ X 1 degGactive (u) ≤ =⇒ k 100 u∈C
X
degGactive (u) ≤
u∈C
k . 100d′
In particular, |R(C)| ≤
X
degGactive (u) ≤
u∈C
k . 100d′
(17)
A per-cluster success event that survives unmatching. Fix a cluster C ∈ Cv . For each iteration t ∈ {1, 2, . . . , k} of the matching phase, define the event FC,t that the following all hold in iteration t: 1. v is sampled; 2. exactly one neighbor u ∈ C of v is sampled; 3. u is the only sampled node in R(C); 4. among the blue neighbors of u, the only sampled one is v. If FC,t occurs, then the edge {u, v} is added to the matching in iteration t, and moreover no other red node in C can add an edge in the same iteration (because u is the only sampled node in R(C)). Let HC,t be the event that in every iteration t′ ̸= t, cluster C adds no edge to the matching (during the matching phase). Then, if FC,t ∩ HC,t occurs, cluster C has exactly one incident matched edge in the entire matching phase, namely {u, v}, and hence {u, v} necessarily survives the unmatching phase. In other words, under FC,t ∩ HC,t , cluster C contributes a surviving edge incident to v. 41
Lower bounding Pr[FC,t ]. Let pB := 1/k and pR := d′ /k be the sampling probabilities of blue and red nodes. There are xC choices for the unique sampled neighbor u ∈ C of v. Fix such a node u. Independence implies Pr[FC,t ] ≥ pB · xC · pR · (1 − pR )|R(C)|−1 · (1 − pB )degGactive (u)−1 .
(18)
By Observation 7.6, degGactive (u) ≤ k/2, so (1 − pB )degGactive (u)−1 ≥ (1 − k1 )k/2 ≥ e−1 , where the last inequality holds for any k ≥ 2. Moreover, using (17) we have (|R(C)| − 1) · pR ≤ |R(C)| ·
d′ 1 ≤ , k 100
1 99 and hence (1 − pR )|R(C)|−1 ≥ 1 − 100 ≥ 100 . Plugging these bounds into (18) yields
Pr[FC,t ] ≥
1 d′ 99 xC d′ · xC · · · e−1 ≥ c0 · 2 , k k 100 k
(19)
for a constant c0 > 0. Bounding the probability of additional edges from C. It remains to lower bound Pr[HC,t ]. Fix an iteration t′ ̸= t. Let WC,t′ be the number of edges added to the matching in iteration t′ that are incident to cluster C. By Markov’s inequality, Pr[WC,t′ ≥ 1] ≤ E[WC,t′ ]. We upper bound E[WC,t′ ] by summing over all edges with a red endpoint in C. Fix such an edge {u, w} with u ∈ C. The edge can be added only if u is sampled and w is the unique sampled blue neighbor of u, so d′ Pr[{u, w} is added in iteration t′ ] ≤ pR · pB = 2 . k Summing over all edges with exactly one endpoint in C gives d′ k 1 d′ X degGactive (u) ≤ 2 · = . E[WC,t′ ] ≤ 2 k k 100d′ 100k u∈C
1 , and by a union bound over the k − 1 iterations t′ ̸= t, Therefore, Pr[WC,t′ ≥ 1] ≤ 100k
Pr[HC,t ] = Pr[∀t′ ̸= t, WC,t′ = 0] ≥ 1 −
X t′ ̸=t
Pr[WC,t′ ≥ 1] ≥ 1 −
k−1 99 ≥ . 100k 100
(20)
A surviving edge from C with probability Ω(xC d′ /k). Since FC,t depends only on iteration t and HC,t depends only on the other iterations, the two events are independent. Thus, by (19) and (20), 99 xC d′ Pr[FC,t ∩ HC,t ] = Pr[FC,t ] Pr[HC,t ] ≥ · c0 · 2 . 100 k Let GC be the event that cluster C contributes a surviving edge incident to v after the unmatching phase. Since the events {FC,t ∩ HC,t }kt=1 are mutually exclusive (because HC,t forces C to add no edges in all other iterations), we have Pr[GC ] ≥
k X
Pr[FC,t ∩ HC,t ] ≥ k ·
t=1
for a constant c1 > 0. 42
99 xC d′ xC d′ · c0 · 2 = c1 · , 100 k k
Summing over clusters. Let Z be the number of edges incident to v that survive the unmatching ′ phase at the P end of match(d , k). Since each red cluster keeps at most one incident edge, we can write Z = C∈Cv ZC , where ZC ∈ {0, 1} indicates whether C keeps an edge incident to v. Hence, E[Z] =
X
E[ZC ] =
C∈Cv
X C∈Cv
Pr[GC ] ≥
X C∈Cv
c1 ·
xC d′ d′ X d′ k = c1 · xC ≥ c1 · · = Ω(d′ ), k k k 2 C∈Cv
where we used (16) in the last inequality. This proves the lemma. We now prove Lemma 7.4 by combining Lemma 7.7 and Lemma 7.8. Proof of Lemma 7.4. The proof follows the same high-level structure as that of Lemma 6.4. Assume throughout that the maximum degree of the current active subgraph Gactive is at most k. By Lemma 7.7 and a Chernoff bound, after O(log n) executions of match(d′ , k), all active red clusters become small or inactive with high probability. By Observation 7.6, this implies that every active red node u satisfies degGactive (u) ≤ k/2. Next, consider any active blue node v with degGactive (v) ≥ k/2. As long as v remains active and has degree at least k/2, Lemma 7.8 guarantees that each execution of match(d′ , k) adds Ω(d′ ) = Ω(d/ log n) new incident edges to v in expectation. By Claim 7.2, with high probability, the number of new edges added to v in any single execution is at most 0.01d. Consequently, by Markov’s inequality, in each execution of match(d′ , k), with probability Ω(1/ log n), node v gains Ω(d/ log n) new incident edges. We call such an execution good for v. By a Chernoff bound, over C log2 n executions of match(d′ , k), with probability at least 1 − −Ω(C) n , the number of good executions is Ω(C log n). This implies that, unless v becomes inactive or its degree in Gactive drops below k/2 earlier, node v gains Ω(Cd) incident edges in total. Since v can receive at most d incident edges in the matching before it becomes inactive, choosing C to be a sufficiently large constant ensures that after O(log2 n) executions of match(d′ , k), with high probability, every blue node that remains active satisfies degGactive (v) ≤ k/2.
8
Conclusions
In this paper, we present a randomized distributed algorithm that constructs and executes an aggregation schedule in O(n polylog n) rounds and O(∆∗ polylog n) energy. The energy complexity is nearly universally optimal : for every graph and every aggregation schedule, there exists a node that must remain awake for at least ∆∗ rounds. As a by-product, our algorithm also computes an O(log n)-approximate minimum-degree spanning tree while achieving the same round and energy guarantees. A natural direction for future work is to improve the round complexity. Our current O(n polylog n) bound is only nearly existentially optimal : for some graphs, such as star graphs, we have ∆∗ ∈ Ω(n), implying that Ω(n) rounds are unavoidable, even for graphs with diameter two. However, for many other graph families, it may be possible to solve the aggregation problem in o(n) rounds. This raises an intriguing question: can one achieve near universal optimality not only in energy complexity, but also in round complexity? Another natural direction is to study different notions of energy consumption, such as the nodeaverage energy complexity. Although ∆∗ gives a universal lower bound on the worst-case node energy, there exist aggregation schedules with only O(1) node-average energy complexity. Can one design a distributed algorithm whose node-average energy complexity nearly matches this bound? 43
References [AMC07]
Ian F Akyildiz, Tommaso Melodia, and Kaushik R Chowdhury. A survey on wireless multimedia sensor networks. Computer networks, 51(4):921–960, 2007.
[AMP24]
John Augustine, William K Moses Jr, and Gopal Pandurangan. Awake complexity of distributed minimum spanning tree. In International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 45–63. Springer, 2024.
[BB03]
Lélia Blin and Franck Butelle. The first approximated distributed algorithm for the minimum degree spanning tree problem on general graphs. Proceedings International Parallel and Distributed Processing Symposium, 2003. doi: 10.1109/IPDPS.2003. 1213299.
[BFW26]
Sayan Bhattacharya, Ermiya Farokhnejad, and Haoze Wang. Additive one approximation for minimum degree spanning tree: breaking the O(mn) time barrier. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC), 2026.
[BGI92]
Reuven Bar-Yehuda, Oded Goldreich, and Alon Itai. On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization. Journal of Computer and System Sciences, 45(1):104–126, 1992.
[BKP+ 16]
Michael A Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young. Contention resolution with log-logstar channel accesses. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 499–508, 2016. doi: 10.1145/ 2897518.2897655.
[BM21]
Leonid Barenboim and Tzalik Maimon. Deterministic Logarithmic Completeness in the Distributed Sleeping Model. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing (DISC), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), 10:1–10:19, Dagstuhl, Germany. Schloss Dagstuhl – LeibnizZentrum für Informatik, 2021. isbn: 978-3-95977-210-5. doi: 10.4230/LIPIcs.DISC. 2021.10.
[BSL+ 04]
Jonathan Beaver, M Sharaf, Alexandros Labrinidis, and P Chrysanthis. Locationaware routing for data aggregation in sensor networks. Geosensor Networks:189–209, 2004.
[CD21]
Artur Czumaj and Peter Davies. Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. Journal of the ACM (JACM), 68(2):1–22, 2021.
[CDH+ 18]
Yi-Jun Chang, Varsha Dani, Thomas P Hayes, Qizheng He, Wenzheng Li, and Seth Pettie. The energy complexity of broadcast. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 95–104, 2018.
[CDH+ 20]
Yi-Jun Chang, Varsha Dani, Thomas P Hayes, and Seth Pettie. The energy complexity of BFS in radio networks. In Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC), pages 273–282. ACM, 2020. isbn: 9781450375825. doi: 10.1145/3382734.3405713.
[CGP20]
Soumyottam Chatterjee, Robert Gmyr, and Gopal Pandurangan. Sleeping is efficient: MIS in O(1)-rounds node-averaged awake complexity. In Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC), pages 99–108. ACM, 2020. doi: 10.1145/3382734.3405718. 44
[CHL+ 24]
Yi-Jun Chang, Oren Hecht, Dean Leitersdorf, and Philipp Schneider. Universally optimal information dissemination and shortest paths in the HYBRID distributed model. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC), pages 380–390, 2024.
[CK85]
Imrich Chlamtac and Shay Kutten. On broadcasting in radio networks-problem analysis and protocol design. IEEE Transactions on Communications, 33(12):1240–1246, 1985.
[CK87]
Chlamtac and Kutten. Tree-based broadcasting in multihop radio networks. IEEE Transactions on Computers, 100(10):1209–1223, 1987.
[CKP+ 19]
Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, and Wei Zhan. Exponential separations in the energy complexity of leader election. ACM Transactions on Algorithms, 15(4), 2019. doi: 10.1145/3341111.
[DGH+ 23]
Varsha Dani, Aayush Gupta, Thomas P Hayes, and Seth Pettie. Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks. Distributed Computing, 36(3):373–384, 2023.
[DH22]
Varsha Dani and Thomas P Hayes. How to wake up your neighbors: safe and nearly optimal generic energy conservation in radio networks. In 36th International Symposium on Distributed Computing (DISC 2022), volume 246, 16:1–16:22. Schloss DagstuhlLeibniz-Zentrum für Informatik, 2022.
[DHI+ 19]
Michael Dinitz, Magnus M. Halldorsson, Taisuke Izumi, and Calvin Newport. Distributed minimum degree spanning trees. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pages 511–520, New York, NY, USA. Association for Computing Machinery, 2019. isbn: 9781450362177. doi: 10.1145/3293611.3331604. url: https://doi.org/10.1145/3293611.3331604.
[DMP23]
Fabien Dufoulon, William K Moses Jr, and Gopal Pandurangan. Distributed MIS in O(log log n) awake complexity. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, pages 135–145, 2023.
[DR98]
Devdatt P. Dubhashi and Desh Ranjan. Balls and bins: a study in negative dependence. Random Structures & Algorithms, 13(2):99–124, 1998.
[FR94]
Martin Furer and Balaji Raghavachari. Approximating the minimum-degree steiner tree to within one of optimal. Journal of Algorithms, 17(3):409–423, 1994.
[GH16]
Mohsen Ghaffari and Bernhard Haeupler. Near-optimal bfs-tree construction in radio networks. IEEE Communications Letters, 20(6):1172–1174, 2016.
[GKP98]
Juan A. Garay, Shay Kutten, and David Peleg. A SubLinear time distributed algorithm for minimum-weight spanning trees. SIAM Journal on Computing, 27(1):302– 316, February 1998.
[GP22]
Mohsen Ghaffari and Julian Portmann. Average awake complexity of MIS and matching. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, pages 45–55, 2022.
[GP23]
Mohsen Ghaffari and Julian Portmann. Distributed MIS with low energy and time complexities. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, pages 146–156, 2023.
45
[GT24]
Mohsen Ghaffari and Anton Trygub. A near-optimal low-energy deterministic distributed SSSP with ramifications on congestion and APSP. In Proceedings of the 2024 ACM Symposium on Principles of Distributed Computing (PODC), 2024.
[HRG22]
Bernhard Haeupler, Harald Räcke, and Mohsen Ghaffari. Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1325–1338, 2022.
[HW16]
Bernhard Haeupler and David Wajc. A faster distributed radio broadcast primitive. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), pages 361–370. ACM, 2016.
[HWZ21]
Bernhard Haeupler, David Wajc, and Goran Zuzic. Universally-optimal distributed algorithms for known topologies. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1166–1179, New York, NY, USA. Association for Computing Machinery, 2021. isbn: 9781450380539. doi: 10 . 1145 / 3406325.3451081. url: https://doi.org/10.1145/3406325.3451081.
[IEG+ 02]
Chalermek Intanagonwiwat, Deborah Estrin, Ramesh Govindan, and John Heidemann. Impact of network density on data aggregation in wireless sensor networks. In Proceedings 22nd international conference on distributed computing systems (ICDCS), pages 457–458. IEEE, 2002.
[JKZ02]
Tomasz Jurdziński, Miroslaw Kutylowski, and Jan Zatopiański. Efficient algorithms for leader election in radio networks. In Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 51–57, 2002. doi: 10.1145/571825.571833.
[LMR07]
Christian Lavault, Jean-François Marckert, and Vlady Ravelomanana. Quasi-optimal energy-efficient leader election algorithms in radio networks. Information and Computation, 205(5):679–693, 2007.
[MFH+ 02]
Samuel Madden, Michael J Franklin, Joseph M Hellerstein, and Wei Hong. Tag: a tiny aggregation service for ad-hoc sensor networks. ACM SIGOPS Operating Systems Review, 36(SI):131–146, 2002.
[NO00]
Koji Nakano and Stephan Olariu. Randomized leader election protocols in radio networks with no collision detection. In International Symposium on Algorithms and Computation (ISAAC), pages 362–373. Springer, 2000.
[PS97]
Alessandro Panconesi and Aravind Srinivasan. Randomized distributed edge coloring via an extension of the chernoff–hoeffding bounds. SIAM Journal on Computing, 26(2):350–368, 1997.
[RGH+ 22]
Václav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, and Jason Li. Undirected (1+ϵ)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms. In Stefano Leonardi and Anupam Gupta, editors, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 478–487. ACM, 2022.
[SBY06]
Adam Silberstein, Rebecca Braynard, and Jun Yang. Constraint chaining: on energyefficient continuous monitoring in sensor networks. In Proceedings of the 2006 ACM SIGMOD international conference on Management of data, pages 157–168, 2006.
46
[TKW+ 12]
Yoshiaki Taniguchi, Akimitsu Kanzaki, Naoki Wakamiya, and Takahiro Hara. An energy-efficient data gathering mechanism using traveling wave and spatial interpolation for wireless sensor networks. Information and Media Technologies, 7(1):448–457, 2012.
[WX06]
Lan Wang and Yang Xiao. A survey of energy-efficient scheduling mechanisms in sensor networks. Mobile Networks and Applications, 11:723–740, 2006.
A
Algorithms and Analysis for the Subroutines
In this appendix, we present algorithms and proofs for the subroutines stated in Section 4. All constructions use the local-broadcast primitive Local-broadcast (Lemma 2.1) as the sole communication building block. Random-delay scheduling of algorithms. We frequently need to execute a collection of subroutines A1 , A2 , . . . , At , each of which internally invokes Local-broadcast. In other words, each algorithm Ai is simply a sequence of Local-broadcast-instances. Let Vi ⊆ V denote the set of nodes participating in Ai , and assume that V1 , V2 , . . . , Vt are pairwise disjoint. For a single algorithm A, let dilation(A) be an upper bound on the number of Local-broadcast instances invoked by A, and let energy(A) be an upper bound on the maximum number of times any node participates in an Local-broadcast instance during A. Furthermore, for any node v ∈ V , let congestionv (A) be an upper bound on the number of Local-broadcast instances in A where a neighbor of v acts as a transmitter. For a collection of algorithms, we define energy(A1 , . . . , At ) = max energy(Ai ), i∈[t] X congestionv (A1 , . . . , At ) = congestionv (Ai ), i∈[t]
congestion(A1 , . . . , At ) = max congestionv (A1 , . . . , At ), v∈V
dilation(A1 , . . . , At ) = max dilation(Ai ). i∈[t]
Lemma A.1 (Random-delay scheduling). Assume that each set Vi shares O(polylog n) bits of private randomness. Then the subroutines A1 , . . . , At can be executed in parallel using O(log2 n) · congestion(A1 , . . . , At ) + dilation(A1 , . . . , At ) Local-broadcast instances, while each node participates in at most O(log n) · energy(A1 , . . . , At ) Local-broadcast instances, with high probability. Proof. A naive parallel execution may cause collisions when multiple Local-broadcast instances run simultaneously. We avoid this by introducing random delays. Using the shared randomness within Vi , each algorithm Ai independently chooses a delay τi ∈ {0, 1, . . . , congestion(A1 , . . . , At ) − 1} 47
uniformly at random. The kth Local-broadcast call of Ai is then scheduled at global time s = τi + k. Consequently, the total schedule length is at most congestion(A1 , . . . , At ) + dilation(A1 , . . . , At ) − 1. Interference at a node in a time step. Fix a node v ∈ V . Across all algorithms, the number of Local-broadcast instances in which a neighbor of v acts as a transmitter while v is not a listener is at most congestion(A1 , . . . , At ). Let Bv denote this set of potentially interfering instances. Fix a global time step s, and let Is be the set of Local-broadcast calls scheduled at time s. Because delays are chosen uniformly, each instance is scheduled at time s with probability at most 1/congestion(A1 , . . . , At ). For two instances, these events are either independent (if they belong to different algorithms) or negatively associated (if they belong to the same algorithm). Let Z = |Bv ∩ Is |, µ = E[Z] ≤ 1. By a Chernoff bound for negatively associated Bernoulli variables [PS97; DR98], for any δ > 0, δ2 µ
Pr[Z ≥ (1 + δ)µ] ≤ e− 2+δ . Hence Pr[Z ≥ t] ∈ e−Ω(t) , and in particular Pr[Z ≥ c log n] ∈ n−Ω(c) . Therefore, with high probability, Z ∈ O(log n). Simulating one global time step. using
Fix a time step s and the set Is . We simulate this step R ∈ Θ(log2 n)
Local-broadcast instances, indexed by j = 1, . . . , R. For each j and each call A ∈ Is , independently, A joins instance j with probability Θ(1/ log n); otherwise all nodes of A remain silent. By a Chernoff bound, each call joins O(log n) instances with high probability. Thus the simulation incurs an O(log2 n) overhead in time and an O(log n) overhead in energy. When A joins instance j, all transmitters and listeners of A participate in instance j with their original roles. Consider a fixed call A ∈ Is and a listener v of A. At most O(log n) calls in Is have transmitters in N (v) and can therefore interfere at v. In a given instance, the probability that A joins while none of these potential interferers joins is Θ(1/ log n). Over R = Θ(log2 n) instances, a Chernoff bound implies that, with high probability, there exists an instance where this good event occurs. In that instance, the Local-broadcast call of A is simulated at v exactly as if executed in isolation. A union bound over all listeners of all calls shows that, every Local-broadcast call in every schedule is simulated correctly, with high probability. Complexity.
There are at most congestion(A1 , . . . , At ) + dilation(A1 , . . . , At ) − 1
global time steps, each simulated using R ∈ Θ(log2 n) Local-broadcast instances. Hence the total number of Local-broadcast instances is O(log2 n) · congestion(A1 , . . . , At ) + dilation(A1 , . . . , At ) . 48
Moreover, during the simulation of a single time step, each call joins at most O(log n) instances with high probability, implying an O(log n) multiplicative overhead in per-node participation. Therefore each node participates in at most O(log n) · energy(A1 , . . . , At ) Local-broadcast instances, with high probability.
A.1
Down-Cast
Recall the task Up-cast: for each cluster C ∈ V, the center c(C) holds an O(polylog n)-bit message M (C), and the goal is to deliver M (C) to every node in C. It suffices to consider the case where M (C) has size O(log n) bits. The general case of an O(polylog n)-bit message follows by repeating the same procedure O(polylog n) times, incurring only an additional O(polylog n) factor in both round and energy complexity. Single-cluster schedule. We first design an algorithm AC for a single cluster C. For ℓ = 1, 2, . . . , D, we invoke Local-broadcast(S, R) with S = {v ∈ C : L(v) = ℓ − 1},
R = {v ∈ C : L(v) = ℓ},
using M (C) as the transmitted message. Intuitively, the message propagates level by level throughout the cluster. Before the ℓth iteration, all nodes at level ℓ − 1 have already received M (C). By the correctness of Local-broadcast, the iteration ensures that all nodes at level ℓ receive M (C) by the end of the ℓth iteration. The algorithm performs D invocations of Local-broadcast. Each node participates in at most two instances, once as a listener and once as a transmitter, so the total cost is O(D polylog n) rounds and O(polylog n) energy. Multiple clusters. We extend the procedure to all clusters simultaneously using Lemma A.1. For the collection {AC }C∈V , we may use dilation ({AC }C∈V ) = D
and
congestion ({AC }C∈V ) ≤ ∆,
since each node serves as a transmitter at most once, and energy ({AC }C∈V ) ≤ 2, since each node participates at most once as a transmitter and once as a listener. Applying Lemma A.1, we obtain a schedule that executes AC for all clusters using O((D + ∆) polylog n) rounds and O(polylog n) energy.
A.2
Up-Cast
Recall the task Up-cast: for each cluster C ∈ V, some nodes may hold an O(polylog n)-bit message. The goal is for the center c(C) to learn one such message if any exists, and otherwise to determine that no message is present. It suffices to consider the case where the message size is O(log n). The general case of an O(polylog n)-bit message can be handled by repeating the same procedure O(polylog n) times, which increases both the round and energy complexities by at most an O(polylog n) factor. To ensure that the message received by the cluster center originates from the same node across all repetitions, it is enough to fix the same randomness in every repetition. 49
Algorithm.
We design an algorithm AC for a single cluster C as follows. Let msg(v) ∈ {⊥} ∪ {0, 1}O(log n)
denote the message held by each node v ∈ C, where ⊥ indicates that v holds no message. For ℓ = D, D − 1, . . . , 1, we invoke Local-broadcast(S, R) with S = {v ∈ C : L(v) = ℓ and msg(v) ̸= ⊥},
R = {v ∈ C : L(v) = ℓ − 1},
using msg(v) as the transmitted message for each sender v ∈ S. Each receiver u ∈ R that successfully receives a message stores it as msg(u). In this procedure, messages propagate level by level through the cluster, moving toward the cluster center. If at least one message is present initially, then the procedure guarantees that the cluster center receives a message by the end. The analysis of round and energy complexities, as well as the extension to multiple clusters, are identical to those for Down-cast.
A.3
Across-Matching Communication
For the task Across-matching-comm, a (1, k)-component–node matching M is given. For each blue node v, the node v itself and all red nodes u with {u, v} ∈ M are provided with the following information: • ID(v), • a shared random string r(v) of length O(polylog n). The goal of the task is that, for each edge e = {u, v} ∈ M , the endpoints u and v exchange O(polylog n) bits of information in both directions. As in Up-cast and Down-cast, it suffices to consider the case where the message size is O(log n). The general case of an O(polylog n)-bit message follows by repeating the same procedure O(polylog n) times, which increases both the round and energy complexities by at most an O(polylog n) factor. Deciding whether degM (v) > 0 for all blue nodes v. We first describe an O(M polylog n)round and O(polylog n)-energy procedure that allows all blue nodes to decide whether degM (v) > 0. For a blue node v, let Av be the algorithm consisting of one invocation of Local-broadcast(S, R), where S is the set of all red nodes u with {u, v} ∈ M and R = {v}. Each node u ∈ S transmits the message ID(v). At the end of Av , node v can determine whether degM (v) > 0 by checking whether it receives ID(v). To perform this simultaneously for all blue nodes, we apply Lemma A.1 to the collection of algorithms Av over all blue nodes v, which is possible due to the shared randomness assumption. We may use energy ({Av }v is a blue node ) = 1,
dilation ({Av }v is a blue node ) = 1,
and congestion ({Av }v is a blue node ) = M, since M equals the total number of transmitters across all instances of Av . Therefore, the overall cost is O(M polylog n) rounds and O(polylog n) energy.
50
Algorithm for a single blue node. We now design an algorithm A′v that solves the task restricted to the edges of M incident to a blue node v with degM (v) > 0. Let U = {u is red : {u, v} ∈ M }. Each node u can locally determine whether it belongs to U from the given information. Let U ∗ denote the subset of nodes in U that have not yet exchanged messages with v. Initially, U ∗ ← U . The algorithm A′v repeatedly performs the following steps: 1. Run Local-broadcast(S, R) with S = U ∗ and R = {v}, where each u ∈ U ∗ transmits the message it wishes to send to v. 2. Run Local-broadcast(S, R) with S = {v} and R = U . There are two cases for the message sent by v: • If v does not receive any message in the previous step, then v concludes that it has already exchanged messages with all nodes in U , so U ∗ = ∅ and the task is complete. In this case, v transmits a special symbol ⊥ indicating termination. • If v receives a message m from some u ∈ U in the previous step, then v transmits the pair consisting of ID(u) and the message that v wishes to send to u. This message allows u to conclude that it has successfully exchanged messages with v, so it can remove itself from U ∗ . The algorithm requires 2(degM (v) + 1) ≤ 2(k + 1) invocations of Local-broadcast. Algorithm for all blue nodes. To solve Across-matching-comm, it suffices to run A′v for all blue nodes v with degM (v) > 0. We again apply Lemma A.1 to the collection of algorithms A′v over all such blue nodes. We may use energy {A′v }v is a blue node with degM (v)>0 = 2(k + 1), dilation {A′v }v is a blue node with degM (v)>0 = 2(k + 1), and congestion {A′v }v is a blue node with degM (v)>0 = 4M, since the total number of Local-broadcast instances across all A′v is X X 2(degM (v) + 1) ≤ 4 degM (v) ≤ 4M, v
v
where the summation is over all blue nodes v with degM (v) > 0. Therefore, by Lemma A.1, the total cost is O(M polylog n) rounds and O(k polylog n) energy.
A.4
Merge
For Merge, we start with the same assumptions as in Across-matching-comm. We first perform the following preprocessing step.
51
Preprocessing. The center of each blue cluster C prepares the new O(polylog n)-bit shared randomness r∗ (C) and the new color Color∗ (C) for the new clustering V ′ , and disseminates them to all nodes in C via Down-cast. After that, we execute Across-matching-comm on the given matching M so that, for every edge e = {u, v} ∈ M , the blue endpoint v transmits its basic information to the red endpoint u. This basic information includes the existing good labeling L(v), the existing cluster identifier ID(C) of the cluster C containing v, the new shared randomness r∗ (C), and the new color Color∗ (C). The good labeling and cluster identifier for the new clustering V ′ are inherited from the original clustering V. Updates within each red cluster. We now focus on a red cluster C ′ that is incident to an edge in M . Specifically, let e = {u, v} ∈ M with u ∈ C ′ and v ∈ C. To complete the construction of the new clustering V ′ , we must update the basic information for all nodes in C ′ . This includes updating the good labeling L and disseminating the values ID(C), r∗ (C), and Color∗ (C). For notational convenience, let m∗ denote an O(log n)-bit message encoding ID(C), r∗ (C), and Color∗ (C). This is accomplished using a variant of Up-cast followed by a variant of Down-cast, both executed in parallel over all red clusters. We cannot treat these procedures as black boxes, since we must also update the good labeling in addition to disseminating information. To distinguish the new labeling from the old one, we denote the new labeling by L∗ . The original labeling L is still used to guide the communication: in the subsequent discussion, the level of a node w ∈ C ′ is L(w) and not L∗ (w) . Node u locally sets L∗ (u) = L(v) + 1. Modified up-cast. Initialize U ← {u}. During the process, any node that receives a message adds itself to U ; all nodes in U have already assigned their new label values. For ℓ = D, D −1, . . . , 1, perform the following steps: 1. Run Local-broadcast(S, R), where S is the set of nodes in level ℓ of C ′ that belong to U , and R is the set of nodes in level ℓ − 1 of C ′ . Each node x ∈ S transmits a message containing m∗ and L∗ (x). 2. If a node y receives a message from some x during this invocation of Local-broadcast, then y adds itself to U and sets L∗ (y) = L∗ (x) + 1. This process may not reach all nodes of C ′ in general; however, it guarantees that the cluster center c(C ′ ) is included in U . Modified down-cast. To complete the update, we perform a modified version of Down-cast. For ℓ = 1, 2, . . . , D, perform the following steps: 1. Run Local-broadcast(S, R), where S is the set of nodes in level ℓ − 1 of C ′ , and R is the set of nodes in level ℓ of C ′ that do not belong to U . Each node x ∈ S transmits a message containing m∗ and L∗ (x). 2. If a node y receives a message from some x during this invocation of Local-broadcast, then y sets L∗ (y) = L∗ (x) + 1. It can be shown by induction that before the ℓth iteration, all nodes in level ℓ − 1 of C ′ have already obtained m∗ and their new labels L∗ . Hence, by the end of the process, all nodes in C ′ are updated. The main difference from the modified Up-cast above is that here nodes already in U are excluded from R, since they have already received m∗ and their new labels.
52
Summary. Using the known bounds for Across-matching-comm, Up-cast, and Down-cast, the entire procedure completes in O(n polylog n) rounds and O(k polylog n) energy.
A.5
Approximate Counting
P For Approx-count, each node v holds a nonnegative integer xv such that v∈C xv ∈ nO(1) . The P b goal is for every node in a cluster C to learn an estimate X(C) of X(C) = v∈C xv satisfying b X(C) ≤ X(C) ≤ (1 + ϵ)X(C). Let Xmax ∈ nO(1) be a known upper bound on the maximum possible value of X(C). It suffices to obtain the weaker guarantee b X(C) ∈ (1 ± O(ϵ))X(C), i.e., an approximation factor of 1 ± O(ϵ) that allows both overestimation and underestimation. b Once such an estimate is available, scaling X(C) by a factor of 1 + O(ϵ) and redefining ϵ′ ∈ Θ(ϵ) b yields the desired one-sided bound X(C) ≤ X(C) ≤ (1 + ϵ)X(C). Algorithm. We focus on a single cluster C. Consider the geometric sequence of guesses Xi = (1 + ϵ)i for i = 0, 1, 2, . . ., stopping once Xi > Xmax . The number of guesses is O(ϵ−1 log n). For each guess Xi , we perform the following experiment independently m ∈ Θ(ϵ−2 log n) times. Execute an Up-cast in which each node v ∈ C sends a message with probability 1 − e−xv /Xi . The probability that the cluster center receives no message in a single experiment is Y e−xv /Xi = e−X(C)/Xi . v∈C
If Xi is close to X(C), this probability is close to 1/e. Thus, by repeating the experiment and estimating the fraction of trials with no message, we can test whether Xi is a (1 ± O(ϵ)) approximation of X(C). More precisely, the cluster center accepts a guess Xi if the absolute difference between 1/e and the observed fraction of experiments with no message is at most O(ϵ). The hidden constant will be chosen large enough to ensure that at least one guess is accepted with high probability. b After all experiments are completed, the cluster center sets X(C) to any accepted Xi (breaking b ties arbitrarily) and performs a Down-cast to broadcast X(C) to all nodes in C. Overall, Approx-count performs O(ϵ−3 log2 n) invocations of Up-cast and one invocation of Down-cast. Using the round and energy costs of these primitives, the total cost is O(ϵ−3 n polylog n) rounds and O(ϵ−3 polylog n) energy. Analysis. Fix a guess Xi . In one experiment, let Y = 1 if the cluster center receives no message and Y = 0 otherwise. Then Y is a Bernoulli random variable with mean pi := Pr[Y = 1] = e−X(C)/Xi . After m ∈ Θ(ϵ−2 log n) independent repetitions, let m
1 X pbi = Yj m j=1
be the empirical fraction of experiments with no message. A standard Chernoff bound yields 2
Pr[ |b pi − pi | > α ] ∈ 2e−Ω(mα ) . 53
Choosing α ∈ Θ(ϵ) and taking the constant in m sufficiently large ensures that |b pi − pi | ∈ O(ϵ) holds simultaneously for all guesses i with probability at least 1 − n−c for any fixed constant c, by a union bound over the O(ϵ−1 log n) indices. Next, observe that if Xi = (1 + δ)X(C) with |δ| ≤ 1/2, then pi = e−1/(1+δ) ∈
1 1 + Θ(δ) , e
and therefore pi − 1/e ∈ Θ(|δ|). We accept a guess Xi if pbi − 1/e ≤ c0 ϵ, where c0 > 0 is a sufficiently large constant. Since |b pi − pi | ∈ O(ϵ), choosing c0 large enough guarantees that (i) at least one guess is accepted, and (ii) every accepted Xi satisfies Xi ∈ (1 ± O(ϵ))X(C).
A.6
Loneliness Testing
For Loneliness-test, the goal is to determine whether V consists of exactly one cluster C = V , and to ensure that all nodes learn the outcome. Let ℓ ∈ O(log n) be a known upper bound on the maximum length of a cluster identifier. We show how to solve Loneliness-test using ℓ pairs of Local-broadcast invocations, followed by an Up-cast and a Down-cast. For each i = 1, 2, . . . , ℓ, run Local-broadcast(S, R) where S is the union of all clusters C whose ith bit of ID(C) equals 0 and R = V \ S, and then run another Local-broadcast with S and R swapped. If V consists of exactly one cluster C = V , then no node receives any message during this procedure. Otherwise, in every cluster C, some node must receive a message. Indeed, there must exist an edge {u, v} with u ∈ C and v ∈ / C, and there exists an index i such that the ith bit of ID(C) differs from the ith bit of ID(C ′ ), where C ′ is the cluster containing v. During the corresponding iteration, one endpoint transmits while the other listens, causing a message to be received. To complete the task, we perform an Up-cast in which each node sends a one-bit indicator of whether it received any message during the above procedure. The cluster center can then determine whether its cluster is the unique cluster. Finally, a Down-cast is executed to broadcast the result to all nodes. Overall, the procedure requires O(n polylog n) rounds and O(polylog n) energy.
54