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

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 $\mathrm{\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” to mean “with probability at least $1-1/n$”.

We use square brackets to indicate sets of consecutive integers: $[i,j]=\{i,\mathrm{\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 $ℒ$ from the set $V$ of nodes to the set $S$ of finite binary strings. The string $ℒ(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 $ℒ$ 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 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 [16] or different strings may be given to different nodes [8, 7, 9, 10], 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 [1].

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)$.
$\bullet$ 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.
$\bullet$ 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 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) [7]. As in [7], 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 [7] 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 [7] 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+\mathrm{\Delta }\log n+{\log }^{2}n)$, that uses a (non-constructive) labeling scheme of optimal length $O(\log \mathrm{\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 [13].

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 [13, 19] and the best known gossiping time (without any extra assumptions on parameters) follows from [13]. For large values of $\mathrm{\Delta }$, this was later improved in [4]. 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)$ [20], later improved in [5] for some values of parameters $D$ and $\mathrm{\Delta }$. For gossiping, the best known time in arbitrary directed (strongly connected) graphs was given in [12, 14] and the best known time for undirected graphs follows from [22]. Randomized distributed broadcasting was studied in [18, 6], where optimal $O(D\log (n/D)+{\log }^{2}n)$ time algorithms were obtained independently. For gossiping, optimal randomized time was given in [15].

The advice paradigm has been applied to many different distributed network tasks: finding a minimum spanning tree [9], finding the topology of the network [10], and leader election [16]. In [8] and [7], 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 [17] or rendezvous [21]. In this case, advice is given to mobile agents.

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.

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

With this aim, we make use of properties of a 2-HRT to implement the centralized algorithm for gathering from [13] 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 [13] determines the unique round $t(v)$ in which each node $v$ transmits all messages from its subtree of $T$⁴⁴4The authors of [13] use the notion of gathering trees, but 2-HRT satisfy all properties of gathering trees. to the parent of $v$ without a collission. These collision-free transmissions are assured by the properties of gathering trees from [13] which are also satisfied by 2-HRT. The value of $t(v)$ depends on parameters $D$, $\text{level}(v)$, $h_2(v)\in [0,\log n]$, $\mathrm{\Delta }$ and on some auxiliary label $s(v)\in [0,\mathrm{\Delta }-1]$. Thus, while $\mathrm{\Delta }$ and $s(v)$ can be encoded in the label of $v$ using $O(\log \mathrm{\Delta })$ bits, we cannot store $D$, $h_2(v)$ and $\text{level}(v)$ in the label of length $O(\log \mathrm{\Delta })$. With this aim we use a modified Size Learning Algorithm from [11] 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. In order to coordinate all nodes so that they know when the consecutive subroutines of the final algorithm start, we use an acknowledged broadcasting.