Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks

Ganczorz, Adam; Jurdzinski, Tomasz; Pelc, Andrzej

doi:10.4230/LIPIcs.OPODIS.2025.14

Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks

Adam Ganczorz

Institute of Computer Science, University of Wrocław, Poland Tomasz Jurdzinski

Institute of Computer Science, University of Wrocław, Poland Andrzej Pelc

Département d’informatique, Université du Québec en Outaouais, Gatineau, Canada

Abstract

We consider two fundamental communication tasks in arbitrary radio networks: broadcasting (information from one source has to reach all nodes) and gossiping (every node has a message and all messages have to reach all nodes). Nodes are assigned labels that are (not necessarily different) binary strings. Each node knows its own label and can use it as a parameter in the same deterministic algorithm. The length of a labeling scheme is the largest length of a label. The goal is to find labeling schemes of asymptotically optimal length for the above tasks, and to design fast deterministic distributed algorithms for each of them, using labels of optimal length.

Our main result concerns broadcasting. We show the existence of a labeling scheme of constant length that supports broadcasting in time $O(D+\log^{2}n)$ , where $D$ is the diameter of the network and $n$ is the number of nodes. This broadcasting time is an improvement over the best currently known $O(D\log n+\log^{2}n)$ time of broadcasting with constant-length labels, due to Ellen and Gilbert (SPAA 2020). It also matches the optimal broadcasting time in radio networks of known topology. Hence, we show that appropriately chosen node labels of constant length permit to achieve, in a distributed way, the optimal centralized broadcasting time. This is, perhaps, the most surprising finding of this paper. We are able to obtain our result thanks to a novel methodological tool of propagating information in radio networks, that we call a 2-height respecting tree.

Next, we apply our broadcasting algorithm to solve the gossiping problem. We get a gossiping algorithm working in time $O(D+\Delta\log n+\log^{2}n)$ , using a labeling scheme of optimal length $O(\log\Delta)$ , where $\Delta$ is the maximum degree. Our time is the same as the best known gossiping time in radio networks of known topology.

Keywords and phrases:

radio network, distributed algorithms, algorithms with advice, labeling scheme, broadcasting, gossiping

Funding:

Andrzej Pelc: Partially supported by NSERC discovery grant RGPIN 2024-03767 and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Distributed algorithms

Related Version:

Full Version: https://arxiv.org/abs/2410.07382

Funding:

Supported by the National Science Center, Poland (NCN), grant 2020/39/B/ST6/03288.

DOI:

10.4230/LIPIcs.OPODIS.2025.14

Event:

29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Editors:

Andrei Arusoaie, Emanuel Onica, Michael Spear, and Sara Tucci-Piergiovanni

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

We consider two fundamental communication tasks often occurring in networks. In broadcasting, one node, called the source, has a message that must reach all other nodes. In gossiping, every node has a message and all messages have to reach all nodes.

The model and the problem

We consider radio networks modeled as simple undirected connected graphs. Throughout this paper, $G=(V,E)$ denotes the graph modeling the network, $n$ denotes the number of its nodes, $D$ its diameter, and $\Delta$ its maximum degree. At the cost of a small abuse of notation, we sometimes use $D$ to denote the height of a BFS spanning tree of a graph with a fixed root node. Note however that the height of a BFS tree is not larger than the diameter $D$ and not smaller than $D/2$ , so the orders of magnitude are the same. In our probabilistic considerations concerning graphs with $n$ nodes, we use the term “with high probability” (whp) to mean “with probability at least $1-1/n$ ”.

We use square brackets to indicate sets of consecutive integers: $[i,j]=\{i,\dots,j\}$ and $[i]=[1,i]$ . All logarithms are to the base 2. For simplicity of presentation, we assume throughout the paper that the number of nodes of a graph $n$ is a power of 2, in order to avoid rounding of logarithms. One can easily generalize all the results for arbitrary $n$ , preserving asymptotic efficiency measures.

As usually assumed in the algorithmic literature on radio networks, nodes communicate in synchronous rounds (also called steps). All nodes start executing an algorithm in the same round. In each round, a node can either transmit a message to all its neighbors, or stay silent and listen. At the receiving end, a node $v$ hears the message from a neighbor $w$ in a given round, if $v$ listens in this round, and if $w$ is its only neighbor that transmits in this round. If more than one neighbor of a node $v$ transmits in a given round, there is a collision at $v$ . Two scenarios concerning collisions were considered in the literature. The availability of collision detection means that node $v$ can distinguish collision from silence which occurs when no neighbor transmits. If collision detection is not available, node $v$ does not hear anything in case of a collision (except the background noise that it also hears when no neighbor transmits). We do not assume collision detection. The time of a deterministic algorithm for a given task is the worst-case number of rounds it takes to solve it, expressed as a function of various network parameters.

If nodes are indistinguishable (anonymous), i.e., in the absence of any labels, none of our communication problems can be solved, for example, in the four-cycle. Hence we consider labeled networks, i.e., we assign binary strings, called labels, to nodes. A labeling scheme for a given network represented by a graph $G=(V,E)$ is any function ${\mathcal{L}}$ from the set $V$ of nodes to the set $S$ of finite binary strings. The string ${\mathcal{L}}(v)$ is called the label of the node $v$ . Labels assigned by a labeling scheme are not necessarily distinct. The length of a labeling scheme ${\mathcal{L}}$ is the maximum length of any label assigned by it. Every node knows a priori only its label, and can use it as a parameter in the same deterministic algorithm

Solving distributed network problems with short labels can be seen in the framework of algorithms with advice. In this paradigm that has recently got growing attention, an oracle knowing the network (and, for some problems, some distinguished node(s) of the network) gives advice to nodes not knowing it, in the form of binary strings, provided to nodes before the beginning of a computation. A distributed algorithm uses this advice to solve the problem. The required size of advice (maximum length of the strings) can be considered a measure of the difficulty of the problem. Two variations are studied in the literature: either the binary string given to nodes is the same for all of them [19] or different strings may be given to different nodes [11, 10, 12, 13], as in the case of the present paper. If strings may be different, they can be considered as labels assigned to nodes by a labeling scheme. Such labeling schemes permitting to solve a given network task efficiently are also called informative labeling schemes. One of the famous examples of using informative labeling schemes is to answer adjacency queries in graphs [2].

Several authors have studied the minimum amount of advice (i.e., label length) required to solve certain problems (see the subsection Related work). The framework of advice permits us to quantify the minimum amount of information used to solve a given network problem, regardless of the type of information that is provided. Note that the scenario of the same advice given to all (otherwise anonymous) nodes would be useless in the case of radio networks: no deterministic communication could occur.

We now define formally our two communication tasks in a radio network $G=(V,E)$ .

$\blacksquare$

Broadcasting: One node of the graph, called the source, has a broadcast message that has to reach all nodes $v\in V$ . A node which already knows the broadcast message is called an informed node, otherwise the node is uninformed. If a node $v$ receives the broadcast message for the first time in round $r$ , from some neighbor $u$ , we say that $u$ informed $v$ in round $r$ . An uninformed node $v$ is a frontier node in a given round, if it is a neighbor of an informed node. In our broadcasting algorithms, only informed nodes send messages.
$\blacksquare$

Gossiping: Each $v\in V$ has a message, and all messages have to reach all nodes in $V$ .

As it is customary in algorithmic literature concerning radio networks, we assume that when a node sends a message, this message can be of arbitrary size. In particular, a node could send its entire history (however, in our algorithms, messages will be usually shorter: in broadcasting, some control messages will be appended to the source message, and in gossiping, all messages already known to a node will be combined in a single message).

Now our goal can be succinctly formulated as follows:

For the above tasks, find an optimal-length labeling scheme permitting to accomplish this task, and design an optimal-time algorithm using a scheme of optimal length.¹¹1For the task of broadcasting, constant-length labeling schemes are known, so in this case the goal is to find a scheme of constant length supporting an optimal-time broadcasting algorithm.

Our results

Our main result concerns broadcasting. We improve the best currently known time of deterministic broadcasting using labeling schemes of constant length, due to Ellen and Gilbert (SPAA 2020) [10]. As in [10], our results are of two types: constructive, where the labeling scheme used by the algorithm is explicitly constructed using an algorithm polynomial in $n$ , and non-constructive, where we only prove the existence of the labeling scheme used by the algorithm, via the probabilistic method. The broadcasting algorithm from [10] using a constructive constant-length labeling scheme runs in time $O(D\log^{2}n)$ . We improve it to time $O\left(D+\min(D,\log n)\cdot\log^{2}n\right)$ . The broadcasting algorithm from [10] using a non-constructive constant-length labeling scheme runs in time $O(D\log n+\log^{2}n)$ . We improve it to time $O(D+\log^{2}n)$ . This latter time is, in fact, the optimal deterministic broadcasting time in radio networks of known topology.²²2This means that every node has an isomorphic copy of the graph, with nodes labeled in the same way by unique identifiers, and a node knows its identifier. Deterministic algorithms using such knowledge are called centralized.. Hence, we show that appropriately chosen node labels of constant length permit us to achieve, in a deterministic distributed way, the optimal centralized broadcasting time. This is, perhaps, the most surprising finding of this paper. We are able to obtain our result thanks to a novel tool that we call a 2-height respecting tree. The properties of these crucial objects permit us to implement centralized communication techniques in the distributed context.

It should be mentioned that messages used by both our broadcasting algorithms contain the source message and a constant number of control bits.

Next, we apply our broadcasting algorithm to solve the gossiping problem. Using the non-constructive version of our result for broadcasting, we get an algorithm working in time $O(D+\Delta\log n+\log^{2}n)$ , that uses a (non-constructive) labeling scheme of optimal length $O(\log\Delta)$ .³³3Using only constructive labeling schemes, the polylogarithmic summand in our complexity of gossiping changes from $\log^{2}n$ to $\min(D,\log n)\log^{2}n$ . Our time is the same as the best known gossiping time for radio networks of known topology (without any extra assumptions on parameters), that follows from [16].

