Faster Information Gathering in Ad-Hoc Radio Tree Networks

Abstract

We study information gathering in ad-hoc radio networks. Initially, each node of the network has a piece of information called a rumor, and the overall objective is to gather all these rumors in the designated target node. The ad-hoc property refers to the fact that the topology of the network is unknown when the computation starts. Aggregation of rumors is not allowed, which means that each node may transmit at most one rumor in one step. We focus on networks with tree topologies, that is we assume that the network is a tree with all edges directed towards the root, but, being ad-hoc, its actual topology is not known. We provide two deterministic algorithms for this problem. For the model that does not assume any collision detection nor acknowledgement mechanisms, we give an $O(n\log \log n)$-time algorithm, improving the previous upper bound of $O(n\log n)$. We then show that this running time can be reduced to O(n), which is asymptotically optimal, if the model allows for acknowledgements of successful transmissions.

1 Introduction

We study the problem of information gathering in ad-hoc radio networks. Initially, each node of the network has a piece of information called a rumor, and the objective is to gather all these rumors, as quickly as possible, in the designated target node. The nodes communicate by sending messages via radio transmissions. At any time step, one or more nodes in the network may transmit. When a node transmits a message, this message is sent immediately to all nodes within its range. When two nodes send their messages to the same node at the same time, a collision occurs and neither message is received by that node. Aggregation of rumors is not allowed, by which we mean that each message may contain at most one rumor.

The network can be naturally modeled by a directed graph, where an edge (u, v) indicates that v is in the range of u. The ad-hoc property refers to the fact that the actual topology of the network is unknown when the computation starts. We assume that nodes are labeled by integers $0,1,\ldots ,n-1$. An information gathering protocol determines a sequence of transmissions of a node, based on its label and on the previously received messages.

Our results In this paper, we focus on ad-hoc radio networks with tree topologies, that is the underlying ad-hoc network is assumed to be a tree with all edges directed towards the root, although the actual topology of this tree is unknown.

We consider two variants of the problem. In the first one, we do not assume any collision detection or acknowledgment mechanisms, so none of the nodes (in particular neither the senders nor the intended recipient) are notified about a collision after it occurred. In this model, we give a deterministic algorithm that completes information gathering in time $O(n\log \log n)$. Our result significantly improves the previous upper bound of $O(n\log n)$ from  [7]. To our knowledge, no lower bound for this problem is known, apart from the trivial bound of $\Omega (n)$, which applies to any fixed tree and follows from the fact that each rumor must be received by the root in a different time step.

In the second part of the paper, we also consider a variant where acknowledgments of successful transmissions are provided to the sender. All the remaining nodes, though, including the intended recipient, cannot distinguish between collisions and absence of transmissions. Under this assumption, we show that the running time can be improved to O(n), which is asymptotically optimal, as explained earlier.

While we assume that all nodes are labelled $0,1,\ldots ,n-1$ (where n is the number of vertices), our algorithms’ asymptotic running times remain the same if the labels are chosen from a larger range $0,1,\ldots ,N-1$, as long as $N = O(n)$.

Related work The problem of information gathering for trees was introduced in  [7], where the model without any collision detection was studied. In addition to the $O(n\log n)$-time algorithm without aggregation—that we improve in this paper—[7] develops an O(n)-time algorithm for the model with aggregation, where a message can include any number of rumors. Another model studied in  [7], called fire-and-forward, requires that a node cannot store any rumors; a rumor received by a node has to be either discarded or immediately forwarded. For fire-and-forward protocols, a tight bound of $\Theta (n^{1.5})$ is given in [7].

The information gathering problem is closely related to two other information dissemination primitives that have been well studied in the literature on ad-hoc radio networks: broadcasting and gossiping. All the work discussed below is for ad-hoc radio networks modeled by arbitrary directed graphs, and without any collision detection capability.

In broadcasting, a single rumor from a specified source node has to be delivered to all other nodes in the network (assuming that all nodes are actually reachable from the source.) The naïve RoundRobin algorithm (see the next section) completes broadcasting in time $O(n^2)$. Following a sequence of papers [3, 5, 8, 14, 15, 22] where this naïve bound was gradually improved; it is now known that broadcasting can be solved in time $O(n\log D\log \log (D\Delta /n))$ [13], where D is the diameter of G and $\Delta$ is its maximum in-degree. This nearly matches the lower bound of $\Omega (n\log D)$ from  [12]. Randomized algorithms for broadcasting have also been well studied [1, 14, 24].

The gossiping problem is an extension of broadcasting, where each node starts with its own rumor, and all rumors need to be delivered to all nodes in the network. (In gossiping, it is assumed that the network is strongly connected.) The time complexity of deterministic algorithms for gossiping is a major open problem in the theory of ad-hoc radio networks. Obviously, the lower bound of $\Omega (n\log D)$ for broadcasting [12] applies to gossiping as well, but no better lower bound is known. It is also not known whether gossiping can be solved in time $O(n\,{\mathrm{polylog}}(n))$ with a deterministic algorithm, even if message aggregation is allowed. The best currently known upper bound is $O(n^{4/3}\log ^4n)$ [20] (see [8, 28] for some earlier work). The case when no aggregation is allowed (or with limited aggregation) was studied in [6]. Randomized algorithms for gossiping have also been well studied [9, 14, 25]. Interested readers can find more information about gossiping in the survey paper [19].

Connections to other problems This research, as well as the earlier work in [7], was motivated by the connections between information gathering in trees and other problems in distributed computing involving shared channels, including gossiping in radio networks and MAC contention resolution.

For arbitrary graphs, assuming aggregation, one can solve the gossiping problem by running an algorithm for information gathering and then broadcasting all rumors (as one message) to all nodes in the network. Thus the existence of an $O(n\,{\mathrm{polylog}}(n))$-time algorithm for information gathering would imply a positive answer to the earlier-discussed open question about the complexity of gossiping. Due to this connection, developing an $O(n\,{\mathrm{polylog}}(n))$-time algorithm for information gathering on arbitrary graphs is likely to be very difficult—if possible at all. We hope that developing efficient algorithms for trees, or for some other natural special cases, will ultimately lead to some insights helpful in resolving the complexity of the gossiping problem in arbitrary graphs.

Some algorithms for ad-hoc radio networks (see [6, 21], for example) involve constructing a spanning subtree of the network and disseminating information along this subtree. A similar approach was used in [10], where broadcasting and gossiping in radio networks with known topology were studied. Better algorithms for information gathering on trees may thus be useful in addressing similar problems for arbitrary graphs.

The problem of contention resolution for multiple-access channels (MAC) has been widely studied in the literature. (See, for example, [2, 16, 17] and the references therein.) There are in fact myriad of variants of this problem, depending on the characteristics of the communication model. Generally, an instance of the MAC contention resolution problem involves a collection of transmitters connected to a shared channel (e.g. ethernet). Some of these transmitters need to send their messages across the channel, and the objective is to design a distributed protocol that will allow them to do that. The information gathering problem for (ad-hoc) trees is in essence an extension of MAC contention resolution to multi-level hierarchies of channels, where transmitters have unique identifiers, and the structure of this hierarchy is not known.

2 Preliminaries

We now provide a formal definition of our model and introduce notation, terminology, and some basic properties used throughout the paper.

Trees In the paper we focus exclusively on radio networks with tree topologies. Such a network will be represented by a tree $\mathcal{T}$ with root r and with $n = |\mathcal{T}|$ nodes. The edges in $\mathcal{T}$ are directed towards the root, representing the direction of information flow: a node can send messages to its parent, but not to its children. We assume that each node $v\in \mathcal{T}$ is assigned a unique label from $[n] = { \left\{ 0,1,\ldots ,n-1 \right\} }$, and we denote this label by ${\textsf {label}}(v)$.

For a node v, by $\deg (v)$ we denote the degree of v, which is the number of v’s children. For any subtree X of $\mathcal{T}$ and a node $v\in X$, we denote by $X_v$ the subtree of X rooted at v that consists of all descendants of v in X.

For any integer $\gamma = 1,2,\ldots ,n-1$ and any node v of $\mathcal{T}$ define the $\gamma$ -height of v as follows. If v is a leaf then the $\gamma$-height of v is 0. If v is an internal node then let g be the maximum $\gamma$-height of a child of v. If v has fewer than $\gamma$ children whose $\gamma$-height equals g then the $\gamma$-height of v is g. Otherwise, the $\gamma$-height of v is $g+1$. The $\gamma$-height of v will be denoted by ${\textit{height}}_\gamma (v)$. In case when several trees are under consideration, to resolve potential ambiguity we will write ${\textit{height}}_\gamma (v,\mathcal{T})$ for the $\gamma$-height of v in $\mathcal{T}$. The $\gamma$-height of a tree $\mathcal{T}$, denoted ${\textit{height}}_\gamma (\mathcal{T})$, is defined as ${\textit{height}}_\gamma (r)$, that is the $\gamma$-height of its root. Figure 1 gives an example of a tree and values of 3-heights for all its nodes.

Fig. 1

An example showing a tree and the values of 3-heights for all its nodes

Note that for $\gamma =1$, the $\gamma$-height corresponds to the standard notion of depth for trees. Its name notwithstanding, the definition of $\gamma$-height is meant to capture the “bushiness” of a tree. For example, if $\mathcal{T}$ is just a path then its $\gamma$-height is equal 0 for each $\gamma \ge 2$. The concept of $\gamma$-height generalizes Strahler numbers [26, 27], introduced in hydrology to measure the branching complexity of streams. It was previously used in [7] and even earlier (under a different name) in [10] to develop radio network protocols.

The lemma below, that gives an estimate on $\gamma$-height, plays a critical role in our algorithms. Variants of this lemma appeared earlier in [7, 10].

Lemma 1

Suppose that $\mathcal{T}$ has q leaves, and let $2\le \gamma \le q$. Then ${\textit{height}}_\gamma (\mathcal{T}) \le \log _\gamma q$.

The justification for this lemma is quite simple: Equivalently, the statement is that any tree having $\gamma$-height j must have at least $\gamma ^j$ leaves. This can be seen by induction on j: if v is a vertex which is furthest from the root among all vertices of $\gamma$-height j, then v, by definition, has at least $\gamma$ children of $\gamma$-height $j-1$, each of which has at least $\gamma ^{j-1}$ leaf descendants by inductive hypothesis.