We summarize our results and compare them with previous ones in Table 1, Appendix A. Due to lack of space, many proofs and details are postponed to the full version of the paper.

Related work

Broadcasting and gossiping in radio networks were extensively investigated in algorithmic literature. For deterministic algorithms, two important scenarios were studied. The first concerns centralized algorithms, in which each node knows the topology of the network and its location in it. Here, an optimal-time broadcasting algorithm was given in [16, 22] and the best known gossiping time (without any extra assumptions on parameters) follows from [16]. For large values of $\Delta$ , this was later improved in [7]. The second scenario concerns distributed algorithms, where nodes have distinct labels, and every node knows its own label and an upper bound on the size of the network but does not know its topology. Here the best known broadcasting time that depends only on $n$ is $O(n\log n\log\log n)$ [23], later improved in [8] for some values of parameters $D$ and $\Delta$ . For gossiping, the best known time in arbitrary directed (strongly connected) graphs was given in [15, 17] and the best known time for undirected graphs follows from [25]. Randomized distributed broadcasting was studied in [21, 9], where optimal $O(D\log(n/D)+\log^{2}n)$ time algorithms were obtained independently. For gossiping, optimal randomized time was given in [18].

The advice paradigm has been applied to many different distributed network tasks: finding a minimum spanning tree [12], finding the topology of the network [13], and leader election [19]. In [11] and [10], the task was broadcasting in radio networks, as in the present paper. In the above papers, advice was given to nodes of the network. Other authors considered the framework of advice for tasks executed by mobile agents navigating in networks, such as exploration [20] or rendezvous [24]. In this case, advice is given to mobile agents.

Organization of the paper

We present a high-level description of our results in Section 2. Section 3 introduces the notion of a $2$ -height respecting tree (2-HRT) and the proof that one can build a BFS tree of each graph which is a 2-HRT, the result essential for our broadcasting algorithms. In Section 4, we focus on broadcasting. Section 5 is devoted to gossiping.

2 High-level Description of our Results

2.1 High-level description of broadcasting

Our algorithms for broadcasting combine three mechanisms. The first two of them are taken from the literature, and the third, which is our main technical contribution, permits us to improve the time complexity of broadcasting.

1. The domination mechanism from [11]

Computation is split into blocks of some constant number of rounds. At the beginning of block $r$ , a fixed set $\mathbf{DOM}_{r}$ of nodes is active which is a minimal set of informed nodes with respect to inclusion that covers all frontier nodes. All elements of $\mathbf{DOM}_{r}$ simultaneously transmit in the first round of the block called the Broadcast step. Minimality of $\mathbf{DOM}_{r}$ guarantees that each $v\in\mathbf{DOM}_{r}$ informs at least one uninformed node. For each $v\in\mathbf{DOM}_{r}$ , the labeling algorithm chooses exactly one such node $v^{\prime}$ informed by $v$ in block $r$ as the feedback node of $v$ in that block.

Importantly, all feedback nodes can transmit simultaneously messages received by the nodes which serve as their witnesses. These feedback nodes transmit in the second round of the block, called the Feedback step. Their messages contain some information stored in their labels which instruct the corresponding nodes from $\mathbf{DOM}_{r}$ whether they should stay in $\mathbf{DOM}_{r+1}$ and instruct them about their behaviour in the remaining steps of the current block $r$ .

Nodes informed until block $r$ which are outside of $\mathbf{DOM}_{r}$ remain inactive to the end of an execution of the algorithm. The intuition regarding this property is the fact that a node $v$ outside of $\mathbf{DOM}_{r}$ does not have its feedback node to instruct $v$ about its actions. On the other hand, $v$ cannot store this information in its own label for many blocks of computation, because it would require non-constant size of labels.

As each block extends the set of informed nodes, the domination mechanism guarantees broadcasting in $O(n)$ time.

2. The propagation mechanism from [10]

In order to accelerate propagation of the broadcast message in the case when the diameter $D$ of the input graph is $o(n)$ , ideas from a randomized seminal distributed algorithm of Bar-Yehuda et al. [3] are applied. Namely, for appropriate random choices of informed nodes whether to transmit in a particular round, one can assure that the broadcast message is passed to the next level of a BFS tree rooted at the source node $s$ in $O(\log n)$ rounds in expectation. This in turn gives randomized broadcasting in $O(D\log n+\log^{2}n)$ rounds with high probability.

These random choices of nodes are mimicked in the labels of nodes. More precisely, the labels store some 0/1 random choices whether to transmit in a given block, assuring a given time bound. In particular, the feedback node of a node $v\in\mathbf{DOM}_{r}$ stores, in the bit Go of its label, information whether $v$ should transmit. Then, the nodes from $\mathbf{DOM}_{r}$ which received Go=1 transmit the broadcast message in the separate Go step of the block $r$ . The labeling scheme obtained in this way is non-constructive. Using ideas from [4] regarding centralized broadcasting in arbitrary bipartite graphs, one can obtain a constructive labeling scheme. However, the time of the broadcasting algorithm such a scheme would support becomes $O(D\log^{2}n)$ instead of time $O(D\log n+\log^{2}n)$ supported by the non-constructive scheme.

3. The fast tracks mechanism

This mechanism is the main novelty of our solution and permits us to improve the broadcasting time from [10]. The goal here is to implement ideas of a fast centralized algorithm into constant-size advice such that a distributed algorithm can somehow simulate the centralized one. The key ingredient of our approach is illustrated by the notion of a 2-height respecting trees (2-HRT) and the fact that there exists a BFS tree which is also 2-HRT, for each graph. The 2-height of a node $v$ in a tree intuitively denotes the maximum number of “critical branches” (causing large congestion) on a path from $v$ to a leaf. The maximum 2-height is always at most $\log n$ . Each time the 2-height of a node $v$ and of some child $w$ of $v$ are the same, transmission of a message from $v$ to $w$ can be made in parallel with other similar transmissions from the level of $v$ dedicated to the particular value of $2$ -height. Therefore, such an edge connecting $v$ and $w$ with equal $2$ -heights is called a fast edge. As all but $\log n$ edges on each path from the root to a leaf are fast, the centralized algorithm from [16] accomplishes broadcast in almost optimal time $O(D+\log^{3}n)$ . With this aim, the authors of [16] make use of the notion of gathering trees which somehow minimize collisions between fast edges. Our notion of a 2-HRT imposes stronger requirements than gathering trees, making fast transmissions even more parallelizable. Then, the key challenge is an implementation of the idea of a centralized algorithm by constant-size labels instructing nodes of a distributed algorithm how to simulate the centralized algorithm. The main obstacle here comes from the domination mechanism which switches off some nodes irreversibly, preventing them from transmitting any message starting from the block $r$ in which they are outside of the minimal dominating set $\mathbf{DOM}_{r}$ . We show that, for each such node, one can determine its “rescue node” still present in the dominating set, such that its transmission on behalf of a switched off node does not cause additional collisions.

Our final solution using this mechanism gives a non-constructive labeling scheme of constant length, supporting broadcasting in time $O(D+\log^{2}n)$ , which is optimal, even for centralized algorithms. Using the technique from [4] we can build labels constructively at the cost of increasing the time complexity of broadcasting to $O\left(D+\min(D,\log n)\cdot\log^{2}n\right)$ .

2.2 High-level description of gossiping

We introduce the auxiliary task of gathering: each node of the graph has a message, and all messages have to reach a node called the sink. We provide a gathering algorithm working in time $O(D+\Delta\log n+\log^{2}n)$ and using a labeling scheme of optimal length $O(\log\Delta)$ .

With this aim, we make use of properties of a 2-HRT to implement the centralized algorithm for gathering from [16] in a distributed way, using short labels. Let $T$ be a BFS tree of the input graph which is also a 2-HRT. The centralized algorithm from [16] determines the unique round $t(v)$ in which each node $v$ transmits all messages from its subtree of $T$ ⁴⁴4The authors of [16] use the notion of gathering trees in their paper, but 2-HRT satisfy all properties of gathering trees as well. to the parent of $v$ without a collision. These collision-free transmissions are assured by the properties of gathering trees from [16] which are also satisfied by 2-HRT. The value of $t(v)$ depends on parameters $D$ , $\textit{level}(v)$ , $h_{2}(v)\in[0,\log n]$ , $\Delta$ and on some auxiliary label $s(v)\in[0,\Delta]$ . Thus, while $\Delta$ and $s(v)$ can be encoded in the label of $v$ using $O(\log\Delta)$ bits, we cannot store $D$ , $h_{2}(v)$ and $\textit{level}(v)$ in the label of length $O(\log\Delta)$ . With this aim we use a modified Size Learning Algorithm from [14] followed by an acknowledged broadcasting algorithm to share information about the value of $D$ among all nodes and assure that nodes learn their levels during an execution of the broadcasting algorithm. Finally, each leaf is marked as such by an appropriate bit of its label. The fact that a node $v$ is a leaf implies also that $h_{2}(v)=0$ . Other nodes learn their values of $h_{2}$ by modifying the maximal values of $h_{2}$ of their children.

Our solution of the gossiping problem works as follows. First, we gather all messages in an arbitrary node $s$ , executing our gathering algorithm. Then, all messages collected at $s$ are distributed using our broadcasting algorithm. An obstacle which arises in implementing this idea is caused by the fact that all nodes have to be coordinated so that they know when the consecutive subroutines of the final algorithm start. We overcome this difficulty by using an acknowledged broadcasting.

3 $2$ -height Respecting Trees

For a rooted tree $T$ with the root node $s$ , we denote the parent of a node $v\neq s$ as $\textit{p}(v)$ . The level of a node $v$ in the tree $T$ is equal to its distance to the root $s$ . The level of $v$ is denoted as $\textit{level}(v)$ . Thus, in particular, $\textit{level}(s)=0$ . For a fixed graph $G=(V,E)$ and a node $s\in V$ , the set of nodes at distance $l\geq 0$ from $s$ will be called the level $l$ and denoted as $L_{l}$ . Thus, in particular, $L_{0}=\{s\}$ , $L_{1}$ is the set of neighbors of $s$ and $L_{l}=$ $\{v\,|\,\textit{level}(v)=l\}$ .

Now, we define the notion of a 2–height respecting tree (2-HRT), resembling gathering trees introduced in [16]. However, it is important to note that 2–height respecting trees must satisfy stronger properties than gathering trees. That is, each 2-HRT is a gathering tree while a gathering tree might not be a 2-HRT.

Definition 1 (2-height, fast edge, slow edge).

The 2-height of a node $v$ of a rooted tree $T$ , denoted as $h_{2}(v)$ , is defined as follows:

$\blacksquare$

If $v$ is a leaf then $h_{2}(v)=0$ .
$\blacksquare$

If $v$ is not a leaf, it has the children $u_{1},u_{2},\dots,u_{k}$ for $k\geq 1$ and there is exactly one node $u_{i}$ such that $h_{2}(u_{i})=\max_{j}\{h_{2}(u_{j})\}_{j\in[k]}$ then $h_{2}(v)=\max_{j}\{h_{2}(u_{j})\}_{j\in[k]}$ .
$\blacksquare$

If $v$ is not a leaf, it has the children $u_{1},u_{2},\dots,u_{k}$ for $k\geq 1$ and there are two or more nodes $u_{i}$ such that $h_{2}(u_{i})=\max_{j}\{h_{2}(u_{j})\}_{j\in[k]}$ then $h_{2}(v)=\max_{j}\{h_{2}(u_{j})\}_{j\in[k]}+1$ .

If $h_{2}(v)=h_{2}(\textit{p}(v))$ in a rooted tree $T$ then the edge $(p(v),v)$ in $T$ is called a fast edge. Otherwise, the edge $(p(v),v)$ is a slow edge.

Definition 2 (2-height respecting tree).

A rooted tree $T$ is a $2$ -height respecting tree (2-HRT for short) of a graph $G$ if it is a BFS Tree of $G$ satisfying the following property:

( $\star$ ): For each two nodes $u,u^{\prime}$ such that $\textit{level}(u)=\textit{level}(u^{\prime})$ and $h_{2}(u)=h_{2}(u^{\prime})=h_{2}(\textit{p}(u))=h_{2}(\textit{p}(u^{\prime})),$ there is no common neighbor $v$ of $u$ and $u^{\prime}$ in $G$ such that $\textit{level}(v)=\textit{level}(u)-1=\textit{level}(u^{\prime})-1$ .

The key difference between gathering trees from [16] and $2$ -height respecting trees is that the nodes $u$ and $u^{\prime}$ on the same level such that $h_{2}(u)=h_{2}(u^{\prime})=h_{2}(\textit{p}(u))=h_{2}(\textit{p}(u^{\prime}))$ cannot have the same parent, i.e., $\textit{p}(u)\neq\textit{p}(u^{\prime})$ in the case of gathering trees, while they cannot even have a common neighbor on the level $\textit{level}(u)-1$ in the case of 2-HRT. The following key lemma shows that, for each graph $G=(V,E)$ and each of its nodes $s\in V$ , a 2-HRT of $G$ rooted in $s$ can be constructed in polynomial time.

Lemma 3.

For every graph $G=(V,E)$ and each $s\in V,$ one can construct a BFS spanning tree $T$ of $G$ rooted at $s$ such that $T$ is a 2-HRT. Moreover, the tree $T$ can be constructed in time $\text{poly}(n)$ .

The high-level idea of the proof is that an arbitrary BFS tree of a graph can be gradually transformed into a 2-HRT such that it still is a BFS spanning tree of the input graph. The transformation goes level by level, starting from the largest ones. In order to show that the gradual changes eventually lead to the construction of a 2-HRT in polynomial time, we introduce a kind of potential function which measures to which extent edges at a particular level might potentially break requirements of a 2-HRT and we show that each change of the tree decreases the value of this function.

4 Broadcasting Algorithms

This section is devoted to the broadcasting problem. We start with the description of a modified variant of the Executor Algorithmfrom [10], called Levelled Executor Algorithm. It extends the original algorithm so that only nodes from specific levels can transmit and listen in particular rounds. Subsequently, this algorithm will be improved to get our final result. Table 2 (p. 2) compares algorithms from [11, 10] to our algorithms presented in this section.

4.1 Levelled Executor Algorithm

A broadcasting algorithm is a levelled algorithm, if each node on level $l>0$ accepts the broadcast message (i.e., considers it as received) only if it is received from a node on level $l-1$ . Observe that, in order to incorporate such requirement, it is necessary to provide to nodes information which permits them to deduce the level of a node from which they receive the broadcast message.

We present the Levelled Executor Algorithmbelow and state its properties. First, we modify the Executor Algorithmso that it becomes a levelled algorithm, while preserving time complexity and various other properties of the Executor Algorithm.

The Executor Algorithmcombines the dominating set mechanism introduced in [11] with the propagation mechanism from [10]. An execution of the algorithm is divided into blocks, each consisting of 3 steps: Broadcast, Feedback and Go. Let $r$ be the number of the current block and let $\mathbf{INF}_{r}$ and $\mathbf{UNINF}_{r}$ be respectively the sets of informed nodes and uniformed nodes at the beginning of the block $r$ . In the block $r$ we keep some minimal set $\mathbf{DOM}_{r}$ of informed nodes which dominates frontier nodes, i.e., uninformed neighbors of informed nodes. Formally, $\mathbf{DOM}_{r}$ is a minimal subset of $\mathbf{INF}_{r}$ with respect to inclusion, such that, for each node $v\in\mathbf{UNINF}_{r}$ , if there exists a neighbor $u\in\mathbf{INF}_{r}$ of $v$ , then there is some neighbor $u^{\prime}$ of $v$ in the dominating set $\mathbf{DOM}_{r}$ .

The labels of nodes for the Executor Algorithmare assigned gradually during a simulation of the algorithm on a given input graph. They consist of three bits called Join, Stay and Go. As it might be seen as a simulation of a randomized distributed algorithm based on ideas from [3], we assign the values of some bits of the labels randomly. However, as the simulated distributed algorithm accomplishes broadcast in the claimed number of rounds with high probability, one can assign those bits by simulating all possible random choices of the randomized algorithm and fixing the choices assuring the given round complexity. At the beginning we set $\mathbf{DOM}_{0}=\{s\}$ , where $s$ is the source node. In the Broadcast step of the block $r$ , all nodes in $\mathbf{DOM}_{r}$ transmit their messages. We preserve the invariant that each node is always aware if it belongs to $\mathbf{DOM}_{r}$ in the current block $r$ . As $\mathbf{DOM}_{r}$ is minimal, there will be at least one node newly informed only by $v$ for each node $v$ from $\mathbf{DOM}_{r}$ . One of the nodes informed by $v$ in block $r$ is chosen to be the Feedback Node of $v$ in that block.

All newly informed Feedback Nodes send their values of Stay and Go bits in the Feedback step of the block, provided that at least one of them (Stay or Go) is equal to $1$ . If the Feedback Node of $v$ sends the value $\mathit{Go}=1$ then $v$ will also broadcast in the “bonus” Go step of the block. The value of Go bit is chosen at random by the oracle for all Feedback Nodes. Finally, $v$ will stay in the dominating set $\mathbf{DOM}_{r+1}$ if and only if the $\mathit{Stay}$ bit of its feedback node is equal to 1.⁵⁵5As no node $v$ has the centralized view of the progress of the algorithm allowing it to determine whether in belongs to the set $\mathbf{DOM}_{r}$ in the current block $r$ , we provide this information to nodes through labels. Each newly informed node joins the dominating set $\mathbf{DOM}_{r+1}$ if its Join bit is equal to $1$ .

In order to transform the Executor Algorithminto a Levelled Executor Algorithm, we associate a new variable $\textit{Lev}(v)$ with each node $v$ which is equal the value of the distance from the source node $s$ to $v$ modulo $3$ . (That is, $\textit{Lev}(v)=\textit{level}(v)\mod 3$ .) The value of $\textit{Lev}(v)$ can be stored as two bits of the label of $v$ . Assume that the current block is $r$ such that $r\mod 3=x$ . Then, only nodes from the current dominating set with $\mathit{Level}$ equal to $x$ transmit in Broadcast and Go Steps of the block $r$ , and listen in the Feedback step. Moreover, only nodes with $\mathit{Level}$ value equal to $(x+1)\mod 3$ listen in the Broadcast, Go steps and transmit in the Feedback step. In order to adjust this change to the standard Executor Algorithmpreserving the general meaning of the sets $\mathbf{DOM}_{r}$ , $\mathbf{INF}_{r}$ and $\mathbf{UNINF}_{r}$ , we must also redefine the sets $\mathbf{DOM}_{r}$ , $\mathbf{INF}_{r}$ and $\mathbf{UNINF}_{r}$ so that, for $r\mod 3=x$ , one is looking only at edges where informed nodes are at such levels $l$ that $l\mod 3=x$ and, for an informed node at level $l$ , only its uninformed neighbors at level $l+1$ are considered.

The final label for each node $v$ is the tuple consisting of four elements: Join, Lev, Stay and Go. Join is the bit indicating whether $v$ should join the dominating set when it receives the broadcast message for the first time from a node at the level preceding the level of $v$ and remain in the dominating set for the next $3$ blocks (recall that nodes are active as informed ones only in one of each three blocks in the Levelled Executor Algorithm). Lev is the distance from the root to $v$ modulo $3$ . Assume that $v$ is informed in the block $r$ such that $\textit{Lev}(v)=(r+1)\mod 3$ . If $v$ is chosen as the feedback node of some node $w$ which informed $v$ then

$\blacksquare$

Stay is the bit indicating whether $w$ should stay in the dominating set $\mathbf{DOM}_{r+3}$ .
$\blacksquare$

Go is the bit indicating whether $w$ should broadcast in the Go step of the block $r$ .