Information gathering protocols in trees Each node v of $\mathcal{T}$ has a label (or an identifier) associated with it, and denoted ${\textsf {label}}(v)$. When the computation is about to start, each node v has also a piece of information, $\rho _v$, that we call a rumor. The computation proceeds in discrete, synchronized time steps, numbered $0,1,2,\ldots$. At any step, v can either be in the receiving state, when it listens to radio transmissions from other nodes, or in the transmitting state, when it is allowed to transmit. When v transmits at a time t, the message from v is sent immediately to its parent in $\mathcal{T}$. As we do not allow rumor aggregation, this message may contain at most one rumor, plus possibly $O(\log n)$ bits of other information. If w is v’s parent, w will receive v’s message if and only if w is in the receiving state and no collision occurred, that is if no other child of w transmitted at time t. In Sects. 3 and 4 we do not assume any collision detection nor acknowledgement mechanisms, so if v’s message collides with a message from one of its siblings, neither v nor w receive any notification. (In other words, w cannot distinguish collisions between its children’s transmissions from background noise.) We relax this requirement in Sect. 5, by assuming that v (and only v) will obtain a one-bit acknowledgment from w after each successful transmission.

The objective of an information gathering protocol is to deliver all rumors from $\mathcal{T}$ to its root r, as quickly as possible. Such a protocol needs to achieve its goal even without the knowledge of the topology of $\mathcal{T}$. More formally, a gathering protocol $\mathcal{A}$ can be defined as a function that, at each time t, and for each given node v, determines the action of v at time t based only on v’s label and the information received by v up to time t. The action of v at each time step t involves choosing its state (either receiving or transmitting) and, if it is in the transmitting state, choosing which rumor to transmit.

We will say that $\mathcal{A}$ runs in time T(n) if, for any tree $\mathcal{T}$ and any assignment of labels to its nodes, after at most T(n) steps all rumors are delivered to r.

Throughout the paper we assume that all nodes know the value of n. This assumption is not essential, because otherwise an information gathering algorithm can employ a doubling trick by trying, sequentially and in increasing order, all powers of 2 as potential values of n. For our algorithms, this will at most double the time to complete gathering (although the algorithm itself will not know that and will iterate the process forever).

Protocol RoundRobin ${\textsc {RoundRobin}}$ is a simple protocol for information gathering in which nodes transmit one at a time. It consists of n rounds, and in each round the nodes transmit in the order $0,1,\ldots ,n-1$ of their labels. (Put differently, at time $t = 0,1,\ldots ,n^2-1$, the node with label $l = t\pmod n$ transmits.) For any node v, when it is its turn to transmit, v transmits any rumor from the set of rumors that have been received so far (including its own rumor) but not yet transmitted. In each round, each rumor that is still not in r will get closer to r, so after $n^2$ steps all rumors will reach r.

In our algorithms we will use a variation of this idea that we call ${\textsc {SB-RoundRobin}}$ (for source-based round-robin). In ${\textsc {SB-RoundRobin}}$ there are also n rounds, each consisting of n steps. In step $l=0,1,\ldots ,n-1$ of each round, a node v checks if it already has collected a rumor $\rho _z$ that originated from the node z with label ${\textsf {label}}(z) = l$. If so, v transmits this rumor, otherwise v is quiet. Note that, similar to ${\textsc {RoundRobin}}$, there are no collisions in ${\textsc {SB-RoundRobin}}$, since the tree topology implies that a node and its siblings share no rumors in common. The advantage of ${\textsc {SB-RoundRobin}}$ is that any node v, in a single round (n steps), will transmit all its rumors to its parent.

Strong k -selectors. Let ${\bar{S}}= (S_0, S_1, \ldots , S_{m-1})$ be a family of subsets of $[n] = { \left\{ 0,1,\ldots ,n-1 \right\} }$, the label set. ${\bar{S}}$ is called a strong k -selector ¹ if, for each k-element set $A\subseteq [n]$ and each $a\in A$, there is a set $S_i$ such that $S_i\cap A = { \left\{ a \right\} }$. As shown in [12, 18], for each k there exists a strong k-selector ${\bar{S}}= (S_0, S_1, \ldots , S_{m-1})$ with $m = O(k^2\log n)$. We will make extensive use of strong k-selectors in our algorithms. At a certain time in the computation our protocols will “run” ${\bar{S}}$, for an appropriate choice of k, by which we mean that they will execute a sequence of m consecutive steps, such that in the jth step the nodes from $S_j$ will transmit, while those not in $S_j$ will stay quiet. This will guarantee that, for any node v with at most $k-1$ siblings, there will be at least one step in the execution of ${\bar{S}}$ where v will transmit but none of its siblings will. Therefore at least one of v’s transmissions will be successful.

3 An $O(n\sqrt{\log n})$-Time Protocol

We first give a gathering protocol SimpleGather for trees with running time $O(n\sqrt{\log n})$. This will allow us to gradually introduce some techniques needed for our faster protocol that will be presented in the next section.

Assume that $n\ge 2$. We fix three parameters:

$$\begin{aligned} K&= 2^{{ \lceil \sqrt{\log n} \rceil }},\\ D&= { \lceil \log _Kn \rceil } = O(\sqrt{\log n}), \quad \text {and}\\ D'&= { \lceil \log K^3 \rceil } = O(\sqrt{\log n}). \end{aligned}$$

(Here and elsewhere all logarithms are assumed to be binary unless otherwise stated). We also fix a strong K-selector ${\bar{S}}= (S_0, S_1, \ldots , S_{m-1})$, with $m \le CK^2\log n$, for some constant $C>0$.