If $v$ is not a feedback node of any other node then the bits Stay and Go are set to $0$ . Finally, $v$ sends the bits Stay and Go in the Feedback step of block $r$ if Stay=1 or Go=1.

At the beginning we assign the label $(1,0,0,0)$ to the source node $s$ . The labels of all other nodes are initiated to zeroes and they will be assigned gradually during a simulation of the final distributed algorithm using those labels, as described above.

By a slight modification of the proof of Th. 12 from [10], one can show the following non-constructive result.

Theorem 4 ([10]).

There exists a labeling scheme of constant length for which the Levelled Executor Algorithmfinishes broadcast in $O(D\log n+\log^{2}n)$ rounds.

The essential properties of the algorithm that make a generalization of the proof from [10] possible are that the levelled variant of the algorithm guarantees that the set of informed nodes is extended in each Broadcast step and the probability of setting Go such that frontier nodes receive the broadcast message in the Go step satisfy conditions from the original analysis. The details will be given in the full version of the paper.

Using the graph-theoretic result from [4] and the algorithmic technique of maximization of expectation, one can show that the result of Th. 4 might be turned into a constructive one at the cost of increasing its complexity to $O(D\log^{2}n)$ rounds.

4.2 Fast Broadcast Algorithm: Linear Dependency on $𝑫$

In this section, we extend the labeling scheme and modify the Levelled Executor Algorithmin order to improve its complexity to $O(D+\min(D,\log n)\log^{2}n)$ . The linear dependency on $D$ is clearly optimal, and the second summand will be improved later. The resulting algorithm is called Fast Broadcast Algorithm.

We build labels gradually starting from zero labels, by simulating the broadcasting algorithm step by step. The final algorithm works in the framework of the Levelled Executor Algorithm. We introduce special shortcut edges, as described by Gasieniec et al. [16]. All but $O(\log n)$ edges are such shortcuts on each path from the source of a BFS tree which is a 2-HRT. These shortcut edges correspond to fast edges of a 2-height respecting BFS spanning tree of the communication graph.

One can refer to [16, 6] for the proof of the following lemma.

Lemma 5 ([6]).

For every tree of size $|V|=n$ the maximum value of 2-height is $\leq\log n$ .

As $h_{2}(\textit{p}(v))\leq h_{2}(v)+1$ , the maximum value of $2$ -height is not larger than the height of a tree. Moreover, as the height of a BFS tree of $G=(V,E)$ is $\leq D$ , we have the following corollary.

Corollary 6.

For a BFS spanning tree of a graph $G=(V,E)$ , the max. $2$ -height is $\leq\min(D,\log n)$ .

Our algorithm works in blocks which consist of a fixed constant number of steps. It uses the labels for the Levelled Executor Algorithmand performs its standard steps along with some additional steps, as well as some additional bits of the labels are added in order to accelerate the broadcasting process, partially using some ideas of the centralized broadcasting from [16]. To this aim, we start by building a BFS tree $T$ of the input graph with the source vertex $s$ as the root of $T$ , which is a 2-HRT, see Lemma 3. (Let us stress here that a 2-height respecting tree must satisfy stricter requirements than the so-called gathering spanning trees from [16], and this difference is essential for our labeling scheme and for the distributed algorithm.) Then, we follow the framework of the Levelled Executor Algorithmextended in such a way that:

$\blacksquare$

Each block is extended by rounds Fast and Rescue which accelerate the broadcasting through non-colliding shortcut/fast edges, so that the $2$ -height of a node and its child are equal.
$\blacksquare$

In order to instruct nodes about their actions in these new steps in blocks, we also add two extra bits to their labels, called the Fast bit and the Rescue bit. As it turns out, facilitating these transmissions without collisions faces significant challenges which we overcome by taking advantage of the fact that $T$ is a $2$ -height respecting tree.

First, for each node $v$ we define the ultimate block number $x(v)$ of $v$ as follows

x(v)=3\cdot\left(\textit{level}(v)+30\lceil\log^{2}n\rceil(h_{2}(s)-h_{2}(v))% \right)+\left((\textit{level}(v)-1)\mod 3\right).

(1)

We will now build the rest of the algorithm to ensure that $x(v)$ is an upper bound on the number of the block when $v$ is informed, i.e., when it receives the broadcast message for the first time, and this received message is transmitted from a node on the level $\textit{level}(v)-1$ .

To achieve the above goal, we set the bits Fast and Rescue so that their values instruct nodes about their actions in the Fast and Rescue steps respectively. Initially all bits Fast and Rescue are set to $0$ which means that (initially) no nodes are supposed to transmit in the new steps Fast and Rescue of any block. Additionally, for each $u$ , $v$ such that $u$ is the feedback node of $v$ in some block, apart from its Stay and Go bits, $u$ will also transmit its values of Fast and Rescue bits to $v$ in the appropriate Feedback step.

A node $v\in\mathbf{DOM}_{r}$ such that $\textit{Lev}(v)=r\mod 3$ (i.e., informed in a block $r^{\prime}<r$ ) transmits in Fast (respectively Rescue) step of the current block if the value of received Fast (respectively Rescue) bit transmitted to $v$ (in the Feedback step) by its current feedback node is equal to $1$ .

Below, we describe assignments of the bits Fast and Rescue in more detail.

If $h_{2}(v)\neq h_{2}(\textit{p}(v))$ or $\textit{p}(v)$ has not received the broadcast message until the round $x(v)>x(p(v))$ (see the definition of $x(v)$ ), no change of the values of the bits Fast or Rescue are caused by $v$ . Similarly, if the node $v$ receives the broadcast message before the block $x(v)$ then it does not cause change of bits Fast, Rescue of any node.

So let $v$ be a node such that $h_{2}(v)=h_{2}(\textit{p}(v))$ , i.e., it is connected to its parent by a fast edge. Additionally assume that: the node $v$ has not received the broadcast message from $\textit{p}(v)$ until the beginning of the block $x(v)$ but $\textit{p}(v)$ received the broadcast message in the block $x(\textit{p}(v))$ or earlier.

Consider the following cases regarding the status of node $p(v)$ at the beginning of block $x(v)$ :

Case 1.: The node $\textit{p}(v)$ was informed before the block $x(v)$ and it is in the dominating set $\mathbf{DOM}_{x(v)}$ of the block $x(v)$ of the algorithm.

Then $\textit{p}(v)$ has some feedback node $w$ first informed in the block $x(v)$ . We set $F a s t$ bit of $w$ to $1$ .
Case 2.: The node $\textit{p}(v)$ was informed before the block $x(v)$ but it is not in the dominating set $\mathbf{DOM}_{x(v)}$ of the block $x(v)$ of the algorithm.

As $v$ is still not informed before the block $x(v)$ , there must be a neighbor $u$ of $v$ in the dominating set $\mathbf{DOM}_{x(v)}$ with $\textit{level}(u)=\textit{level}(\textit{p}(v))$ (see Sec. 4.1). Then, as $u$ is in $\mathbf{DOM}_{x(v)}$ , it has some feedback node $w$ first informed, by $u$ , in the block $x(v)$ . We set the Rescue bit of $w$ to $1$ .

We express properties of the algorithm following from the assignment of the bits Fast and Rescue and the actions of nodes caused by these settings in the following observation.

Observation 7.

1.

A node $v$ transmits in the Fast step of a block $b$ if and only if $b=x(v^{\prime})$ for a child $v^{\prime}$ of $v$ such that $h_{2}(v^{\prime})=h_{2}(v)$ and $v^{\prime}$ is not informed before the block $b$ .
2.
Let $V_{b}$ be the set of nodes which transmit in the Rescue step of a block $b$ and let $V^{\prime}_{b}$ be the set of such nodes $v^{\prime}$ which are uninformed before the block $b$ , $x(v^{\prime})=b$ and their parents are not in the dominating set $\mathbf{DOM}_{b}$ . Then, there exists a 1-to-1 assignment $\phi_{b}:V_{b}\to V^{\prime}_{b}$ such that, for $v\in V_{b}$ and $v^{\prime}=\phi_{b}(v)$ ,
1. (a)
  
  $\textit{level}(v^{\prime})=\textit{level}(v)+1$ ,
2. (b)
  
  $(v,v^{\prime})\in E$ ,
3. (c)
  
  $v^{\prime}$ is connected with its parent $p(v^{\prime})$ by a fast edge, i.e., $h_{2}(v^{\prime})=h_{2}(\textit{p}(v^{\prime}))$ .

As the above described Fast Broadcast Algorithm is an extension of the Levelled Executor Algorithmby adding extra transmissions in each block, the correctness of the new algorithm follows directly from the correctness of the Levelled Executor Algorithmassured by the domination mechanism. To obtain a bound on the time of the new algorithm, we prove the following lemma.

Lemma 8.

A node $v$ becomes informed by the end of block $x(v)$ , for each $v\in V$ .

Proof.

We prove the lemma by induction on $x(v)$ . The base regards only $s$ which is informed in round $0$ . For the inductive step, consider an arbitrary value $x>0$ and any node $v$ such that $x(v)=x$ . Assume that the lemma holds for all nodes $u$ such that $x(u)<x$ . As $x(v)>0$ , the node $v$ is not the source node $s$ . So the parent $\textit{p}(v)$ is defined in this case. As $\textit{level}(v)=\textit{level}(\textit{p}(v))+1$ and $h_{2}(v)\leq h_{2}(\textit{p}(v))$ , we know that $x(\textit{p}(v))<x(v)=x$ . Therefore, by the inductive hypothesis, $\textit{p}(v)$ was informed until the block $x(\textit{p}(v))<x=x(v)$ . Consider the following cases:

Case I: $h_{2}(v)<h_{2}(\textit{p}(v))$ .

As 2-heights of $v$ and $\textit{p}(v)$ are different and the values of $x(v)$ and $x(\textit{p}(v))$ differ by more than $90\lceil\log^{2}n\rceil$ (see (1)) which means that $p(v)$ is active in at least $30\log^{2}n$ blocks of the levelled algorithm between the blocks $x(v)$ and $x(p(v))$ . Then, by Corollary 17, as $\textit{p}(v)$ gets informed until the block $x(\textit{p}(v))$ , in view of the inductive hypothesis, $v$ gets informed by the block $x(\textit{p}(v))+90\lceil\log^{2}n\rceil=x(v)$ .

Case II: $h_{2}(v)=h_{2}(\textit{p}(v))$ .

If the node $v$ is informed before the block $x(v)$ , we are done. If not, we will inspect carefully Cases 1–2 presented above in the description of the algorithm.

For Case 1, observe that the node $\textit{p}(v)$ sends the broadcast message in the Fast step of the block $x(v)$ – see Observation 7.1. Thus, it is sufficient to show that $v$ receives this message transmitted by $\textit{p}(v)$ in the Fast step of the block $x(v)$ . To get a contradiction, assume that there is another node $w$ transmitting in the Fast step of the block $x(v)$ , such that $w\neq\textit{p}(v)$ is a neighbor of $v$ and therefore its transmission causes collision at $v$ in the Fast step of the block $x(v)$ – see Figure 1. By Observation 7.1, there exists $w^{\prime}$ connected to $w$ such that:

$\blacksquare$

$w^{\prime}$ is a child of $w$ connected to $w$ by a fast edge, and thus $h_{2}(w)=h_{2}(w^{\prime})$ ;
$\blacksquare$

$x(v)=x(w^{\prime})$ (since $w=\textit{p}(w^{\prime})$ transmits in the block $x(w^{\prime})$ which is the same as the transmission block of $p(v)$ equal to $x(v)$ ) and, as $\textit{level}(v)=\textit{level}(w^{\prime})$ , the equality $h_{2}(v)=h_{2}(w^{\prime})$ also holds.

The above relationships imply not only that $\textit{level}(\textit{p}(v))=\textit{level}(w)$ but also $h_{2}(\textit{p}(v))=h_{2}(w)$ , since they are connected by fast edges with their children $v$ , $w^{\prime}$ such that $h_{2}(v)=h_{2}(w^{\prime})$ .

Figure 1: The cases in the analysis of our algorithm – Lemma 8.

Thus both $w^{\prime}$ and $v$ have the same 2-height as their respective parents. This final setting (see Fig. 1 again) implies that existence of the edges $(v,w)$ and $(w^{\prime},w)$ contradicts the requirement of the definition of a 2-HRT (see Definition 1).

We reason similarly for Case 2. Here $u$ , a neighbor of $v$ such that $\textit{level}(u)=\textit{level}(\textit{p}(v))$ (but $u\neq\textit{p}(v)$ in this case), sends the message in Rescue step of the block $x(v)$ by Obs. 7.2. To get a contradiction, assume that there is another node $w$ transmitting in the Rescue step of the block $x(v)$ such that $w$ is also a neighbor of $v$ – see Fig. 1. This fact implies in turn that $\textit{level}(\textit{p}(v))=\textit{level}(w)$ . Moreover, by Obs. 7.2 as $w$ is transmitting in Rescue step in the block $x(v)$ , $w$ must be a neighbor of some node $w^{\prime}$ with $x(w^{\prime})=x(v)$ , $\textit{level}(w^{\prime})=\textit{level}(v)$ and thus $h_{2}(w^{\prime})=h_{2}(v)$ . Additionally, $h_{2}(\textit{p}(w^{\prime}))=h_{2}(w^{\prime})=h_{2}(v)$ . But these properties imply that simultaneous existence of edges $(v,w)$ and $(w^{\prime},w)$ violates the requirements of the definition of a 2-HRT.

To summarize, we have proved that, if $\textit{p}(v)$ gets informed by the end of block $x(\textit{p}(v))$ , then $v$ gets informed by the end of block $x(v)$ . This concludes the inductive step of the proof. $\hfill\blacktriangleleft$

For each node $v$ , the value $x(v)$ is bounded by $3\cdot(D+30\lceil\log^{2}n\rceil h_{2}(s))+2\in O(D+\log^{3}n)$ . Since blocks are of constant length, Lemma 8 and Corollary 6 imply the following theorem.

Theorem 9.

The Fast Broadcast Algorithm accomplishes broadcast in
$O(D+\min(D,\log n)\log^{2}n)$ rounds, and uses a constructive labeling scheme.

4.3 Express Broadcast Algorithm– Optimization of the polylog Additive Summand

In this section, we describe a modification of the Fast Broadcast Algorithm which we call the Express Broadcast Algorithm. It runs in time only $O(D+\log^{2}n)$ , which is the optimal broadcasting time even for radio networks of known topology. A constant length labeling scheme for this optimal broadcasting can be assigned by an appropriate efficient randomized algorithm such that we obtain labels guaranteeing $O(D+\log^{2}n)$ broadcast with high probability. Thus, using the probabilistic method, we get a nonconstructive constant length labeling scheme supporting broadcasting in optimal time.

The Express Broadcast Algorithm is almost the same as the Fast Broadcast Algorithm, with the changed value of the ultimate block number and a random assignment of the values of bits Go. The random assignment of the bits Go is made similarly as in Theorem 4. (One can find details in Theorem 12 in [10]. We do not provide these details here since, for the purpose of our result, the existence of an appropriate setting of the bits Go is sufficient.) Note however that the change of the definition of the ultimate block number has an impact on the labeling of nodes. Thus, for a given communication graph, the labels for the Fast Broadcast Algorithm and the labels for the Express Broadcast Algorithm are usually different.

The ultimate block number $z(v)$ of a node $v$ is now defined as follows. $z(s)=1$ , for the source node $s$ , and for each $v\in V\setminus\{s\}$ , $z(v)$ is the minimum $z$ satisfying the following condition: $z\mod 6\lceil\log n\rceil=y(v)\mod 6\lceil\log n\rceil$ and $\textit{p}(v)$ becomes informed before block $z$ , where $y(v)=6\cdot\left(\textit{level}(v)+(h_{2}(s)-h_{2}(v))\right)+\left(level(v)-1% \right)\mod 3$ .

Observation 10.

If $z(u)=z(v)$ and $\textit{level}(u)=\textit{level}(v)$ then $h_{2}(u)=h_{2}(v)$ .

The labeling scheme for the Express Broadcast Algorithm and the algorithm itself are defined as for the Fast Broadcast Algorithm, with two differences in the labeling scheme:

$\blacksquare$

the assignment of the Fast, and Rescue bits of each node $v$ is determined by the values of $z(v)$ instead of $x(v)$ . More precisely, assume that $v$ has not received the broadcast message until the block $z(v)$ and $v$ is connected with its parent by a fast edge, i.e., $h_{2}(v)=h_{2}(\textit{p}(v))$ .

Consider the following cases regarding the status of the node $p(v)$ at the beginning of block $z(v)$ :

Case 1.

The node $\textit{p}(v)$ is in the dominating set $\mathbf{DOM}_{z(v)}$ .

Then $\textit{p}(v)$ has some feedback node $w$ informed in the block $z(v)$ . We set $F a s t$ bit of $w$ to $1$ .

Case 2.

The node $\textit{p}(v)$ is not in the dominating set $\mathbf{DOM}_{z(v)}$ .

As $v$ is still not informed before the block $z(v)$ , there must be a neighbor $u$ of $v$ in the dominating set $\mathbf{DOM}_{z(v)}$ with $\textit{level}(u)=\textit{level}(\textit{p}(v))$ . Then, as $u$ is in $\mathbf{DOM}_{z(v)}$ , it has some feedback node $w$ first informed in the block $z(v)$ . We will set Rescue bit of $w$ to $1$ .
$\blacksquare$

bits $G o$ are assigned as follows:

Define a feedback node of a block $r$ to be each node $v$ such that $v$ is a feedback node of some node $v^{\prime}\in\mathbf{DOM}_{r}$ in the block $r$ . For each block $r$ , choose the value $p_{r}\in\{1,\ldots,\log n\}$ randomly with uniform distribution. Then set the value of the bit Go to $1$ with probability $1/2^{p_{r}}$ for each feedback node of the block $r$ independently.

The behavior of nodes based on their labels is the same as in the Levelled Fast Broadcast Algorithm.

Lemma 11.

If $h_{2}(v)=h_{2}(\textit{p}(v))$ then $z(p(v))<z(v)\leq z(p(v))+7$ and $v$ receives the broadcast message by the end of block $z(v)$ .

Theorem 12.

The Express Broadcast Algorithm runs in time $O(D+\log^{2}n)$ whp.

Proof.

Let $u$ be an arbitrary node. We will show that $u$ becomes informed in $O(\textit{level}(v)+\log^{2}n)$ , rounds with probability at least $1-n^{-2}$ . This estimation combined with the union bound implies the result stated in the theorem.

We introduce the auxiliary notion of a fast track. It is a path $(v_{1},\ldots,v_{k})$ in $T$ such that

$\blacksquare$

$v_{i}=\textit{p}(v_{i+1})$ for each $i\in[1,k-1]$ ,
$\blacksquare$

$h_{2}(v_{1})=h_{2}(v_{2})=\cdots=h_{2}(v_{k})$ for each $i\in[1,k]$ ,
$\blacksquare$

$v_{1}=s$ or $(\textit{p}(v_{1}),v_{1})$ is a fast edge.

That is, all edges of a fast track are fast edges. Observe that, according to Lemma 11, if $(v_{1},\ldots,v_{k})$ is a fast track and $v_{1}$ receives the broadcast message in some block $b$ then $z(v_{k})=b+O(k)$ and $v_{k}$ receives the broadcast message by the end of block $z(v_{k})$ . As the maximum of $h_{2}(v)$ over all $v\in V$ is smaller than $\log n$ and the value of $h_{2}$ cannot increase on a simple path from the root $s$ to any node $v$ of $T$ , a path from $s$ to $v$ can be split into at most $\log n$ fast tracks and at most $\log n$ slow edges. As we have shown, the number of rounds needed for broadcasting a message along the fast tracks is linear with respect to the total length of these tracks which is $O(D)$ . Thus, it remains to analyze the number of rounds needed to pass the broadcast message through $h_{2}(v)-h_{2}(s)<\log n$ slow edges.