By Lemma 1, we have that ${\textit{height}}_K(\mathcal{T}) \le D$. Recall that, for a node v of $\mathcal{T}$, $\mathcal{T}_v$ is the subtree of $\mathcal{T}$ rooted at v. We call v light if $|\mathcal{T}_v|\le n/K^3$; otherwise we say that v is heavy. Let $\mathcal{T}'$ be the subtree of $\mathcal{T}$ induced by the heavy nodes. By the definition of heavy nodes, $\mathcal{T}'$ has at most $K^3$ leaves, so ${\textit{height}}_2(\mathcal{T}')\le D'$. Also, obviously, $r\in \mathcal{T}'$.

To streamline the description of our algorithm we will allow each node to receive and transmit messages at the same time. We will also assume a preprocessing step allowing each node v to know both the size of its subtree $\mathcal{T}_v$ (in particular, whether it is in $\mathcal{T}'$ or not), its K-height, and, if it is in $\mathcal{T}'$, its 2-height in the subtree $\mathcal{T}'$. We later explain how to implement this preprocessing and how to modify the algorithm to separate the transmitting and receiving steps.

The algorithm consists of two epochs. Epoch 1 consists of $D+1$ stages, each lasting O(n) steps. In this epoch only light vertices participate. The purpose of this epoch is to gather all rumors from $\mathcal{T}$ in $\mathcal{T}'$. Epoch 2 has $D'+1$ stages and only heavy vertices participate in the computation during this epoch. The purpose of epoch 2 is to deliver all rumors from $\mathcal{T}'$ to r. We describe the computation in the two epochs separately.

A detailed description of Algorithm SimpleGather is given in Pseudocode 1. To distinguish between computation steps (which do not consume time) and communication steps, we use command “at time t”. When the algorithm reaches this command it waits until time step t to continue processing. Each message transmission takes one time step. For each node v we maintain a set $B_v$ of rumors received by v, including its own rumor $\rho _v$.

Epoch 1: light vertices Let $0 \le h \le D$, and let v be a light vertex whose K-height equals h. Then v will be active only during stage h which starts at time $\alpha _h = (C+1)hn$ and lasts $(C+1)n$ steps. This stage is divided into two parts.

In the first part of stage h, that lasts Cn steps, v will transmit according to the strong K-selector ${\bar{S}}$. Specifically, this part has ${ \lfloor n/K^3 \rfloor }$ iterations, where each iteration corresponds to a complete execution of ${\bar{S}}$. At any time, some of the rumors in $B_v$ may be marked; the marking on a rumor indicates that the algorithm has already attempted to transmit it using ${\bar{S}}$. At the beginning of each execution of ${\bar{S}}$, v chooses any rumor $\rho _z\in B_v$ it has not yet marked, then transmits $\rho _z$ in the steps that use sets $S_i$ containing the label of v. This $\rho _z$ is then marked. (If it so happens that $B_v$ does not contain any unmarked rumors, v stays idle in this iteration.) The definition of strong K-selectors guarantees that if the parent u of v has degree at most K, then $\rho _z$ will be received by u at some point over the course of the selector. However, if u’s degree is larger it may not have received $\rho _z$. Note that the total number of steps required for this part of stage h is ${ \lfloor n/K^3 \rfloor } \cdot m \le Cn$, so these steps will be completed before the second part of stage h starts.

In the second part, that starts at time $\alpha _h + Cn$ and lasts n steps, we simply run a cycle of ${\textsc {SB-RoundRobin}}$.

We claim that the following invariant holds for all $h = 0,1,\ldots ,D$:

($\mathbf I ^{}_{h}$):

If $u\in \mathcal{T}$ is a light vertex with ${\textit{height}}_K(u) \le h$, then u and its parent have both received all rumors from $\mathcal{T}_u$ before time step $\alpha _{h+1}$ (when stage $h+1$ starts).

(Note that $u\ne r$, because $|\mathcal{T}_u|\le n/K^3 < n$. So u does have a parent.)

To prove this invariant we proceed by induction on h. For convenience, we introduce an artificial base case where $h=-1$ (with stage $-1$ being void), for which condition ($\mathbf I ^{}_{-1}$) holds vacuously.

We now give a proof of the inductive step. Fix some $h \in { \left\{ 0,1,\ldots ,D \right\} }$, and assume that ($\mathbf I ^{}_{h-1}$) holds. We need to prove ($\mathbf I ^{}_{h}$). If ${\textit{height}}_K(u) \le h-1$ then ($\mathbf I ^{}_{h}$) follows immediately from the inductive assumption ($\mathbf I ^{}_{h-1}$). So assume that ${\textit{height}}_K(u) = h$.

Consider the subtree $\mathcal{H}$ rooted at u and containing all descendants of u whose K-height is equal to h. (See Fig. 2 for illustration.) By the inductive assumption ($\mathbf I ^{}_{h-1}$), at time $\alpha _h$ any $v\in \mathcal{H}$ has all rumors from the subtrees rooted at its descendants of K-height strictly smaller than h, in addition to its own rumor $\rho _{v}$. Therefore all rumors from $\mathcal{T}_u$ are already in $\mathcal{H}$ and each of them has exactly one copy in $\mathcal{H}$, because all nodes in $\mathcal{H}$ were idle before time $\alpha _h$.

We now make the following claim:

Claim 1

During the first part of stage h, right after each execution of ${\bar{S}}$ the collection of nodes in $\mathcal{H}$ still holding unmarked rumors forms an induced sub-tree of $\mathcal{H}$ rooted at u.

The claim follows from induction: At the beginning of the stage (that is, at time $\alpha _h$) the nodes in $\mathcal{H}$ still hold their own original rumor, and it is unmarked since those nodes were idle so far. So this induced sub-tree from the claim is the whole H.

In the inductive step, suppose that the nodes with unmarked rumors satisfy Claim 1 right before some execution of ${\bar{S}}$. For any $v\in \mathcal{H}-{ \left\{ u \right\} }$, the definition of $\mathcal{H}$ guarantees that v has at most $K-1$ siblings in $\mathcal{H}$. Hence, the definition of strong K-selectors implies that, as long as v has an unmarked rumor right before this execution of ${\bar{S}}$, v will successfully transmit an unmarked rumor to its parent during this execution. Therefore no “holes” can ever form, that is, if a node other than u has an unmarked rumor then so does its parent, proving the inductive step and completing the proof of Claim 1.

Claim 1 implies that, during the first part of stage h, node u will receive a new rumor in each execution of ${\bar{S}}$, as long as there is at least one rumor from $\mathcal{T}_u$ that still has not reached u. Since $\mathcal{T}_u$ originally had $|\mathcal{T}_u|\le n/K^3$ rumors, u will receive all rumors from its subtree after at most $n/K^3$ executions of ${\bar{S}}$, thus before the second part of stage h starts at time $\alpha _h + Cn$.

Next, we prove the second part of ($\mathbf I ^{}_{h}$). Let w be the parent of u (see Fig. 2). Note that, as ${\textit{height}}_K(u) =h$, node u will attempt to transmit its rumors to w during the first part, but, since we are not making any assumptions about the degree of w, there is no guarantee that w will receive them. This is where the second part of this stage is needed. Since u has all rumors from $\mathcal{T}_u$ after the first part of this stage, and in the second part each rumor is transmitted without collisions, all rumors from u will reach w when stage h ends (right before time $\alpha _{h+1}$), completing the proof of ($\mathbf I ^{}_{h}$).

Fig. 2

Proving invariant ($\mathbf I ^{}_{h}$). Dark-shaded subtrees of $\mathcal{T}_u$ consist of light nodes with K-height at most $h-1$. $\mathcal{H}$ consists of the descendants of u with K-height equal h

Using invariant ($\mathbf I ^{}_{h}$) for $h=D$, we obtain that, when epoch 1 ends, each heavy node w will have received rumors from the subtrees rooted at all light children of w. Therefore at that time all rumors from $\mathcal{T}$ will be already in $\mathcal{T}'$, with each rumor having exactly one copy in $\mathcal{T}'$.

Epoch 2: heavy vertices In this epoch only heavy nodes (that is, those in $\mathcal{T}'$) participate in the computation. As explained above, when epoch 2 starts, all rumors are already in $\mathcal{T}'$. In this epoch we have $D'+1$ stages numbered $0,1,\ldots ,D'$. Stage g starts at time $\alpha '_g = \alpha _{D+1}+2ng$ and it lasts 2n steps. In stage g the nodes in $\mathcal{T}'$ whose 2-height is equal g will participate. Similar to the stages of epoch 1, this stage has two parts and the second part executes ${\textsc {SB-RoundRobin}}$, as before. The difference is that now, in the first part, instead of using the strong K-selector, each heavy node will transmit for n consecutive steps.

We need to show that r will receive all rumors at the end. The argument is similar as for light vertices, but with a twist, since we do not use selectors now; instead we have steps when all nodes transmit. In essence, we show that each stage reduces by at least one the 2-height of the minimum subtree of $\mathcal{T}'$ that contains all rumors.

Specifically, we show that the following invariant holds for all $g = 0,1,\ldots ,D'$:

($\mathbf J ^{}_{g}$):

If $u\in \mathcal{T}'$ is a heavy vertex with ${\textit{height}}_2(u,\mathcal{T}') \le g$, then u has received all rumors from $\mathcal{T}_u$ before time $\alpha '_{g+1}$ (when stage $g+1$ starts). Further, if $u\ne r$ then the parent of u has received all rumors from $\mathcal{T}_u$ before this time as well.

We prove invariant ($\mathbf J ^{}_{g}$) by induction on g. For convenience, we introduce an artificial base case where $g=-1$ (with stage $-1$ being void). Then, as we have explained earlier, ($\mathbf J ^{}_{-1}$) follows from $\alpha '_0 = \alpha _{D+1}$ and from property ($\mathbf I ^{}_{D}$).

We now prove the inductive step. Fix some stage $g \in { \left\{ 0,1,\ldots ,D' \right\} }$. Let u be a heavy node with ${\textit{height}}_2(u,\mathcal{T}') \le g$. If ${\textit{height}}_2(u,\mathcal{T}') \le g-1$, we are done, by the inductive assumption. So we can assume that ${\textit{height}}_2(u,\mathcal{T}') = g$.

Let P be the subtree of $\mathcal{T}'$ rooted at u and consisting of all descendants of u whose 2-height in $\mathcal{T}'$ is equal g. Then P is simply a path. By the inductive assumption, for each $v\in P$, all rumors from the subtrees of v rooted at its children of 2-height at most $g-1$ are in v. Thus all rumors from $\mathcal{T}_u$ are already in P. All nodes in P participate in stage g, but their children outside P do not transmit. Therefore each transmission from any node $x\in P-{ \left\{ u \right\} }$ during stage g will be successful. Due to pipelining, all rumors from P will reach u after the first part of stage g, implying the first part of ($\mathbf J ^{}_{g}$).

To show the second part of ($\mathbf J ^{}_{g}$), suppose that $u\ne r$ and let w be the parent of u. In the second part of stage g there are no collisions, so all rumors from u will be successfully sent to w. Hence, after stage g all rumors from $\mathcal{T}_u$ will be in w, completing the proof that ($\mathbf J ^{}_{g}$) holds.

We are now ready to wrap up the analysis of Algorithm ${\textsc {SimpleGather}}$. Since ${\textit{height}}_2(r,\mathcal{T}') \le D'$, invariant ($\mathbf J ^{}_{D'}$) implies that r will receive all rumors from $\mathcal{T}_r = \mathcal{T}$ before time $\alpha '_{D'+1}$. Hence the running time of Algorithm ${\textsc {SimpleGather}}$ is at most $\alpha '_{D+1} = O(n\sqrt{\log n})$.

Removing simplifying assumptions At the beginning of this section we made some simplifying assumptions. It still remains to explain how to modify our algorithm so that it works even if these assumptions do not hold. These modifications are similar to those described in [7], but we include them here for the sake of completeness.

First, we assumed a preprocessing step whereby each v knows certain parameters of its subtree $\mathcal{T}_v$, including the size, its K-height, etc. The justification for this lies in the algorithm from [7] for information gathering in trees with aggregation. Such an algorithm can be modified to compute in linear time any function f such that f(v) is uniquely determined by the values of f on the children of v, so long as the output of f can be transmitted in $O(\log n)$ bits (in particular, any function whose output is an integer at most polynomial in n). The modification is that each node u, when its sends its message (which, in the algorithm from [7] contains all rumors from $\mathcal{T}_u$), it will instead send the value of f(u). A node v, after it receives the values of f(u) from each child u, will compute² the value of f(v).

We also assumed that each node can receive and transmit messages at the same time. We now need to modify the algorithm so that it receives messages only in the receiving state and transmits only in the transmitting state. For the RoundRobin steps this is trivial: a node v is in the transmitting state only if it is scheduled to transmit, otherwise it is in the receiving state. For other steps, we will explain the modification for light and heavy nodes separately.

Consider the computation of the light nodes during the steps when they transmit according to the strong selector. Instead of the strong K-selector, we can use the strong $(K+1)$-selector, which will not affect the asymptotic running time. When a node v is scheduled to transmit, it enters the transmitting state, otherwise it is in the receiving state. In the proof, where we argue that the message from v will reach its parent, instead of applying the selector argument to v and its siblings, we apply it to the set of nodes consisting of v, its siblings, and its parent, arguing that there will be a step when v is the only node transmitting among its siblings and when its parent is in the receiving state.

Finally, consider the computation of the heavy nodes, at steps when all of them transmit. We modify the algorithm so that, in any stage g, the iteration (in Line 19) of these steps is preceded by O(n)-time preprocessing. Recall that the nodes whose 2-height in $\mathcal{T}'$ is equal g form disjoint paths. We can run a single round of RoundRobin where each node transmits an arbitrary message. This way, each node will know whether it is the first node on one of these paths or not. If a node x is first on some path, say P, x sends a message along this path, so that each node $y\in P$ can compute its distance from x. Then, in the part where all nodes transmit, we replace each step by two consecutive steps (even and odd), and we use parity to synchronize the computation along these paths: the nodes at even positions are in the receiving state at even steps and in the transmitting state at odd steps, and the nodes at odd positions do the opposite.

Summarizing this section, we have presented Algorithm SimpleGather that completes information gathering in ad-hoc radio networks with tree topologies in time $O(n\sqrt{\log n})$. In the next section, we will show how to improve this bound to $O(n\log \log n)$.

4 A Protocol with Running Time $O(n\log \log n)$

In this section we consider the same basic model of information gathering in trees as in Sect. 3, that is, the model does not provide any collision detection and rumor aggregation is not allowed. We show how to refine our $O(n\sqrt{\log n})$ protocol SimpleGather to improve the running time to $O(n\log \log n)$. This is the first main result of our paper, as summarized in the theorem below.

Theorem 1

The problem of information gathering in ad-hoc networks with tree topology, without rumor aggregation, can be solved in time $O(n\log \log n)$.

Our protocol that achieves running time $O(n\log \log n)$ will be called  FastGather. This protocol can be thought of as an iterative application of the idea behind Algorithm SimpleGather from Sect. 3. We assume that the reader is familiar with Algorithm SimpleGather and its analysis, and in our presentation we will focus on high level ideas behind Algorithm FastGather, referring the reader to Sect. 3 for the implementation of some details.

As before, we use notation $\mathcal{T}$ for the input tree and $n = |\mathcal{T}|$ for the number of vertices in $\mathcal{T}$. We assume that n is sufficiently large, and we will establish some needed lower bounds for n as we work through the proof. We fix some arbitrary integer constant $\beta \ge 2$. For $\ell = 0, 1,2, \ldots ,$ let $K_\ell = { \lceil n^{\beta ^{-\ell }} \rceil }$. So $K_0 = n$, $K_1 = { \lceil n^{1/\beta } \rceil }$, the sequence $(K_\ell )_\ell$ is non-increasing, and $\lim _{\ell \rightarrow \infty } K_\ell = 2$. Let L be the largest value of $\ell$ for which $n^{\beta ^{-\ell }} \ge \log n$. (Note that L is well defined for $n\ge 3$, since $\beta$ is fixed). We thus have the following exact and asymptotic bounds:

$$\begin{aligned} L&\le \log _\beta (\log n/\log \log n)&K_L&\ge \log n \nonumber \\ L&= \Theta (\log \log n)&K_L&= O(\log ^\beta n) \end{aligned}$$

(1)

(The last bound follows from $n^{\beta ^{-(L+1)}} < \log n$.) For $\ell = 1,2,\ldots ,L$, by ${\bar{S}}^\ell = (S^\ell _0, S^\ell _1,\ldots ,S^\ell _{m_\ell -1})$ we denote a strong $K_\ell$-selector of size $m_\ell \le C K_\ell ^2\log n$, for some constant $C>0$. As discussed in Sect. 2, such selectors ${\bar{S}}^\ell$ exist.

Let $\mathcal{T}^{(0)} = \mathcal{T}$, and for each $\ell = 1,2,\ldots ,L$, let $\mathcal{T}^{(\ell )}$ be the subtree of $\mathcal{T}$ induced by the nodes v with $|\mathcal{T}_v| > n/K_{\ell }^3$. Each tree $\mathcal{T}^{(\ell )}$ is non-empty, rooted at r, and $\mathcal{T}^{(\ell )} \subseteq \mathcal{T}^{(\ell -1)}$ for all $\ell \ge 1$.

As in the previous section, we will make some simplifying assumptions. First, we will assume that all nodes can receive and transmit messages at the same time. Second, we will also assume that each node v knows the size of its subtree $|\mathcal{T}_v|$, its $K_\ell$-heights in $\mathcal{T}$, for each $\ell \le L$, and its 2-height within $\mathcal{T}^L$. After completing the description of the algorithm we will explain how to modify it so that these assumptions will not be needed.

Algorithm FastGather consists of $L+1$ epochs, numbered $1,2,\ldots ,L+1$. In each epoch $\ell =1,2,\ldots ,L$ only the nodes in $\mathcal{T}^{(\ell -1)} - \mathcal{T}^{(\ell )}$ participate. At the beginning of epoch $\ell$ all rumors will be already collected in $\mathcal{T}^{(\ell -1)}$, and the purpose of epoch $\ell$ is to move all these rumors into $\mathcal{T}^{(\ell )}$. (Each such epoch is similar to epoch 1 from Algorithm SimpleGather.) Each of these L epochs will run in time O(n), so their total running time will be $O(nL) = O(n\log \log n)$. In epoch $L+1$, only the nodes in $\mathcal{T}^{(L)}$ participate. (This epoch corresponds to epoch 2 from Algorithm SimpleGather.) At the beginning of this epoch all rumors will be already in $\mathcal{T}^{(L)}$, and when this epoch is complete, all rumors will be collected in r. This epoch will take time $O(n\log \log n)$. Thus the total running time will be also $O(n\log \log n)$.

We use two more parameters: $D = 3 \beta +1 = O(1)$ and $D' = \log (K^3_L)= O(\log \log n)$, where the last equality follows from the last bound in (1). (We “recycle” notations D and $D'$ from Sect. 3, because these parameters are analogous to those used in that section: $D+1$ is the number of rounds of each epoch $1,2,\ldots ,L$, that correspond to epoch 1 from Algorithm SimpleGather, while $D'+1$ is the number of rounds of epoch $L+1$, that corresponds to epoch 2 from Algorithm SimpleGather.)

Claim 2

Assuming that n is large enough, for each $\ell = 1,\ldots ,L$, we have ${\textit{height}}_{K_{\ell }}( \mathcal{T}^{(\ell -1)} ) \le D$.

First, we verify the claim for $\ell =1$. $\mathcal{T}^{(0)}$ has at most n leaves, so Lemma 1 implies that

$$\begin{aligned} {\textit{height}}_{K_1}(\mathcal{T}^{(0)}) \le \log _{K_1} n \le \log _{n^{1/\beta }} n = \beta \le D. \end{aligned}$$

Consider now some $\ell \ge 2$. The definition of tree $\mathcal{T}^{(\ell -1)}$ implies that it has at most $K_{\ell -1}^3$ leaves. Since $K_{\ell -1} \le 2n^{\beta ^{-\ell +1}}$ and $K_{\ell }\ge n^{\beta ^{-\ell }}$, from Lemma 1 we have

$$\begin{aligned} {\textit{height}}_{K_\ell } ( \mathcal{T}^{(\ell -1)} )&\le \log _{K_{\ell }}(K_{\ell -1}^3) \\&\le 3\, \log _{ n^{\beta ^{-\ell }} }(2n^{\beta ^{-\ell +1}}) \\&= 3\, \log _{ n^{\beta ^{-\ell }} }n^{\beta ^{-\ell +1}} + 3\, \log _{ n^{\beta ^{-\ell }} } 2 \\&= 3\beta + \frac{3\beta ^{\ell }}{\log n} \le 3\beta + \frac{3\beta ^{L}}{\log n} \le 3\beta +1, \end{aligned}$$

where the last inequality holds as long as $3\beta ^{L}\le \log n$, which is true for $n \ge 256$ (since, by the first bound in (1), we have $\beta ^L \le \log n/\log \log n$). This completes the proof of Claim 2.

We now provide the complete description of the algorithm and its analysis.

Epochs $\ell = 1,2,\ldots ,L$. In epoch $\ell$, only the nodes in $\mathcal{T}^{(\ell -1)} - \mathcal{T}^{(\ell )}$ are active; all other nodes remain quiet. The computation in this epoch is very similar to the computation of light nodes (in epoch 1) in Algorithm SimpleGather. Epoch $\ell$ starts at time $\gamma _\ell = (D+1)(2C+1)(\ell -1) n$ and lasts $(D+1)(2C+1)n$ steps.

Let $v\in \mathcal{T}^{(\ell -1)} - \mathcal{T}^{(\ell )}$. The computation of v in epoch $\ell$ consists of $D+1$ identical stages. Each stage $h = 0,1,\ldots ,D$ starts at time step $\alpha _{\ell ,h} = \gamma _\ell + (2C+1)hn$ and lasts $(2C+1)n$ steps.

Stage h itself consists of two parts. The first part starts at time $\alpha _{\ell ,h}$ and lasts time 2Cn. During this part we execute ${ \lceil n/K_\ell ^3 \rceil }$ iterations, where each iteration executes the strong $K_{\ell }$-selector ${\bar{S}}^\ell$. The time needed to complete these iterations is at most

$$\begin{aligned} { \lceil \frac{n}{K_\ell ^3} \rceil } \cdot CK^2_{\ell }\log n \le 2Cn \cdot \frac{ \log n }{ K_\ell } \le 2Cn \cdot \frac{ \log n }{ n^{\beta ^{-\ell }} } \le 2Cn \cdot \frac{ \log n }{ n^{\beta ^{-L}} } \le 2Cn, \end{aligned}$$

where the last inequality follows from the definition of L. Thus all iterations executing the strong selector will complete before time $\alpha _{\ell ,h}+2Cn$. Then v stays idle until time $\alpha _{\ell ,h}+2Cn$, which is when the second part starts. In the second part we run the SB-RoundRobin protocol, which takes n steps. So stage h will complete right before step $\alpha _{\ell ,h}+(2C+1)n = \alpha _{\ell ,h+1}$. Note that the whole epoch will last $(D+1)(2C+1) n$ steps, as needed.

We claim that the algorithm preserves the following invariant for $\ell = 1,2,\ldots ,L$:

($\mathbf I ^{\ell }_{}$):

Let $u\in \mathcal{T}- \mathcal{T}^{(\ell )}$. Then u and its parent both have received all rumors from $\mathcal{T}_u$ before time step $\gamma _{\ell +1}$ (when epoch $\ell +1$ starts).

(Note that $u\ne r$, because $|\mathcal{T}_u|\le n/K_\ell ^3 < n$. So u does have a parent.)

The proof of invariant ($\mathbf I ^{\ell }_{}$) is by induction. For the base case, we consider an artificial epoch 0, for which condition ($\mathbf I ^{0}_{}$) holds vacuously (because $\mathcal{T}- \mathcal{T}^{(0)} = \emptyset$).

In the inductive step, fix some $\ell \in { \left\{ 1,2,\ldots ,L \right\} }$ and assume that ($\mathbf I ^{\ell -1}_{}$) holds. We want to show that ($\mathbf I ^{\ell }_{}$) holds as well. So let $u \in \mathcal{T}-\mathcal{T}^{(\ell )}$. If $u \not \in \mathcal{T}^{(\ell -1)}$ then ($\mathbf I ^{\ell }_{}$) follows directly from the inductive assumption. We can thus assume that $u\in \mathcal{T}^{(\ell -1)} - \mathcal{T}^{(\ell )}$, as illustrated in Fig. 3.

Fig. 3

Proving invariant ($\mathbf I ^{\ell }_{}$). (In this picture, node w is in $\mathcal{T}^{(\ell )}$, but it also may be in $\mathcal{T}^{(\ell -1)} - \mathcal{T}^{(\ell )}$.)

The argument now is very similar to that for Algorithm ${\textsc {SimpleGather}}$ in Sect. 3, when we analyzed epoch 1. For each $h = 0,1,\ldots ,D$ we prove a refined version of condition ($\mathbf I ^{\ell }_{}$):

($\mathbf I ^{\ell }_{h}$):

Let $u\in \mathcal{T}^{(\ell -1)} - \mathcal{T}^{(\ell )}$ satisfy ${\textit{height}}_{K_\ell }(u,\mathcal{T}^{(\ell -1)}) \le h$. Then u and its parent will both receive all rumors from $\mathcal{T}_u$ before time $\alpha _{\ell ,h+1}$ (that is before stage $h+1$ of epoch $\ell$ starts).

The proof is the same as for invariant ($\mathbf I ^{}_{h}$) in Sect. 3, proceeding by induction on h. In the (artificial) base case for $h=-1$ we use the condition ($\mathbf I ^{\ell -1}_{}$) which gives us that all rumors from $\mathcal{T}_u$ are in $\mathcal{T}^{(\ell -1)}_u$ when stage 0 starts. In the inductive step, tor each fixed $h\in { \left\{ 1,2,\ldots ,D \right\} }$, assume (without loss of generality, because of the inductive assumption) that ${\textit{height}}_{K_\ell }(u,\mathcal{T}^{(\ell -1)}) = h$ and consider a subtree $\mathcal{H}$ rooted at u and consisting of all descendants of u in $\mathcal{T}^{(\ell -1)}$ whose $K_\ell$-height in $\mathcal{T}^{(\ell -1)}$ is equal h. By the inductive assumption, at the beginning of stage h all rumors from $\mathcal{T}_u$ are already in $\mathcal{H}$. Then, the executions of ${\bar{S}}^\ell$ in the first part of stage h will move all rumors from $\mathcal{H}$ to u. In the second part of stage h the execution of SB-RoundRobin will move all rumors from u to its parent. (See Sect. 3 for the details.)

By applying condition ($\mathbf I ^{\ell +1}_{h}$) with $h = D$, we obtain that after all stages of epoch $\ell$ are complete, that is immediately prior to time $\gamma _{\ell +1}$, u and its parent will receive all rumors from $\mathcal{T}_u$, completing the inductive step and the proof of invariant ($\mathbf I ^{\ell }_{}$).

Epoch $L+1$ We focus on subtree $\mathcal{T}^{(L)}$, which contains all rumors when this epoch starts. The subtree of each leaf of $\mathcal{T}^{(L)}$ has size at least $n/K^3_L$. These subtrees are disjoint, so $\mathcal{T}^{(L)}$ has at most $K^3_L$ leaves. Therefore the 2-height of $\mathcal{T}^{(L)}$ is at most $D'$. (Recall that $D' = \log (K^3_L)=O(\log \log n)$.)

In epoch $L+1$, that starts at time $\gamma _{L+1}$, only the nodes in $\mathcal{T}^{(L)}$ participate in the computation. The computation is similar to epoch 2 from Algorithm SimpleGather. As before, this epoch consists of $D'+1$ stages, where each stage $g = 0,1,...,D'$ starts at time $\alpha '_g = \gamma _{L+1} + 2gn$ and consists of two parts. In the first part, we have n consecutive steps in which each node transmits. In the second part, also of length n, we run one iteration of SB-RoundRobin.

To prove correctness, it is enough to show that the following invariant holds for all stages $g = 0,1,\ldots ,D'$:

($\mathbf J ^{}_{g}$):

If $u\in \mathcal{T}^{(L)}$ satisfies ${\textit{height}}_2(u,\mathcal{T}^{(L)}) \le g$, then u has received all rumors from $\mathcal{T}_u$ before time $\alpha '_{g+1}$. Further, if $u\ne r$ then the parent of u has received all rumors from $\mathcal{T}_u$ before this time as well.

The proof of this invariant is identical to the proof of the analogous invariant ($\mathbf J ^{}_{g}$) in Sect. 3, so we omit it here.

To complete the correctness proof we apply invariant ($\mathbf J ^{}_{D'}$), which implies that after stage $D'$ of epoch $L+1$ (that is, at time $\alpha '_{D'+1}$) the root r of $\mathcal{T}$ will have received all rumors from $\mathcal{T}_r = \mathcal{T}$.

As for the running time, we recall that $L = O(\log \log n)$. Each epoch $\ell = 1,2,\ldots ,L$ has $D+1 = O(1)$ stages, where each stage takes time O(n), so the execution of the first L epochs will take time $O(n\log \log n)$. Epoch $L+1$ has $D'+1 = O(\log \log n)$ stages, each stage consisting of O(n) steps, so this epoch will complete in time $O(n\log \log n)$. We thus have that the overall running time of our protocol is $O(n\log \log n)$.

It remains to explain that the simplifying assumptions we made at the beginning of this section are not needed. Computing all subtree sizes and all $K_\ell$-heights can be done recursively bottom-up, using the linear-time information gathering algorithm from [7] that uses aggregation. Using the same approach, we can compute the 2-heights of all nodes in $\mathcal{T}^{(L)}$. This was explained in Sect. 3. The difference now is that each node has to compute $L+1 = O(\log \log n)$ values $K_\ell$, and, since we limit book-keeping information in each message up to $O(\log n)$ bits, these values need to be computed separately. Nevertheless, the total pre-computation time will still be $O(n\log \log n)$.

Removing the assumption that nodes can receive and transmit at the same time can be done in the same way as in Sect. 3. Roughly, in each epoch $\ell = 1,2,\ldots ,L$, any node $v \in \mathcal{T}^{(\ell -1)} - \mathcal{T}^{(\ell )}$ uses a strong $(K_\ell +1)$-selector (instead of a strong $K_\ell$-selector) to determine whether to be in the receiving or transmitting state. In epoch L the computation (in the steps when all nodes transmit) is synchronized by transmitting a control message along induced paths, and then choosing the receiving or transmitting state according to node parity.

Summarizing, we have proved above that the running time of Algorithm ${\textsc {FastGather}}$ is $O(n\log \log n)$, thus completing the proof of Theorem 1.

5 An O(n)-Time Protocol with Acknowledgments

In this section we consider a slightly different communication model from that in Sects. 3 and 4. We now assume that acknowledgements of successful transmissions are provided to the sender (immediately after the transmission). All the remaining nodes, including the intended recipient, cannot distinguish between collisions and absence of transmissions. The main result of this section, as summarized in the theorem below, is that with this feature it is possible to achieve the optimal running time O(n).

Theorem 2

The problem of information gathering in ad-hoc networks with tree topology, without rumor aggregation, can be solved in time O(n) if acknowledgments of successful transmissions are provided.

The overall structure of our O(n)-time protocol, called Algorithm LinGather, is similar to Algorithm SimpleGather. It consists of two epochs. The first epoch does not use the acknowledgement feature, and it is in fact identical to epoch 1 in Algorithm SimpleGather, except for a different choice of the parameters. After this epoch, lasting time O(n), all rumors will be collected in the subtree $\mathcal{T}'$ consisting of heavy nodes (for a suitable definition of “heavy”).

In the second epoch only the heavy nodes in $\mathcal{T}'$ will participate in the computation, and the objective of this epoch is to move all rumors, already collected in $\mathcal{T}'$, to the root r. The key obstacle to overcome in this epoch is congestion stemming from the fact that, although $\mathcal{T}'$ may be small, its nodes have many rumors to transmit. This congestion means that simply repeatedly applying strong k-selectors is no longer enough. For example, suppose that $\mathcal{T}'$ is a complete binary tree of depth $\log \log n$, with each leaf holding $\frac{n}{\log n}$ rumors. Repeating a strong 2-selector $\frac{n}{\log n}$ times guarantees that each rumor from each leaf will be successfully transmitted to this leaf’s parent. But the lower bound in [11] on the size of selectors implies that that this would require time $\Omega (n)$ – no better than ${\textsc {SB-RoundRobin}}$, and it would only move all the rumors up a single level of the tree. In this tree $\mathcal{T}'$ there are $\log \log n$ levels and the congestion only gets worse as we move up the tree, so this approach will not lead to an O(n)-time algorithm.

To overcome this obstacle, we introduce two novel tools that will play a critical role in our algorithm. The first tool is a so-called amortizing selector family. Since a parent, say with degree d, receives at most one rumor per round, it clearly cannot simultaneously be receiving rumors at an average rate greater than $\frac{1}{d}$ from each child individually. With the amortizing selector family, we will be able to achieve a constant fraction of this bound over long time intervals, so long as each child knows (approximately) how many siblings it is competing with.

Of course, such a family will not be useful unless a node can obtain an accurate estimate of its parent’s degree, which will be the focus of our second tool, k -distinguishers. Using a k-distinguisher a node can determine whether its parent’s degree d is at least k or at most 2k. While this information is not sufficient to determine the exact relation between d and k, we show how to combine different k-distinguishers to obtain another structure, called a cardinality estimator, that will determine the value of d within a factor of 4. Using this estimate, and the earlier described amortizing selector family, a node can quickly transmit its rumors to its parent. This will allow us to gather all rumors from $\mathcal{T}'$ in the root in time O(n).

The degree estimation problem is in fact more subtle than what we outlined above. In reality, the value that needs to be estimated is the number of siblings that are currently active (attempting to transmit), which could be much smaller than the parent’s degree. It also can vary over time, so this degree estimation needs to be performed repeatedly and very efficiently.

This section is divided into three parts. In Sects. 5.1 and 5.2 we give precise definitions and constructions of our combinatorial structures. Our O(n)-time protocol LinGather is described and analyzed in Sect. 5.3.

5.1 Construction of Amortizing Selectors

We now define the concept of an amortizing selector family ${\bar{F}}$. Similarly to a strong selector, this amortizing family will be a collection of subsets of the underlying label set [n], though now it will be doubly indexed, ${\bar{F}}= { \{ F^j_i \} }$. The general idea is that a node with roughly $2^j$ siblings will use sets $F^j_0, F^j_1,\ldots$ to determine its transmissions.

Specifically, let ${\bar{F}}= { \{ F^j_{i} \} }$, where $i \in { \left\{ 0,1,\ldots ,m-1 \right\} }$ and $j \in { \left\{ 0,1,\ldots ,\kappa \right\} }$, for some integer parameters $m\ge 1$ and $\kappa \in { \left\{ 1,2, \ldots ,{ \lceil \log n \rceil } \right\} }$. We say that ${\bar{F}}$ is an amortizing selector family with cumulative success rate $\rho$ if the following statement holds:

• (ASF) For each $j = 0,1,\ldots ,\kappa -1$, each subset $A \subseteq [n]$ satisfying $2^{j-1} \le |A| \le 2^{j+1}$, and each $a \in A$, there are at least ${\rho }m / {|A|}$ distinct indices i for which

  $$\begin{aligned} a \in F^j_i \text { and } A \cap (F^{j-1}_i \cup F^j_i \cup F^{j+1}_i) = { \left\{ a \right\} }. \end{aligned}$$

(For $j=0$ the set $F^{-1}_i$ is defined to be empty.) For a fixed j, we will refer to the collection of sets ${\bar{F}}^j = F^j_0, F^j_1,\ldots ,F^j_{m-1}$ as a j-amortizing selector. Parameter m in the definition of ${\bar{F}}$ is called the length of ${\bar{F}}$.

In the application to rumour gathering, m can be thought of as the “running time” of ${\bar{F}}$, $2^j$ as a node’s estimate of the number of its active siblings, and $2^{\kappa }$ as some bound on the parent’s maximum degree (that is, the number of siblings, including v) that can be handled by ${\bar{F}}$. A node v whose number of active siblings is estimated to be about $2^j$ transmits at time step i if and only if ${\textsf {label}}(v)\in F^j_i$. Denoting by A the set of labels of v’s siblings, what condition (ASF) is then saying is that if $|A| \le 2^{\kappa -1}$, and if each active sibling of v (including v itself) estimates |A| within a factor of 2, then v (as well as each of its active siblings) will succeed at rate at least ${\rho }/{|A|}$. Thus the parent of v will receive transmissions from its children at overall rate $\rho$ – averaging about one successful transmission per $1/\rho$ steps.

Note that strong k-selectors (see Sect. 2) are not sufficient to give us that success rate. Even if all children know the exact degree k of their parent and execute synchronously a strong k-selector ${\bar{S}}$, their overall success rate guaranteed by ${\bar{S}}$ is only roughly $1/(k\log n)$. On the other hand, the RoundRobin protocol will satisfy (ASF) only for those A with $|A| \ge \rho n$ (here the intuition is that if $|A|=k$, then ${{\textsc {RoundRobin}}}$ by construction will have k successful transmissions from A in each n rounds).

Theorem 3

There are fixed constants $\rho ,C > 0$ such that the following is true: For any n and $\kappa \le { \lceil \log n \rceil }$, and any $m \ge Ck^2 \log n$, where $k = 2^\kappa$, there is an amortizing selector family with parameters $n,\kappa ,m$ and cumulative success rate $\rho$.

Proof

Let $\kappa$, n and m be given such that $m \ge C k^2 \log n$, where $k = 2^\kappa$, and let C be a constant to be determined later. We form our amortizing selector family probabilistically: For each a, i,  and j, we independently include a in $F^j_{i}$ with probability $1/2^{j+1}$.

Observe that it suffices to check the selector property (ASF) for the case $|A|=2^{j+1}$. Indeed, this follows from monotonicity: for any set A with $2^{j-1}\le |A|\le 2^{j+1}$, if we replace A by a set $A'$ such that $A\subseteq A'$ and $|A'| = 2^{j+1}$, then for any $a \in A$ and any i satisfying

$$\begin{aligned} A' \cap (F^{j-1}_{i} \cup F^j_{i} \cup F^{j+1}_{i}) = \{a\}, \end{aligned}$$

we must also have

$$\begin{aligned} A \cap (F^{j-1}_{i} \cup F^j_{i} \cup F^{j+1}_{i}) = \{a\}. \end{aligned}$$

So if there are at least ${\rho ' m}/{|A'|}$ distinct indices i satisfying the first equality, then there are at least $\rho m/{|A|}$ indices satisfying the second equality, for $\rho = {\textstyle \frac{1}{4}}\rho '$. In other words, restricting the argument to sets A with $|A|=2^{j+1}$ can only overestimate the cumulative success rate by a factor of 4.

Now fix some $j \in { \left\{ 1,2, \dots , \kappa -1 \right\} }$, a set $A\subseteq [n]$ with $|A| = 2^{j+1}$ and some $a\in A$, and let the random variable X be the number of indices i for which (ASF) holds, that is

$$\begin{aligned} X = \left| \left\{ i: a \in F^j_{i} \text { and } A \cap (F^{j-1}_{i} \cup F^j_{i} \cup F^{j+1}_{i}) = \{a\} \right\} \right| \end{aligned}$$

Denote $\ell = 2^{j+1}$. Each label is included in $F^{j-1}$, $F^j$ and $F^{j+1}$ with respective probabilities $\frac{2}{\ell }$, $\frac{1}{\ell }$ and $\frac{1}{2\ell }$. Thus the expected value of X is

$$\begin{aligned} \mu _X&= m { \Big ( \frac{1}{\ell } \Big ) } { \Big ( 1 - \frac{2}{\ell } \Big ) }^{\ell -1} { \Big ( 1 - \frac{1}{\ell } \Big ) }^{\ell -1} { \Big ( 1-\frac{1}{2\ell } \Big ) }^{\ell -1} \nonumber \\&\ge m { \Big ( \frac{1}{\ell } \Big ) } { \Big ( 1 - \frac{2}{\ell } \Big ) }^{\ell } { \Big ( 1 - \frac{1}{\ell } \Big ) }^{\ell } { \Big ( 1-\frac{1}{2\ell } \Big ) }^{\ell } \ge \frac{ 2 \rho ' m}{\ell }, \end{aligned}$$

(2)

for $\rho ' = {\textstyle \frac{1}{2}}(\frac{21}{64})^4$, where the last inequality holds because the three expressions $(1 - 2/\ell )^{\ell }$, $(1 - 1/\ell )^{\ell }$, and $(1- 1/2 \ell )^{\ell }$ are increasing functions of $\ell$, so they are minimized for $\ell = 4$ (as we assume that $j\ge 1$).

Using the bound (2) on $\mu _X$ and applying the Chernoff bound, we get

$$\begin{aligned} {\mathrm{Pr}}[ X \le \rho ' m/ \ell ] \,&\le \, {\mathrm{Pr}}[ X \le {\textstyle \frac{1}{2}}\mu _X] \\ \,&\le \, \mathrm {e}^{-\mu _X/8} \,\le \, \mathrm {e}^{-\rho ' m/4\ell }. \end{aligned}$$

The above derivation assumes $j\ge 1$, but it can be easily extended to $j=0$; the only difference is that the sets $F^{-1}_i$, which are empty, do not need to be considered.

We now use the union bound over all choices of $\ell$, a, and A. We have at most n choices of a, at most $\log n+1\le 2\log n$ choices for $\ell$, and at most $\left( {\begin{array}{c}n\\ \ell -1\end{array}}\right) \le n^{k-1}$ choices of A, given fixed values of $\ell$ and a. Thus the probability that our family does not satisfy condition (ASF) with rate $\rho '$, for sets A with cardinality $\ell = 2^{j+1}$, is at most

$$\begin{aligned} n\cdot (2 \log n) \cdot n^{k-1} \cdot \mathrm {e}^{-\rho ' m/4\ell } \;&\le \; 2 n^{2k} \cdot \mathrm {e}^{-\rho ' \cdot (Ck^2 \log n)/ 4\ell } \\&\le \; 2 n^{2k} \cdot \mathrm {e}^{-C \rho ' k (\log n) / 4} \\&=\; 2 n^{k(2 -C \rho ' (\log \mathrm {e}) / 4)}, \end{aligned}$$

which is smaller than 1 for sufficiently large C. Thus there exists a family $\{F^j_i\}$ that satisfies condition (ASF) with rate $\rho '$ for sets A with cardinality $2^{j+1}$. As explained earlier, this implies the existence of an amortizing selector family with cumulative success rate $\rho = {\textstyle \frac{1}{4}}\rho '$.

We remark that similar structures to our amortizing selector families, called ultra-selectors, were considered in [4]. The most crucial difference is that the intersection property of ultra-selectors is weaker: any set A of a specified cardinality is hit a constant fraction of times on any element, while we require that each element of A is hit at about the same rate. (Naturally, this makes amortizing selectors larger by about a factor of k.)

5.2 Construction of k-Distinguishers and Cardinality Estimators

In this section, we define k-distinguishers and show how to construct them. We then show how we can use k-distinguishers to construct other combinatorial structures called cardinality estimators, which a node can use to estimate the number of its siblings.

Consider a family ${\bar{E}}= { \left\{ E_0,E_1,\ldots ,E_{m-1} \right\} }$ of sets, where $E_j \subseteq [n]$ for each j. For $A\subseteq [n]$ and $a\in A$, define

$$\begin{aligned} \textit{hits}_{a,A}({\bar{E}}) = |{ \left\{ j {\;:\;}E_j\cap A = { \left\{ a \right\} } \right\} }|, \end{aligned}$$

that is $\textit{hits}_{a,A}({\bar{E}})$ is the number of indices j for which $E_j$ intersects A exactly on a. Note that, using this terminology, ${\bar{E}}$ is a strong k-selector if and only if $\textit{hits}_{a,A}({\bar{E}}) >0$ for all sets $A\subseteq [n]$ of cardinality at most k and all $a\in A$.

We say that ${\bar{E}}$ is a k -distinguisher if there is a threshold value $\xi$ (which may depend on k) such that, for any $A\subseteq [n]$ and $a\in A$, the following conditions hold:

• (DIS1) if $|A| < k$ then $\textit{hits}_{a,A}({\bar{E}}) > \xi$, and

• (DIS2) if $|A|\ge 2k$ then $\textit{hits}_{a,A}({\bar{E}}) \le \xi$.

We make no assumptions on what happens for $|A|\in { \left\{ k, k+1,\ldots ,2k-1 \right\} }$.

The idea is this: consider a fixed a, and imagine that we have some set A that contains a, but its other elements are not known. Suppose that we also have an access to a hit oracle that for any set Y will tell us whether $Y\cap A = { \left\{ a \right\} }$ or not. We can then apply this oracle to each set $Y = E_j$ in a k-distinguisher ${\bar{E}}$, which will give us the cardinality of $\textit{hits}_{a,A}({\bar{E}})$, thus allowing us to extract some information about the cardinality of A: If $|\textit{hits}_{a,A}({\bar{E}})| \le \xi$ then we know that $|A| \ge k$, and if $|\textit{hits}_{a,A}({\bar{E}})| > \xi$ then we know that $|A| < 2k$.

In our radio network model, if all nodes transmit according to a k-distinguisher ${\bar{E}}$ (that is, at time j a node v transmits iff ${\textsf {label}}(v)\in E_j$), then the acknowledgement of a message received from a parent corresponds exactly to a “yes” response from the hit oracle. This way, after running the whole k-distinguisher, each node can determine either that its parent has at least k children or that it has fewer than 2k children.

What we will show shortly, again by a probabilistic construction, is that not-too-large k-distinguishers exist:

Theorem 4

For any $n\ge 2$ and $k \in { \left\{ 1,2,\ldots , { \lfloor n/2 \rfloor } \right\} }$ there exists a k-distinguisher of size $m = O(k^2\log n)$.

Proof

Let $m= C k^2 \log n$, where C is some sufficiently large constant whose value we will determine later. We choose the collection of random sets ${\bar{E}}= { \left\{ E_0,E_1,\ldots ,E_{m-1} \right\} }$ by independently including each $a \in [n]$ in each $E_j$ with probability 1 / 2k (“independently” here means that the mn events of the form “a is contained in $E_j$” are all independent). Thus, for any set A and $a\in A$, the probability that $E_j\cap A = { \left\{ a \right\} }$ is $(1/2k)(1-1/2k)^{|A|-1}$, and the expected value of $\textit{hits}_{a,A}({\bar{E}})$ is

$$\begin{aligned} {\mathbf{E}}[\,\textit{hits}_{a,A}({\bar{E}})\,] = m \cdot \frac{1}{2k}{ \Big ( 1-\frac{1}{2k} \Big ) }^{|A|-1}. \end{aligned}$$

(3)

We claim that, for a suitable value of $\xi$, the probability that there exists a set $A\subseteq [n]$ and some $a\in A$ for which ${\bar{E}}$ does not satisfy one of conditions (DIS1), (DIS2) is smaller than 1 (and in fact tends to 0). This will be sufficient to show existence of a k-distinguisher with threshold value $\xi$.

Observe that in order to be a k-distinguisher it is sufficient that ${\bar{E}}$ satisfies (DIS1) for sets A with $|A| = k$ and satisfies (DIS2) for sets A with $|A| = 2k$. This is true because the value of $\textit{hits}_{a,A}({\bar{E}})$ is monotone with respect to the inclusion: if $a \in A\subseteq B$ then each set hitting B exactly on a also hits A exactly on a, so $\textit{hits}_{a,A}({\bar{E}}) \ge \textit{hits}_{a,B}({\bar{E}})$.

Now consider some fixed $a\in [n]$ and two sets $A_1, A_2 \subseteq [n]$ such that $|A_1| = k$, $|A_2| = 2k$ and $a\in A_1\cap A_2$. For $i =1,2$, we consider two corresponding random variables $X_i = |\textit{hits}_{a,A_i}({\bar{E}})|$ and their expected values $\mu _i = {\mathrm{Exp}}[X_i]$. For any integer $k\ge 1$ we have

$$\begin{aligned} \frac{1}{\mathrm {e}^{1/2}} \;&\le \; { \Big ( 1-\frac{1}{2k} \Big ) }^{k-1} \,,\;\text {and}\\ \frac{1}{\mathrm {e}} \;&\le \; { \Big ( 1-\frac{1}{2k} \Big ) }^{2k-1} \le \frac{1}{2} \end{aligned}$$

From (3), substituting $m = Ck^2\log n$, this gives us the corresponding estimates for $\mu _1$ and $\mu _2$:

$$\begin{aligned} \textstyle \frac{1}{2\mathrm {e}^{1/2}} C k \log n \;&\le \; \mu _1 \,,\;\text {and}\\ \textstyle \frac{1}{2\mathrm {e}} C k \log n \;&\le \; \mu _{2} \;\le \; {\textstyle \frac{1}{4}}C k \log n \end{aligned}$$

Since $\mathrm {e}^{-1/2} > {\textstyle \frac{1}{2}}$, we have $\mu _2 < \mu _1$, so we can choose an $\epsilon \in (0,1)$ and $\xi$ for which

$$\begin{aligned} (1+\epsilon )\mu _2< \xi < (1-\epsilon )\mu _1. \end{aligned}$$

Then the probability that ${\bar{E}}$ violates (DIS1) for $A=A_1$ is

$$\begin{aligned} {\mathrm{Pr}}[ X_1 \le \xi ] \;&\le \; {\mathrm{Pr}}[ X_1 \le (1-\epsilon )\mu _1]\\&\le \; \mathrm {e}^{-\epsilon ^2\mu _1/2}\\&\le \; \mathrm {e}^{-C \epsilon ^2 \mathrm {e}^{-1/2} k (\log n)/ 4}, \end{aligned}$$

where in the second inequality we use the Chernoff bound for deviations below the mean. Similarly, using the Chernoff bound for deviations above the mean, we can bound the probability of ${\bar{E}}$ violating (DIS2) for $A=A_2$ as follows:

$$\begin{aligned} {\mathrm{Pr}}[ X_2 > \xi ] \;&\le \; {\mathrm{Pr}}[ X_2 \ge (1+\epsilon )\mu _2]\\&\le \; \mathrm {e}^{-\epsilon ^2\mu _2/3}\\&\le \; \mathrm {e}^{- C \epsilon ^2\mathrm {e}^{-1} k(\log n)/6}. \end{aligned}$$

To finish off the proof, we apply the union bound. We have at most n choices for a, at most $\left( {\begin{array}{c}n\\ k-1\end{array}}\right) \le n^{k-1} \le n^{2k-1}$ choices of $A_1$, and at most $\left( {\begin{array}{c}n\\ 2k-1\end{array}}\right) \le n^{2k-1}$ choices of $A_2$. Note also that $\mathrm {e}^{-1/2}/4 > \mathrm {e}^{-1}/6$. Putting it all together, the probability that ${\bar{E}}$ is not a k-distinguisher is at most

$$\begin{aligned} \textstyle n \cdot {\left( {\begin{array}{c}n\\ k-1\end{array}}\right) } \cdot {\mathrm{Pr}}\left[ X_1 \le \xi \right] + n \cdot {\left( {\begin{array}{c}n\\ 2k-1\end{array}}\right) } \cdot {\mathrm{Pr}}\left[ X_2> \xi \right]&\le n^{2k} \cdot \left( {\mathrm{Pr}}\left[ X_1 \le \xi \right] +{\mathrm{Pr}}\left[ X_2 > \xi \right] \right) \\&\le 2 n^{2k} \cdot \mathrm {e}^{- C\epsilon ^2\mathrm {e}^{-1} k(\log n)/6}\\&= 2n^{k(2 - C\epsilon ^2\mathrm {e}^{-1}(\log \mathrm {e})/6)}\\&< 1, \end{aligned}$$

where the last inequality holds for sufficiently large C. As explained earlier, this implies existence of a k-distinguisher with threshold value $\xi$.

Cardinality estimators Now let $\lambda$ be a fixed parameter between 0 and 1. For each $i = 0,1,\ldots ,{ \lceil \lambda \log n \rceil }$, let ${\bar{E}}^i$ be a $2^i$-distinguisher of size $O(2^{2i}\log n)$ and with threshold value $\xi _i$. We can then concatenate these k-distinguishers to obtain a sequence

$$\begin{aligned} {\widehat{E}}\;=\; {\bar{E}}^0 {\bar{E}}^1\, \ldots \,{\bar{E}}^{{ \lceil \lambda \log n \rceil }} \end{aligned}$$

of length $m_{{\widehat{E}}} = \sum _{i=0}^{{ \lceil \lambda \log n \rceil }}O(2^{2i}\log n) = O(n^{2\lambda }\log n)$. We will refer to ${\widehat{E}}$ as a cardinality estimator, because applying our hit oracle to ${\widehat{E}}$ we can estimate a cardinality of an unknown set within a factor of 4, making $O(n^{2\lambda }\log n)$ hit queries.

More specifically, consider again a scenario where we have a fixed a and some unknown set A containing a, where $|A|\le n^{\lambda }$. Using the hit oracle, compute the values $h_i = \textit{hits}_{a,A}({\bar{E}}^i)$, for all i. If $i_0$ is the smallest i for which $h_i > \xi _i$, then by definition of our k-distinguishers (for $k= 2^{i_0-1}$ and $k = 2^{i_0}$) we must have $2^{i_0-1} \le |A| <2^{i_0+1}$. The value of $i_0-1$ will denoted $\textit{est}_{A,a}({\widehat{E}})$. It represents the estimate of $\log (|A|)$ computed by ${\widehat{E}}$ for label a.

In our gathering framework, suppose that some subset of children of a node u is transmitting according to ${\widehat{E}}$, and let A be the set of their labels. If v is one of these children and $a = {\textsf {label}}(v)$, then, thanks to the transmission acknowledgement mechanism, this computation will allow v to compute $j = \textit{est}_{A,a}({\widehat{E}})$ for which the cardinality of A is between $2^j$ and $2^{j+2}$, which is exactly what we need to be able to run the amortizing selector.

The problem of estimating the degree of nodes arises naturally in ad-hoc radio network. For example, some ideas similar to ours can be found in [23], where the authors construct structures called fuzzy separating families and use them to estimate vertex degrees in undirected radio networks, to speed-up leader election. Due to their limited range of parameters and differences in the definition and usage, fuzzy separating families are not sufficient for our application.

5.3 Linear-Time Protocol

We are now ready to present our linear-time algorithm for rumor gathering on trees that uses transmission acknowledgements, thus proving Theorem 2.

As before, $\mathcal{T}$ is the input tree with n nodes. We will recycle the notions of light and heavy nodes from Sect. 3, although now we will use slightly different parameters. Let $0<\delta < \frac{1}{13}$ be a (fixed) small positive constant, and let $K = { \lceil n^\delta \rceil }$. Throughout this section we assume that n is sufficiently large, so that $K\le n^{1/13}$. We say that $v\in \mathcal{T}$ is light if $|T_v|\le n/K^3$ and we call v heavy otherwise. By $\mathcal{T}'$ we denote the subtree of $\mathcal{T}$ induced by the heavy nodes.

We will use three combinatorial structures:

• ${\bar{S}}$ is a strong K-selector of length $m_{{\bar{S}}} = O(K^2\log n)$. As explained in Sect. 3, such strong K-selectors exist.

• ${\bar{F}}$ is an amortizing selector family with cumulative success rate $\rho$, parameter $\kappa ={ \lceil \log (2 K^3) \rceil }$ and length $m_{{\bar{F}}}=C K^7$, where C is a positive constant. If $k = 2^\kappa$ then $k^2\log n = o(K^7)$, so, from Theorem 3, such ${\bar{F}}$ exists if C is large enough. (In fact, it exists for any $C>0$, as long as n is sufficiently large).

• ${\widehat{E}}$ is a cardinality estimator with parameter $\lambda =3 \delta$ and length $m_{{\widehat{E}}} \le m_{{\bar{F}}} = CK^7$. By the construction in Sect. 5.2, since $n^{2\lambda }\log n = n^{6\delta }\log n = o(K^7)$, such ${\widehat{E}}$ exists as long as C is large enough.

Without loss of generality (see Sect. 3), in the algorithm we can assume that the nodes can receive and transmit messages at the same time. We also assume that each node v knows the size of its subtree $\mathcal{T}_v$, its K-height, etc.

For a node v, a rumor from $\mathcal{T}_v$ is called pending at v if it has been received by v but not by v’s parent. Thanks to the transmission acknowledgement feature, v knows which rumors it has already received are pending.

Algorithm LinGather. Our algorithm consists of two epochs. The first epoch is essentially identical to epoch 1 in Algorithm SimpleGather. The objective of this epoch is to move all rumors from $\mathcal{T}$ to $\mathcal{T}'$ in time O(n). In the second epoch only the heavy nodes in $\mathcal{T}'$ will participate in the computation, and its objective is to move all rumors from $\mathcal{T}'$ to r in time O(n). This epoch, which is quite different from our earlier algorithms, will use the amortizing selector families and degree estimators to achieve its goal.

Epoch 1: In this epoch only light nodes participate, and its objective is to move all rumors into $\mathcal{T}'$. In this epoch we will not be taking advantage of the acknowledgement mechanism. As mentioned earlier, except for different choices of parameters, this epoch is essentially identical to epoch 1 of Algorithm SimpleGather, so we only give a very brief overview here.

Let $D= { \lceil \log _K n \rceil } \le { \lceil 1/\delta \rceil } =O(1)$. By Lemma 1, the K-height of $\mathcal{T}$ is at most D. Epoch 1 consists of $D+1$ stages, where in each stage $h = 0,1,\ldots ,D$, nodes of K-height equal h participate. Each stage h consists of ${ \lceil n/K^3 \rceil }$ executions of the strong selector ${\bar{S}}$, followed by an execution of a single round of SB-RoundRobin, taking total time ${ \lceil n/K^3 \rceil } \cdot m_{{\bar{S}}} +n=O(n)$. So the entire epoch takes time $(D+1)\cdot O(n) = O(n)$ as well.

Epoch 2 When this epoch starts, all rumors from $\mathcal{T}$ are already gathered in $\mathcal{T}'$, and the objective is to gather them in the root. As before, no node in $\mathcal{T}'$ can have more than $K^3= O(n^{3\delta })$ heavy children, since each heavy child has at least $n/K^3$ descendants. In other words, the degree of $\mathcal{T}'$ is at most $K^3$.

The second epoch is divided into stages, each consisting of $2(m_{{\widehat{E}}}+m_{{\bar{F}}})$ steps. The number of stages is $f = { \lceil 3Bn/(2m_{{\widehat{E}}}+2m_{{\bar{F}}}) \rceil }$, where B is a constant that will be determined during the analysis. So the total time of epoch 2 is O(n).

A node v will be called active in a given stage if at the beginning of the stage it has already received all rumors from its subtree $\mathcal{T}_v$, but still has at least one pending rumor. (It is possible for a node to never become active, if it receives its last rumor within some stage and then finishes transmitting before the beginning of the next stage.)

In any stage, a node $v\in \mathcal{T}'-{ \left\{ r \right\} }$ behaves as follows:

• In each odd-numbered time step of the stage, if v still has a pending rumor then v transmits such a rumor. (This applies no matter whether v is active or not.)

• In the even-numbered time steps, if v is active in this stage, its computation has two parts:

  • In the first part, v transmits according to the cardinality estimator ${\widehat{E}}$. (Here, it does not matter what message v transmits.) This will take time $2m_{{\widehat{E}}}$. Let $j = \textit{est}_{A,a}({\widehat{E}})$, as defined in Sect. 5.2, for $a = {\textsf {label}}(v)$ and A being the set of labels of active siblings of v (inclusive). Thus at this point v knows that its number of active siblings is between $2^j$ and $2^{j+2}$. (Note that different active siblings may compute different estimates.)

  • In the second part, v transmits its pending rumors (if it still has any) using the corresponding $(j+1)$-amortizing selector ${\bar{F}}^{j+1}$ from the amortizing selector family ${\bar{F}}$. If v happens to run out of pending rumors, it stops transmitting. This part lasts for $2m_{{\bar{F}}}$ steps.

The intuition here is that, most of the time, the cardinality estimations from the first part of a stage will remain accurate throughout the stage, allowing the amortizing selectors to make significant progress at each active node. Although no progress is made during the cardinality estimation itself, the estimation takes only a fraction of the time in the epoch (since by construction $m_{{\widehat{E}}}$ is no larger than $m_{{\bar{F}}}$), so this does not pose a problem.

Analysis Recall that the objective of epoch 1 is to move all rumors from $\mathcal{T}$ to $\mathcal{T}'$. The proof of correctness for epoch 1 is identical to that for Algorithm SimpleGather in Sect. 3, so we omit it here. The correctness of epoch 1 (more specifically, the analog of invariant ($\mathbf I ^{}_{h}$) with $h=D$) implies that, for any $u\in \mathcal{T}'$ and any light child x of u, when epoch 2 starts then all rumors from $\mathcal{T}_x$ will be collected in u.

It remains to prove correctness of epoch 2. Our key claim, stated below, is that each node u with subtree size $s = |\mathcal{T}_u|$ will have received all s rumors from $\mathcal{T}_u$ within O(s) steps of the start of the epoch. In order to make the inductive argument work, however, we need a more subtle property, which also guarantees that the rumors aggregate at least at a steady rate over time.

($\mathbf L ^{}_{}$):

For any heavy node u with $|\mathcal{T}_u| = s$, and any $j = 1,2,\ldots ,s$, node u will receive at least j rumors in the first $B(2s+j)$ steps of epoch 2, where B is some sufficiently large absolute constant. In particular, u will receive all of the rumors from its subtree no later than in step 3Bs of epoch 2.

We will show that invariant ($\mathbf L ^{}_{}$) holds by induction on u’s height within $\mathcal{T}'$. If u a leaf of $\mathcal{T}'$ then invariant ($\mathbf L ^{}_{}$) follows from the correctness of epoch 1, because all children of u are light.

Now consider a non-leaf node $u\in \mathcal{T}'$ with $|\mathcal{T}_u| = s$. Let $v_1,v_2,\ldots ,v_\ell$ be the heavy children of u. For each $i=1,2,\ldots ,\ell$, let $s_i = |\mathcal{T}_{v_i}|$, and order these children so that $s_1 \ge s_2 \ge \dots \ge s_\ell \ge n/K^3$. (The last inequality holds because all $v_i$’s are heavy.) When epoch 2 starts, all rumors from the light children of u are already in u, so we only need to estimate how long it takes for the rumors in the subtrees of $v_1,v_2,\ldots ,v_\ell$ to reach u.

In the proof we will treat $v_1$, a child of u with the largest subtree, separately from all other heavy children $v_2,v_3,\ldots ,v_\ell$. The basic idea is this: Since $s_2,\ldots ,s_\ell$ are each at most s / 2, the inductive assumption implies that each $v_i$, for $i\ge 2$, will receive all rumors from its subtree $\mathcal{T}_{v_i}$ no later than at time $3Bs_i \le {\textstyle \frac{3}{2}}Bs$. This leaves us time at least ${\textstyle \frac{1}{2}}Bs+Bj$ to push j rumors to u, which can be accomplished using amortized selectors (if multiple nodes transmit simultaneously) or odd-numbered transmissions (if only $v_1$ transmits).

We introduce the following notation (see Fig. 4):

$t_1 =$ :

the first time step when the nodes $v_2,v_3,\ldots ,v_\ell$ have already received all rumors from their subtrees. By the inductive hypothesis for invariant ($\mathbf L ^{}_{}$) (for nodes of smaller height in $\mathcal{T}'$), we have that $t_1 \le 3Bs_2 \le {\textstyle \frac{3}{2}}Bs$.

$t_2=$ :

the first time step when u has received all rumors from the subtrees of $v_2,v_3,\ldots ,v_\ell$.

$q=$ :

the number of stages between times $t_1$ and $t_2$. Here, we only count full stages, namely those that are fully included in the time interval $(t_1,t_2)$.

Fig. 4

Notation for the analysis of Algorithm LinGather

In each of the q full stages between times $t_1$ and $t_2$ at least one of $v_2,v_3,\ldots ,v_\ell$ must be active. Each of these stages must be of one of the two following types:

Complete: :

All active $v_i$’s in stages of this type have pending rumors throughout the entire stage. Let $a\ge 1$ be the number of active nodes among $v_2,v_3,\ldots ,v_\ell$ during such stage. Then, by the definition of our amortizing selector family ${\bar{F}}$, u received at least $\rho a m_{{\bar{F}}}/(a+1) \ge {\textstyle \frac{1}{2}}\rho m_{{\bar{F}}}$ new rumors from $v_2,v_3,\ldots ,v_\ell$. (We need $a+1$ in the denominator because $v_1$ may also be active.) Therefore the number of complete stages is at most $(\sum _{i=2}^\ell s_i)/({\textstyle \frac{1}{2}}\rho m_{{\bar{F}}}) \le 2s/(\rho m_{{\bar{F}}})$.

Incomplete: :

In these stages some active $v_i$ transmits its last rumor from $\mathcal{T}_{v_i}$, and stops transmitting. There are at most $K^3$ incomplete stages, because $\ell \le K^3$ and each $v_i$ becomes active at most once (when it has received all rumors from its subtree).

We can thus bound $t_2$ as follows:

$$\begin{aligned} t_2 \;&\le \; t_1 + 2\left( m_{{\widehat{E}}}+m_{{\bar{F}}}\right) (q+2)\nonumber \\&\le \; {\textstyle \frac{3}{2}}Bs + 2(m_{{\widehat{E}}}+m_{{\bar{F}}}) \cdot \left[ 2s/\left( \rho m_{{\bar{F}}}\right) + K^3 + 2 \right] \nonumber \\&\le \; {\textstyle \frac{3}{2}}Bs + 2\left( CK^7+CK^7\right) \cdot \left[ 2s/\left( CK^7\rho \right) + 2K^3 \right] \end{aligned}$$

(4)

$$\begin{aligned}&=\; {\textstyle \frac{3}{2}}Bs + 8 s/\rho + 8CK^{10}\nonumber \\&\le \; \left( {\textstyle \frac{3}{2}}B + 8/\rho +8C\right) s \end{aligned}$$

(5)

$$\begin{aligned}&\le \; 2Bs. \end{aligned}$$

(6)

In the above derivation, inequality (4) follows from $m_{{\bar{F}}} = CK^7$ and $m_{{\widehat{E}}}\le CK^7$. Inequality (5) is true because $K \le n^{1/13}$ and $s \ge n/K^3$ (because u is a heavy node), so $K^{10} \le n/K^3 \le s$. Inequality (6) holds because we can take B sufficiently large.

By the above bound, node $v_1$ is the only node that could still be transmitting after time 2Bs. In particular, if it has a pending rumor during an odd numbered time step after this point, it successfully transmits this rumor to u. By the inductive assumption, for each $j = 1,2,\ldots ,s_1$, $v_1$ will have received at least j rumors by time $B(2s_1+j) \le B(2s+j-2)$. So, for $j=1,2,\ldots ,s_1$, node u will receive the jth rumor from $v_1$ no later than at time $B(2s+j-2)+ 2 \le B(2s+j)$. If $s_1 < j \le s$, then by time $B(2s+j)$ node u will have in fact received all rumors from $\mathcal{T}_u$. This completes the proof of invariant ($\mathbf L ^{}_{}$).

Now, taking $u = r$ in invariant ($\mathbf L ^{}_{}$), we obtain that r will receive all rumors from $\mathcal{T}$ in at most 3Bn steps of epoch 2. Thus the algorithm will complete information gathering in at most f stages of epoch 2 and O(n) time. Since the first epoch also takes linear time, the total running time of Algorithm LinGather is O(n), completing the proof of Theorem 2.

6 Final Comments

Some open problems about information gathering still remain, even for the special case of trees. For the model without rumor aggregation, we gave an algorithm running in time $O(n\log \log n)$. The lower bound of $\Omega (n)$ is trivial, and it applies to any fixed tree, even if the tree is known to the algorithm. It would be interesting to close this gap.

For the model with aggregation allowed, as shown in [7], one can accomplish gathering in time O(n). This is optimal if the running time is expressed as a function of n only. For trees of depth D and maximum degree $\Delta$, the trivial lower bound is $\Omega (\max (D,\Delta ))$, and it is not known whether time ${\tilde{O}}( \max (D,\Delta ) )$ can be accomplished.

The most intriguing open problem in this area is the complexity of information gathering in arbitrary networks (under the assumption that the target node is reachable from all nodes), for which no sub-quadratic algorithm is known, even if aggregation is allowed. For strongly connected graphs the problem is equivalent to gossiping (see Sect. 1), so it can be solved in time ${\tilde{O}}(n^{4/3})$ [20] even without aggregation. Strong connectivity allows for indirect feedback, and known gossiping algorithms take advantage of this to coordinate the computation. Such feedback is not possible in acyclic graphs, so the natural direction for research would be to study first the case of acyclic graphs.