Recall that a feedback node of a block $r$ is each node $v$ such that $v$ is a feedback node of some node $v^{\prime}\in\mathbf{DOM}_{r}$ in the block $r$ . The random choice of the bits $G o$ assigned in labels of feedback nodes, described above, implies that, for each frontier node $w$ , $w$ receives the broadcast message in the Go step of the block $r$ with probability larger than $1/(30\log n)$ , as proved in Lemma 9 in [10].

Let $(s=v_{1},\ldots,v_{p}=v)$ be a path in $T$ from the root $s$ to some node $v$ . Let $b_{1},b_{2},\ldots$ be the sequence of blocks with the property that $b_{i}$ is the $i$ th block of an execution of our algorithm such that, at the beginning of the block $b_{i}$ , the largest index $j$ such that $v_{j}$ is informed is such that $(v_{j},v_{j+1})$ is a slow edge. For a fixed $i$ , let the index $j$ satisfying the properties from the previous sentence be denoted by $r_{i}$ . Let $X_{1},X_{2},\ldots$ be a sequence of independent random variables such that $X_{i}=1$ iff the node $v_{r_{i}+1}$ receives the broadcast message in the Go step of the block $b_{i}$ . Then $\text{Prob}(X_{i}=1)\geq 1/(30\log n)$ by Lemma 9 from [10]. Moreover, if $\sum_{i=1}^{a}X_{i}\geq h_{2}(s)-h_{2}(v)$ then the broadcast message is already delivered through all slow edges of the path $v_{1},\ldots,v_{p}$ until block $b_{a}$ .

Let $\alpha=c\cdot 60\log^{2}n$ , let $c\geq 8$ be a constant and let $X=\sum_{i=1}^{\alpha}X_{i}$ . Then $E(X)\geq\alpha\cdot\frac{1}{30\log n}=2c\log n$ . If $X\geq h_{2}(s)-h_{2}(v)$ then the broadcast message is delivered through all slow edges of the path $v_{1},\ldots,v_{p}=v$ in at most $\alpha=O(\log^{2}n)$ rounds. Using standard Chernoff inequalities, we get $\text{Prob}\left(X<h_{2}(s)-h_{2}(v)\right)<\text{Prob}(X<\log n)<\text{Prob}(% X<E(X)/2)\leq e^{-EX/8}\leq\left(\frac{1}{n}\right)^{2c/8}\leq\frac{1}{n^{2}}$ , for $c\geq 8$ .

Let $v_{i}$ be a node in the path $v_{1},\ldots,v_{p}$ beginning a fast track, i.e., such that $(v_{i-1},v_{i})$ is a slow edge and $(v_{i},v_{i+1})$ is a fast edge. Then, after reception of the broadcast message in (an arbitrary) block $r$ , its ultimate round $z(v_{i})$ might be by at most $6\log n$ larger than $r$ . Thus, the number of rounds lost because of slowdowns on the borders between slow edges and fast tracks is at most $6\log n(h_{2}(s)-h_{2}(v))\in O(\log^{2}n)$ for each node $v$ , with prob. $\geq 1-n^{-2}$ .

The number of rounds required for delivery of the broadcast message to an arbitrary node $v$ is the sum of the number of rounds needed to pass the message through the fast tracks, the number of rounds needed to pass the message through slow edges and the number of rounds of slowdowns on the borders between slow edges and fast tracks. As we proved above, this sum is $O(D+\log^{2}n)$ with probability at least $1-1/n^{2}$ , for each node $v$ . Thus, by the union bound, the probability that any node does not receive the broadcast message within $O(D+\log^{2}n)$ rounds is at most $1/n$ . This concludes the proof. $\hfill\blacktriangleleft$

As the only random ingredient is in the labeling scheme assignment, Theorem 12 implies the following corollary.

Corollary 13.

There exists a constant length labeling scheme supporting broadcast in time $O(D+\log^{2}n)$ .

In view of the lower bound from [1], our broadcasting time $O(D+\log^{2}n)$ is optimal, even when compared to broadcasting time in radio networks of known topology.

4.4 Acknowledged broadcasting

In this section we consider acknowledged broadcasting. when we require that each node knows the round number $T$ such that all nodes receive the broadcast message until round $T$ .

A relatively simple modification of broadcasting algorithms presented in this paper transforms them into acknowledged broadcasting algorithms.

Corollary 14.

1.

Acknowledged broadcasting in time $O(D+\min(D,\log n)\log^{2}n)$ is supported by some constructive labeling scheme of constant length.
2.

There exists a labeling scheme of constant length supporting acknowledged broadcasting in time $O(D+\log^{2}n)$ .

5 Gossiping

First, we focus on the auxiliary task of gathering. Here, the goal is to gather messages of all nodes in a designated node, called the sink. We provide a family of graphs proving the bound $\Omega(\log\Delta)$ on the length of a labeling scheme sufficient to accomplish this task. As gossiping is at least as hard as gathering, this is also a lower bound for gossiping.

Then, we present centralized and distributed algorithms for gathering using short labels. Our centralized algorithm might be seen as a kind of regularized variant of the gathering algorithm from [16], using 2-HRT instead of so-called gathering trees, in order to make it amenable to a distributed implementation with labels of optimal size $O(\log\Delta)$ . Let $T$ be a BFS tree of the input graph which is also a 2-HRT. The centralized algorithm determines the unique round $t(v)$ in which each node $v$ successfully transmits all messages from its subtree of $T$ to the parent of $v$ .

Intuitions behind the centralized algorithm are as follows. We conceptually split the time line into intervals of length $\Delta+1$ such that, on each level of $T$ , one block of an interval is devoted to accomplish fast connections (from nodes to their parents) and the remaining ones are for slow connections. An auxiliary labeling $s:V\to[0,\Delta]$ needed for slow connections will assure that $s(u)\neq s(w)$ for $u$ and $w$ such that $\textit{level}(u)=\textit{level}(w)=l$ and $u, w$ have a common neighbor on the level $l-1$ . Let $P$ be a subpath of a path going from a leaf to the root $s$ of $T$ , such that all edges connecting nodes of $P$ are fast. Let $(v_{1},\ldots,v_{p})$ be the sequence of nodes of $P$ starting from the node on the largest level. As all the edges on $P$ are fast, we have $h_{2}(v_{1})=h_{2}(v_{2})=\cdots=h_{2}(v_{p})$ , and therefore those nodes do not “collide” with other children of their parents with the same value of $h_{2}$ . We facilitate pipelining of transmissions through such a path $P$ by setting $t(v_{j+1})=t(v_{j})+1$ for $j\in[1,p-1]$ . Thus, transmission through such a fast path $P$ takes $p$ plus at most $\Delta$ blocks to start such a pipelined sequence of transmissions. Moreover, each path from a leaf to the sink $s$ of $T$ can be split into at most $\log n$ fast paths separated by at most $\log n$ slow edges, due to Lemma 5.

The value of $t(v)$ depends on $D$ , $\textit{level}(v)$ , $h_{2}(v)\in[0,\log n]$ , $\Delta$ and on the auxiliary label $s(v)\in[0,\Delta-1]$ . While $\Delta$ and $s(v)$ can be encoded in the label of $v$ using $O(\log\Delta)$ bits, we cannot store $D$ , $h_{2}(v)$ and $\textit{level}(v)$ in the label. In order to manage this issue, a modified Size Learning Algorithm from [14] is executed which assures that a designated node learns $D$ . Then an acknowledged broadcasting algorithm broadcasting $D$ is executed. Nodes also learn their levels during an execution of the broadcasting algorithm. Finally, each leaf is marked as such by an appropriate bit of its label. The fact that a node $v$ is a leaf implies also that $h_{2}(v)=0$ . Other nodes determine their values of $h_{2}$ by learning the values of $h_{2}$ of their children (from the obtained messages) which is sufficient to determine $h_{2}(v)$ .

In order to accomplish the gossiping task we gather all messages in an arbitrary node $s$ , executing our gathering algorithm. Then, all messages are distributed using our broadcasting algorithm. An obstacle in implementing this idea is caused by the fact that all nodes have to be coordinated so that they know when the consecutive subroutines of the final algorithm start. We overcome this difficulty by using acknowledged broadcasting.

6 Conclusion and Open Problems

We presented distributed algorithms for broadcasting and gossiping, which use labeling schemes of optimal length. In the case of broadcasting, the time is also optimal, even when compared to centralized algorithms. For gossiping, our algorithm uses a labeling scheme of optimal length $O(\log\Delta)$ , and runs in the best known centralized gossiping time.

Our results yield two interesting problems concerning the above communication tasks. The first problem concerns broadcasting. Is it possible to provide a constructive labeling scheme of constant length that supports broadcasting in time $O(D+\log^{2}n)$ ? The second problem concerns gossiping. What is the time of the fastest gossiping algorithm using a labeling scheme of optimal length $O(\log\Delta)$ ? Note that, if our gossiping time could be improved, this would imply improving the best known gossiping time for centralized algorithms.

Another interesting open problem regards universal labeling for broadcasting, i.e., such that the oracle does not know the source node $s$ so the labels have to be adjusted for an arbitrary source node.

References

[1] Noga Alon, Amotz Bar-Noy, Nathan Linial, and David Peleg. A lower bound for radio broadcast. J. Comput. Syst. Sci., 43(2):290–298, 1991. doi:10.1016/0022-0000(91)90015-W.
[2] Stephen Alstrup, Haim Kaplan, Mikkel Thorup, and Uri Zwick. Adjacency labeling schemes and induced-universal graphs. SIAM J. Discret. Math., 33(1):116–137, 2019. doi:10.1137/16M1105967.
[3] 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. J. Comput. Syst. Sci., 45(1):104–126, 1992. doi:10.1016/0022-0000(92)90042-H.
[4] I. Chlamtac and S. Kutten. On broadcasting in radio networks–problem analysis and protocol design. Communications, IEEE Transactions on, 33(12):1240–1246, December 1985. doi:10.1109/TCOM.1985.1096245.
[5] Imrich Chlamtac. The wave expansion approach to broadcasting in multihop radio networks. IEEE Trans. Commun., 39(3):426–433, 1991. doi:10.1109/26.79285.
[6] Marek Chrobak, Kevin P. Costello, Leszek Gasieniec, and Dariusz R. Kowalski. Information gathering in ad-hoc radio networks with tree topology. Inf. Comput., 258:1–27, 2018. doi:10.1016/j.ic.2017.11.003.
[7] Ferdinando Cicalese, Fredrik Manne, and Qin Xin. Faster deterministic communication in radio networks. Algorithmica, 54(2):226–242, 2009. doi:10.1007/S00453-007-9136-0.
[8] Artur Czumaj and Peter Davies. Deterministic communication in radio networks. SIAM J. Comput., 47(1):218–240, 2018. doi:10.1137/17M1111322.
[9] Artur Czumaj and Wojciech Rytter. Broadcasting algorithms in radio networks with unknown topology. J. Algorithms, 60(2):115–143, 2006. doi:10.1016/J.JALGOR.2004.08.001.
[10] Faith Ellen and Seth Gilbert. Constant-length labelling schemes for faster deterministic radio broadcast. In Christian Scheideler and Michael Spear, editors, SPAA ’20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020, pages 213–222. ACM, 2020. doi:10.1145/3350755.3400238.
[11] Faith Ellen, Barun Gorain, Avery Miller, and Andrzej Pelc. Constant-length labeling schemes for deterministic radio broadcast. In Christian Scheideler and Petra Berenbrink, editors, The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019, pages 171–178. ACM, 2019. doi:10.1145/3323165.3323194.
[12] Pierre Fraigniaud, Amos Korman, and Emmanuelle Lebhar. Local MST computation with short advice. Theory Comput. Syst., 47(4):920–933, 2010. doi:10.1007/s00224-010-9280-9.
[13] Emanuele G. Fusco, Andrzej Pelc, and Rossella Petreschi. Topology recognition with advice. Inf. Comput., 247:254–265, 2016. doi:10.1016/j.ic.2016.01.005.
[14] Adam Ganczorz, Tomasz Jurdzinski, Mateusz Lewko, and Andrzej Pelc. Deterministic size discovery and topology recognition in radio networks with short labels. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), volume 209 of LIPIcs, pages 22:1–22:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.DISC.2021.22.
[15] Leszek Gasieniec and Andrzej Lingas. On adaptive deterministic gossiping in ad hoc radio networks. Inf. Process. Lett., 83(2):89–93, 2002. doi:10.1016/S0020-0190(01)00312-X.
[16] Leszek Gasieniec, David Peleg, and Qin Xin. Faster communication in known topology radio networks. Distributed Comput., 19(4):289–300, 2007. doi:10.1007/s00446-006-0011-z.
[17] Leszek Gasieniec, Tomasz Radzik, and Qin Xin. Faster deterministic gossiping in directed ad hoc radio networks. In Torben Hagerup and Jyrki Katajainen, editors, Algorithm Theory - SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004, Proceedings, volume 3111 of Lecture Notes in Computer Science, pages 397–407. Springer, 2004. doi:10.1007/978-3-540-27810-8_34.
[18] Mohsen Ghaffari and Bernhard Haeupler. Fast structuring of radio networks large for multi-message communications. In Yehuda Afek, editor, Distributed Computing - 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings, volume 8205 of Lecture Notes in Computer Science, pages 492–506. Springer, 2013. doi:10.1007/978-3-642-41527-2_34.
[19] Christian Glacet, Avery Miller, and Andrzej Pelc. Time vs. information tradeoffs for leader election in anonymous trees. ACM Trans. Algorithms, 13(3):31:1–31:41, 2017. doi:10.1145/3039870.
[20] Barun Gorain and Andrzej Pelc. Deterministic graph exploration with advice. ACM Trans. Algorithms, 15(1):8:1–8:17, 2019. doi:10.1145/3280823.
[21] Dariusz R. Kowalski and Andrzej Pelc. Broadcasting in undirected ad hoc radio networks. Distributed Computing, 18(1):43–57, 2005. doi:10.1007/s00446-005-0126-7.
[22] Dariusz R. Kowalski and Andrzej Pelc. Optimal deterministic broadcasting in known topology radio networks. Distributed Computing, 19(3):185–195, 2007. doi:10.1007/s00446-006-0007-8.
[23] Gianluca De Marco. Distributed broadcast in unknown radio networks. SIAM J. Comput., 39(6):2162–2175, 2010. doi:10.1137/080733826.
[24] Avery Miller and Andrzej Pelc. Fast rendezvous with advice. Theor. Comput. Sci., 608:190–198, 2015. doi:10.1016/J.TCS.2015.09.025.
[25] Shailesh Vaya. Round complexity of leader election and gossiping in bidirectional radio networks. Inf. Process. Lett., 113(9):307–312, 2013. doi:10.1016/J.IPL.2013.02.001.

Appendix

Appendix A Table presenting our results

Table 1: Previous and our results.

Ref.	Time	Length of labeling scheme	Constructive
Broadcasting: centralized optimal time $O(D+\log^{2}n)$ , [16, 22]
[11]	$O(n)$	$2$ bits	Yes
[10]	$O(D\log n+\log^{2}n)$	$3$ bits	No
[10]	$O(D\log^{2}n)$	$3$ bits	Yes
here	$O(D+\log^{2}n)$	$7$ bits	No
here	$O\left(D+\min(D,\log n)\cdot\log^{2}n\right)$	$7$ bits	Yes
Gossiping: centralized best time known $O(D+\Delta\log n+\log^{2}n)$ , follows from [16]
here	$O(D+\Delta\log n+\log^{2}n)$	$\Theta(\log\Delta)$	No
here	$O(D+\Delta\log n+\min(D,\log n)\log^{2}n)$	$\Theta(\log\Delta)$	Yes

Appendix B Table comparing previous broadcasting algorithms with our work

Table 2: Overview of broadcasting algorithms in Section 4.

Algorithm	Section/Theorem	Constructive	Time	Paper
$\mathcal{B}$	–	Yes	$O(n)$	[11]
Executor Algorithm	–	No	$O(D\log n+\log^{2}n)$	[10]
Executor Algorithm	–	Yes	$O(D\log^{2}n)$	[10]
Levelled Executor Algorithm	S. 4.1/Th. 4	No	$O(D\log n+\log^{2}n)$	here
Fast Broadcast Algorithm	S. 4.2/Th. 9	Yes	$O(D+\min(D,\log n)\cdot$	here
			$\log^{2}n)$
Express Broadcast Algorithm	S. 4.3/Th. 12	No	$O(D+\log^{2}n)$	here

Appendix C Constructive Variant of Levelled Executor Algorithm

As in [10] (Lemma 13), we will use the following lemma which is a slight modification of the result proved by Chlamtac and Weinstein [5].

Lemma 15 ([5, 10]).

Let $G$ be a bipartite graph with bipartition sets $A$ and $B$ , where the degree of each node $v\in B$ is at least one. Then, there exists a polynomial time deterministic algorithm which finds the sets $A^{\prime}\subseteq A$ and $B^{\prime}\subseteq B$ such that $|B^{\prime}|\geq|B|/\left(15\log|A|\right)$ and each node from $B^{\prime}$ has exactly one neighbor in $A^{\prime}$ .

The above result is obtained as follows. One can show that a random choice of $A^{\prime}$ guarantees that the expected size of $B^{\prime}$ is at least $|B|/\left(15\log|A|\right)$ . Let $A^{\prime}$ be chosen randomly such that, for some fixed $p\in\{1/2^{1},1/2^{2},\ldots,1/2^{\lceil\log n\rceil}\}$ , $v$ is chosen to belong to $A^{\prime}$ with probability $p$ , independently of random choices for other elements of $A$ , for each $v\in A$ . Then, using the technique of derandomization with maximization of expectation one can determine $A^{\prime}$ satisfying Lemma 15 in polynomial time. For more details, refer e.g., to [10].

We now describe a deterministic assignment of the bits Go, using Lemma 15. Divide an execution of the algorithm into consecutive stages consisting of $T=15\log^{2}n$ of our $3-step$ blocks. If a node $v$ gets informed during the block $t_{v}$ then Go bits in its feedback nodes in the blocks $t^{\prime}>t_{v}$ will be set to $0$ until the block $t^{\prime}_{v}$ equal to the smallest number $t^{\prime}$ such that $t^{\prime}=0\mod T$ . (Note that it is sufficient that $\log n$ is known to the oracle assigning labels and the distributed broadcast algorithm working at nodes using these labels can work without knowledge of $\log n$ .) In other words, Go bits of $v$ are set to $0$ until the end of the stage in which $v$ is informed.

Now, we are ready to describe an efficient algorithm which assigns the bits Go to all nodes, together with other bits of labels described above. Let $k\geq 0$ be an integer, let $A$ be the subset of the set of nodes $\mathbf{DOM}_{kT}$ located on some level $l$ and let all labels be already fixed for nodes informed before the block $k T$ . That is, for a fixed $l$ , $A=\mathbf{DOM}_{kT}\cap L_{l}$ . Moreover, for $r\geq 0$ , let $A_{r}\subseteq A$ $\subseteq L_{l}$ be the set of nodes from $A$ still being in the dominating set of the block $kT+r$ . That is, $A_{r}$ is the subset of $A$ containing the nodes which are in $\mathbf{DOM}_{kT+r}$ . Let $B_{r}$ be the set of uninformed neighbors of $A_{r}$ on the level $l+1$ . Then, let $A^{\prime}_{r}\subseteq A_{r}$ and $B^{\prime}_{r}\subseteq B_{r}$ be the sets provided by the the algorithm from Lemma 15 applied to the bipartite graph induced by the sets $A_{r}$ and $B_{r}$ . For each $v\in A_{r}$ , the bit Go of the feedback node of $v$ in block $kT+r$ is set to $1$ iff $v\in A^{\prime}_{r}$ .

Lemma 16.

The set $B_{r^{\prime}}$ , for $r^{\prime}=15\log^{2}n$ , is empty.

Proof.

Fix any block $r<r^{\prime}$ . By the construction of the algorithm, any node $v\in A_{r}$ in the $(kT+r)$ th block gets the Go bit from its feedback node. If $v\in A^{\prime}_{r}$ then its bit Go is set to $1$ and therefore it broadcasts in the Go round. By Lemma 15, if all nodes from $A^{\prime}_{r}$ transmit simultaneously then all nodes from $B^{\prime}_{r}$ receive the broadcast message and therefore they are informed after the block $kT+r$ . As $B_{r+1}\subseteq B_{r}\setminus B^{\prime}_{r}$ , Lemma 15 implies that the size of $B_{r^{\prime}}$ can be bounded as follows:

|B_{r^{\prime}}|\leq|B_{0}|\left(1-\frac{1}{15\log n}\right)^{15\log^{2}n}\leq% |B|\exp(-\log_{2}n)=\frac{|B|}{n}<1.\

$\hfill\blacktriangleleft$ After becoming informed in some block $t$ , a node $v$ waits for the block $r$ with the smallest number $r\geq t$ equal to the multiple of $15\log^{2}n$ and then $v$ becomes a member of the “source part” of such a bipartite graph containing all its uninformed neighbors. Broadcasting in a bipartite graph can be done done in $15\log^{2}n$ blocks by Lemma 16. This implies that, if node $v$ gets first informed in block $r$ then all its neighbors are informed by the end of block $r+30\log^{2}n$ . Hence we get the following corollary.

Corollary 17.

The Levelled Executor Algorithmaccomplishes broadcast in $O(D\log^{2}n)$ rounds, and uses a constructive labeling scheme.

[bib.bib1] [1] Noga Alon, Amotz Bar-Noy, Nathan Linial, and David Peleg. A lower bound for radio broadcast. J. Comput. Syst. Sci., 43(2):290–298, 1991. doi:10.1016/0022-0000(91)90015-W.

[bib.bib2] [2] Stephen Alstrup, Haim Kaplan, Mikkel Thorup, and Uri Zwick. Adjacency labeling schemes and induced-universal graphs. SIAM J. Discret. Math., 33(1):116–137, 2019. doi:10.1137/16M1105967.

[bib.bib3] [3] 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. J. Comput. Syst. Sci., 45(1):104–126, 1992. doi:10.1016/0022-0000(92)90042-H.

[bib.bib4] [4] I. Chlamtac and S. Kutten. On broadcasting in radio networks–problem analysis and protocol design. Communications, IEEE Transactions on, 33(12):1240–1246, December 1985. doi:10.1109/TCOM.1985.1096245.

[bib.bib5] [5] Imrich Chlamtac. The wave expansion approach to broadcasting in multihop radio networks. IEEE Trans. Commun., 39(3):426–433, 1991. doi:10.1109/26.79285.

[bib.bib6] [6] Marek Chrobak, Kevin P. Costello, Leszek Gasieniec, and Dariusz R. Kowalski. Information gathering in ad-hoc radio networks with tree topology. Inf. Comput., 258:1–27, 2018. doi:10.1016/j.ic.2017.11.003.

[bib.bib7] [7] Ferdinando Cicalese, Fredrik Manne, and Qin Xin. Faster deterministic communication in radio networks. Algorithmica, 54(2):226–242, 2009. doi:10.1007/S00453-007-9136-0.

[bib.bib8] [8] Artur Czumaj and Peter Davies. Deterministic communication in radio networks. SIAM J. Comput., 47(1):218–240, 2018. doi:10.1137/17M1111322.

[bib.bib9] [9] Artur Czumaj and Wojciech Rytter. Broadcasting algorithms in radio networks with unknown topology. J. Algorithms, 60(2):115–143, 2006. doi:10.1016/J.JALGOR.2004.08.001.

[bib.bib10] [10] Faith Ellen and Seth Gilbert. Constant-length labelling schemes for faster deterministic radio broadcast. In Christian Scheideler and Michael Spear, editors, SPAA ’20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020, pages 213–222. ACM, 2020. doi:10.1145/3350755.3400238.

[bib.bib11] [11] Faith Ellen, Barun Gorain, Avery Miller, and Andrzej Pelc. Constant-length labeling schemes for deterministic radio broadcast. In Christian Scheideler and Petra Berenbrink, editors, The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019, pages 171–178. ACM, 2019. doi:10.1145/3323165.3323194.

[bib.bib12] [12] Pierre Fraigniaud, Amos Korman, and Emmanuelle Lebhar. Local MST computation with short advice. Theory Comput. Syst., 47(4):920–933, 2010. doi:10.1007/s00224-010-9280-9.

[bib.bib13] [13] Emanuele G. Fusco, Andrzej Pelc, and Rossella Petreschi. Topology recognition with advice. Inf. Comput., 247:254–265, 2016. doi:10.1016/j.ic.2016.01.005.

[bib.bib14] [14] Adam Ganczorz, Tomasz Jurdzinski, Mateusz Lewko, and Andrzej Pelc. Deterministic size discovery and topology recognition in radio networks with short labels. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), volume 209 of LIPIcs, pages 22:1–22:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.DISC.2021.22.

[bib.bib15] [15] Leszek Gasieniec and Andrzej Lingas. On adaptive deterministic gossiping in ad hoc radio networks. Inf. Process. Lett., 83(2):89–93, 2002. doi:10.1016/S0020-0190(01)00312-X.

[bib.bib16] [16] Leszek Gasieniec, David Peleg, and Qin Xin. Faster communication in known topology radio networks. Distributed Comput., 19(4):289–300, 2007. doi:10.1007/s00446-006-0011-z.

[bib.bib17] [17] Leszek Gasieniec, Tomasz Radzik, and Qin Xin. Faster deterministic gossiping in directed ad hoc radio networks. In Torben Hagerup and Jyrki Katajainen, editors, Algorithm Theory - SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004, Proceedings, volume 3111 of Lecture Notes in Computer Science, pages 397–407. Springer, 2004. doi:10.1007/978-3-540-27810-8_34.

[bib.bib18] [18] Mohsen Ghaffari and Bernhard Haeupler. Fast structuring of radio networks large for multi-message communications. In Yehuda Afek, editor, Distributed Computing - 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings, volume 8205 of Lecture Notes in Computer Science, pages 492–506. Springer, 2013. doi:10.1007/978-3-642-41527-2_34.

[bib.bib19] [19] Christian Glacet, Avery Miller, and Andrzej Pelc. Time vs. information tradeoffs for leader election in anonymous trees. ACM Trans. Algorithms, 13(3):31:1–31:41, 2017. doi:10.1145/3039870.

[bib.bib20] [20] Barun Gorain and Andrzej Pelc. Deterministic graph exploration with advice. ACM Trans. Algorithms, 15(1):8:1–8:17, 2019. doi:10.1145/3280823.

[bib.bib21] [21] Dariusz R. Kowalski and Andrzej Pelc. Broadcasting in undirected ad hoc radio networks. Distributed Computing, 18(1):43–57, 2005. doi:10.1007/s00446-005-0126-7.

[bib.bib22] [22] Dariusz R. Kowalski and Andrzej Pelc. Optimal deterministic broadcasting in known topology radio networks. Distributed Computing, 19(3):185–195, 2007. doi:10.1007/s00446-006-0007-8.

[bib.bib23] [23] Gianluca De Marco. Distributed broadcast in unknown radio networks. SIAM J. Comput., 39(6):2162–2175, 2010. doi:10.1137/080733826.

[bib.bib24] [24] Avery Miller and Andrzej Pelc. Fast rendezvous with advice. Theor. Comput. Sci., 608:190–198, 2015. doi:10.1016/J.TCS.2015.09.025.

[bib.bib25] [25] Shailesh Vaya. Round complexity of leader election and gossiping in bidirectional radio networks. Inf. Process. Lett., 113(9):307–312, 2013. doi:10.1016/J.IPL.2013.02.001.

Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

The model and the problem

Our results

Related work

Organization of the paper

2 High-level Description of our Results

2.1 High-level description of broadcasting

1. The domination mechanism from [11]

2. The propagation mechanism from [10]

3. The fast tracks mechanism

2.2 High-level description of gossiping

3 𝟐-height Respecting Trees

Definition 1 (2-height, fast edge, slow edge).

Definition 2 (2-height respecting tree).

Lemma 3.

4 Broadcasting Algorithms

4.1 Levelled Executor Algorithm

Theorem 4 ([10]).

4.2 Fast Broadcast Algorithm: Linear Dependency on 𝑫

Lemma 5 ([6]).

Corollary 6.

Observation 7.

Lemma 8.

Proof.

Case I: 𝒉𝟐⁢(𝒗)<𝒉𝟐⁢(p⁢(𝒗)).

Case II: 𝒉𝟐⁢(𝒗)=𝒉𝟐⁢(p⁢(𝒗)).

Theorem 9.

4.3 Express Broadcast Algorithm– Optimization of the polylog Additive Summand

Observation 10.

Lemma 11.

Theorem 12.

Proof.

Corollary 13.

4.4 Acknowledged broadcasting

Corollary 14.

5 Gossiping

6 Conclusion and Open Problems

References

Appendix

Appendix A Table presenting our results

Appendix B Table comparing previous broadcasting algorithms with our work

Appendix C Constructive Variant of Levelled Executor Algorithm

Lemma 15 ([5, 10]).

Lemma 16.

Proof.

Corollary 17.

3 $2$ -height Respecting Trees

4.2 Fast Broadcast Algorithm: Linear Dependency on $𝑫$

Case I: $h_{2}(v)<h_{2}(\textit{p}(v))$ .

Case II: $h_{2}(v)=h_{2}(\textit{p}(v))$ .