# Deterministic Size Discovery and Topology Recognition in Radio Networks with
Short Labels

Adam Gańczorz111Institute of Computer Science, University of Wrocław, Poland.
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>Supported
by the Polish National Science Centre grant DEC-2017/25/B/ST6/02010. Tomasz
Jurdziński11footnotemark: 1 Mateusz Lewko11footnotemark: 1 Andrzej Pelc222
Département d’informatique, Université du Québec en Outaouais, Gatineau,
Québec J8X 3X7, Canada<EMAIL_ADDRESS>Partially supported by NSERC discovery
grant 2018-03899 and by the Research Chair in Distributed Computing at the
Université du Québec en Outaouais.

###### Abstract

We consider the fundamental problems of _size discovery_ and _topology
recognition_ in radio networks modeled by simple undirected connected graphs.
Size discovery calls for all nodes to output the number of nodes in the graph,
called its size, and in the task of topology recognition each node has to
learn the topology of the graph and its position in it. In radio networks,
nodes communicate in synchronous rounds and start in the same round. In each
round a node can either transmit the same message to all its neighbors, or
stay silent and listen. At the receiving end, a node $v$ hears a 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$. We do not
assume collision detection: in case of a collision, node $v$ does not hear
anything (except the background noise that it also hears when no neighbor
transmits). The time of a deterministic algorithm for each of the above
problems is the worst-case number of rounds it takes to solve it. Nodes have
labels which are (not necessarily different) binary strings. Each node knows
its own label and can use it when executing the algorithm. The length of a
labeling scheme is the largest length of a label.

Our goal is to construct short labeling schemes for size discovery and
topology recognition in arbitrary radio networks, and to design efficient
deterministic algorithms for each of these tasks, using these short schemes.
It turns out that the optimal length of labeling schemes for both problems
depends on the maximum degree $\Delta$ of the graph. For size discovery, we
construct a labeling scheme of length $O(\log\log\Delta)$ (which is known to
be optimal, even if collision detection is available) and we design an
algorithm for this problem using this scheme and working in time
$O(\log^{2}n)$, where $n$ is the size of the graph. We also show that time
complexity $O(\log^{2}n)$ is optimal for the problem of size discovery,
whenever the labeling scheme is of optimal length $O(\log\log\Delta)$. For
topology recognition, we construct a labeling scheme of length
$O(\log\Delta)$, and we design an algorithm for this problem using this scheme
and working in time $O\left(D\Delta+\min(\Delta^{2},n)\right)$, where $D$ is
the diameter of the graph. We also show that the length of our labeling scheme
is asymptotically optimal, by proving that topology recognition in the class
of arbitrary radio networks requires labeling schemes of length
$\Omega(\log\Delta)$.

keywords:  size discovery, topology recognition, radio network, labeling
scheme

##  1 Introduction

Information about the topology of the network or some of its parameters, such
as size, often determines the efficiency and sometimes the feasibility of many
network algorithms. For example, graph exploration with stop in rings with
non-unique labels is impossible without knowing some upper bound on the size
of the ring. On the other hand, optimal broadcasting algorithms in wireless
networks with distinct labels are faster when the topology of the network is
known than without this assumption [7, 22]. Hence, the problems of _size
discovery_ and _topology recognition_ are fundamental in network computing.
Size discovery calls for all nodes to output the number of nodes in the
underlying graph, called its size, and in the task of topology recognition
each node has to output an isomorphic copy of the graph with its position in
it marked. More formally, in topology recognition, every node $v$ of the graph
$G$ modeling the network must output a graph $G^{\prime}$ and a node
$v^{\prime}$ in this graph, such that there exists an isomorphism
$f:G\rightarrow G^{\prime}$, for which $f(v)=v^{\prime}$.

###  1.1 The model

We consider size discovery and topology recognition in radio networks modeled
by 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. We use square brackets to indicate
sets of consecutive integers: $[i,j]=\\{i,\dots,j\\}$ and $[i]=[1,i]$.

As usually assumed in the algorithmic literature on radio networks, nodes
communicate in synchronous rounds, starting in the same round. In each round a
node can either transmit the same message to all its neighbors, or stay silent
and listen. At the receiving end, a node $v$ hears a 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). In this paper
we do not assume collision detection. The time of a deterministic algorithm
for each of the above problems is the worst-case number of rounds it takes to
solve it.

If nodes are anonymous then neither size discovery nor topology recognition
can be performed, as no communication in the network is possible. Indeed,
without any labels, in every round either all nodes transmit or all remain
silent, and so no message can be received. Hence we consider labeled networks.
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 into the set $S$ of finite
binary strings. The string ${\mathcal{L}}(v)$ is called the label of the node
$v$. Note that 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 for the size discovery or topology recognition
algorithm.

Our goal is to construct short labeling schemes for size discovery and
topology recognition in arbitrary radio networks, and to design efficient
deterministic algorithms for each of these tasks, using such schemes. Such
short schemes in the context of radio networks were studied for size discovery
in [19], and for topology recognition in [18]. In [19] the authors worked in
the model with collision detection. They constructed labeling schemes of
length $O(\log\log\Delta)$ and a size discovery algorithm using this scheme
and working in time $O(Dn^{2}\log\Delta)$. They also proved that labels of
size $\Omega(\log\log\Delta)$ are necessary to solve the size discovery
problem in this model. In [18], the authors studied topology recognition
without collision detection, similarly as we do in the present paper, but
restricted attention only to tree networks. They constructed labeling schemes
of length $O(\log\log\Delta)$ and a topology recognition algorithm working for
arbitrary trees, using these schemes. Moreover, they showed that labels of
size $\Omega(\log\log\Delta)$ are necessary to solve the topology recognition
problem for trees.

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, and a distributed algorithm
cooperating with the oracle uses this advice to solve the problem efficiently.
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 [17] or different strings may be given to different nodes [9, 8, 11, 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 network problems (see the subsection Related work).
The framework of advice or labeling schemes permits us to quantify the amount
of information used to solve a network problem, such as size discovery or
topology recognition, regardless of the type of information that is provided.
It should be noticed that the scenario of the same advice given to all nodes
would be trivial in the case of radio networks: no communication could occur,
and hence the advice would have to contain the size of the network for size
discovery, and would not help for topology recognition, as nodes would not be
able to find their position in the network without communicating.

###  1.2 Our results

It turns out that the optimal length of labeling schemes, both for size
discovery and for topology recognition, depends on the maximum degree $\Delta$
of the graph. For size discovery, we construct a labeling scheme of length
$O(\log\log\Delta)$, which is optimal, in view of [19], and we design an
algorithm for this problem using this scheme and working in time
$O(\log^{2}n)$, where $n$ is the size of the graph. We also show that time
complexity $O(\log^{2}n)$ is optimal for the problem of size discovery,
whenever the labeling scheme is of optimal length $O(\log\log\Delta)$. Hence,
without collision detection we achieve the same optimal length of the labeling
scheme, as was done in [19] with collision detection, and for this optimal
scheme our size discovery algorithm is exponentially faster than that in [19].

For topology recognition, we construct a labeling scheme of length
$O(\log\Delta)$, and we design an algorithm for this problem using this scheme
and working in time $O\left(D\Delta+\min(\Delta^{2},n)\right)$, where $D$ is
the diameter of the graph. We also show that the length of our labeling scheme
is asymptotically optimal, by proving that topology recognition in the class
of arbitrary radio networks requires labeling schemes of length
$\Omega(\log\Delta)$. (In fact we prove a stronger result that this lower
bound holds even in the model with collision detection.) If the optimal length
of a labeling scheme sufficient to solve a problem is considered a measure of
the difficulty of the problem, our result shows, in view of the labeling
scheme of length $O(\log\log\Delta)$ for topology recognition in trees [18],
that this task is exponentially more difficult in arbitrary radio networks
than in radio networks modeled by trees.

###  1.3 Related work

There is a vast literature concerning distributed algorithms for various tasks
in radio networks. These tasks include, e.g., broadcasting [5, 15], gossiping
[5, 14] and leader election [6, 21]. In some cases [5, 14], the authors use
the model without collision detection, in others [16, 21], the collision
detection capability is assumed.

Many authors use the framework of algorithms with advice (or equivalently
informative labeling schemes) to investigate the amount of information needed
to solve a given network problem. In [12], the authors compare the minimum
size of advice required to solve two information dissemination problems, using
a linear number of messages. In [11], it is shown that advice of constant size
permits to carry out the distributed construction of a minimum spanning tree
in logarithmic time. In [2], optimal labeling schemes are constructed in order
to answer adjacency queries in graphs. In [10], the advice paradigm is used to
solve online problems.

In the model of radio networks, apart from the previously mentioned papers
[19] studying size discovery and [18] studying topology recognition in the
framework of short labeling schemes, other authors studied the tasks of
broadcast [20, 9, 8], and convergecast [4] in this framework. While [9, 8]
assume that short labels are given to anonymous nodes, [20] adopts a different
approach. The authors study radio networks without collision detection for
which it is possible to perform centralized broadcasting in constant time,
i.e., when the topology of the network is known and all nodes have different
labels. They investigate how many bits of additional information (i.e., not
counting the labels of nodes) given to nodes are sufficient for performing
broadcast in constant time in such networks, if the topology of the network is
not known to the nodes.

The task of topology recognition was also investigated in models other than
the radio model: in [13] the authors use the LOCAL model, and in [23] the
model used is the congested clique.

##  2 Preliminaries

As our algorithms use recent results showing that there exist constant-length
labeling schemes for the broadcast problem, we recall these results, adjust
them to our needs and introduce an auxiliary notion called the broadcast tree.
Then, using the fact that there exists an efficient broadcast algorithm with
constant-length labels, we give a lemma allowing to “encode” a given message
$M$ in labels of the neighborhood of some path associated with an efficient
algorithm that collects the whole message in a single node and broadcasts it
to the whole network.

###  2.1 Broadcast algorithms and broadcast trees

We use the constant-length labeling schemes for the broadcast problem [9, 8].
In this problem, a source node $s$ has a message which must be communicated to
all other nodes. First, we recall the result regarding fast broadcast with
constant-length labels from [8].

######  Theorem 1.

[8] There exists a labeling scheme of length $O(1)$ and an algorithm Executor
using it which solves the broadcast problem in time $O(D\log n+\log^{2}n)$.

We say that a node $v$ is _informed_ in some round $t$ of a broadcast
algorithm if $v$ knows the broadcast message in round $t$. Otherwise, $v$ is
_uninformed_ in round $t$. We assume that feedback messages in the execution
of Executor are distinct from the broadcast message (this can be easily
ensured by adding a special sign to the broadcast message).

######  Definition 1 (Broadcast Tree).

Let $G=(V,E)$ be a graph with the source node $s\in V$.

For each node $v\in V\setminus\\{s\\}$, the parent of $v$, denoted
$\textit{parent}(v)$, is the first node which successfully transmits the
broadcast message to $v$ during the execution of Executor in $G$. The
_broadcast tree_ $T_{\textsc{Executor}(G)}$ is the tree with the root $s$ and
the set of edges $(v,\textit{parent}(v))$ for each $v\neq s$.

The _level_ of a node $v\in V$, denoted $\text{level}(v)$, in the broadcast
tree $T_{\textsc{Executor}(G)}$ is equal to the natural number $i$ such that
$v$ receives the broadcast message from $\textit{parent}(v)$ for the first
time in round $i$ of the execution of Executor on $G$.

In our algorithms for the size discovery problem, we will use the following
properties of the algorithm Executor from [8].

######  Lemma 1.

The broadcast algorithm Executor described in Theorem 1 satisfies the
following properties:

  1. (1)

Assume that the level of a node $v$ in the broadcast tree
$T_{\textsc{Executor}(G)}$ is equal to $i$ and the level of
$\textit{parent}(v)$ in this tree is $j<i$. Then, $\textit{parent}(v)$ has a
child with level $k$ for each $k\in[j+1,i]$ such that $k\mod 3=1$.

  2. (2)

The maximum value of the levels of nodes of the broadcast tree
$T_{\textsc{Executor}(G)}$ is larger than $t-3$, where $t$ is the number of
rounds of the execution of Executor.

  3. (3)

Each node $v$ can determine the level of $\textit{parent}(v)$ and its own
level in the broadcast tree $T_{\textsc{Executor}}(G)$.

###### Proof.

We first give a short description of Executor [8] focusing on elements which
are important for the statement of the lemma. We refer the reader to [8] for
more details. The label of each node of the communication graph consists of
three bits called join, stay nad go. The algorithm works in _stages_ such that
the stage $i$ consist of three round $3i+1,3i+2,3i+3$ for a natural number
$i$. Each node $v$ is active in a consecutive sequence of stages (possibly
empty) starting at the stage directly following the stage at which $v$
receives the broadcast message. The labels guarantee that, if $v$ is active in
a stage, at least one uninformed node receives the broadcast message from $v$
in the given stage.

The sequence of sets $\text{DOM}_{i}$ for $i=1,\ldots,t$ plays an important
role in the formal description and analysis of the algorithm, where $t$ is the
number of stages of the algorithm. One can verify that the following
properties are satisfied during an execution of the algorithm (see [8]):

  1. (a)

each node $v$ can determine whether it belongs to $\text{DOM}_{i}$ at the
beginning of stage $i$, based on its label and its history of communication
until stage $i-1$,

  2. (b)

all elements of $\text{DOM}_{i}$ know the broadcast message already,

  3. (c)

$\text{DOM}_{i}$ is nonempty for each $i\leq t$,

  4. (d)

each element of $\text{DOM}_{i}$ transmits the broadcast message in the first
round of the stage $i$,

  5. (e)

for each $v\in\text{DOM}_{i}$, at least one uninformed node
$u\in\mathcal{N}(v)$ receives the non-ignored broadcast message from $v$ in
the first round of stage $i$,

  6. (f)

for each node $v$: either $v$ does not belongs to $\text{DOM}_{i}$ for any $i$
or $v$ belongs to the sequence of sets
$\text{DOM}_{i},\text{DOM}_{i+1},\ldots,\text{DOM}_{j}$ for $1\leq i\leq j<t$,
where $t$ is the number of all stages.

Below, we shortly describe the elements of the algorithm which are important
with respect to the correctness of the above properties (a)–(f).

Let $\text{FRONTIER}_{i}$ be the set of nodes which are uniformed before stage
$i$ but have at least one informed neighbor. The set $\text{DOM}_{i}$ (as
DOMinating set) is always a _minimal_ set of informed nodes which dominates
the set of frontier nodes $\text{FRONTIER}_{i}$. At first
$\text{DOM}_{1}=\\{s\\}$ and the conditions (a)–(f) are therefore satisfied at
the beginning of stage 1. Assume that (a)–(f) are satisfied until the
beginning of stage $i$. Below, we describe an execution of stage $i$ and argue
that the properties (a)–(f) are also preserved at the beginning of stage
$i+1$.

  * •

In the first round of the stage $i$, each node in $\text{DOM}_{i}$ sends the
broadcast message and the current round number $3i+1$, which assures (d). All
newly informed nodes store the round number $3i+1$ of reception of the
broadcast message. Each such newly informed node becomes an element of the
dominating set $\text{DOM}_{i+1}$ iff its join bit is equal to $1$.

As $\text{DOM}_{i}$ is a minimal set dominating the set $\text{FRONTIER}_{i}$,
i.e., the set of uninformed neighbors of informed nodes, each
$v\in\text{DOM}_{i}$ has an (at least one) uninformed neighbor
$u\in\text{FRONTIER}_{i}$ such that $v$ is the only neighbor of $u$ in
$\text{DOM}_{i}$. Therefore, such node $u$ receives the broadcast message from
$v$ which gives (e). One of such newly informed neighbors of $v$ is chosen as
the Feedback Node of $v$ for stage $i$.

  * •

The second round of the stage is the _Feedback round_. In that round, each
newly informed node checks the value of its stay and go bits. If at least one
of them is equal to $1$, then the node transmits both of these bits. Each node
from $\textsc{DOM}_{i}$ will no longer be in $\textsc{DOM}_{i+1}$ unless it
receives $\textsc{stay}=1$ in the second round.

  * •

In the last round of the phase, introduced as a speed-up of the previous
algorithm with constant size labels [9], a node from $\text{DOM}_{i}$
transmits the broadcast message if it got the value $\textsc{go}=1$ from its
designated Feedback Node in the previous round.

Finally, $\text{DOM}_{i+1}$ contains all elements of $\text{DOM}_{i}$ which
received $\textsc{stay}=1$ in the second round of the stage as well as the
nodes which were newly informed in rounds $1$ and $3$ of the stage $i$ and
their join bit is equal to $1$. This definition of $\textsc{DOM}_{i+1}$ proves
the statements (a), (b) and (f).

Finally, if $\textsc{DOM}_{i}$ is empty, then all nodes are informed, as the
communication graph is connected. And thus the broadcast task is finished,
which gives the above property (c).

Given the properties (a)–(f), one can see that the item (1) of the lemma
directly follows from (e) and (f), the item (2) follows from (c) and the item
(3) follows from the fact that each transmitting node attaches the current
round number to its message transmitted in rounds 1 and 3 of a stage. ∎

Below, we show that Executor can be easily transformed into an acknowledged
broadcast algorithm. We say that an algorithm $A$ solves the _acknowledged
broadcast_ problem in $T$ rounds iff it solves the broadcast problem, and
moreover, all nodes of the graph know after $T$ rounds that broadcast has been
completed.

Similar ideas were applied for the acknowledged broadcast in [9] (note that
the formulation of acknowledged broadcast in [9] was slightly weaker than
ours). However, as the round complexity of the algorithm from [9] is larger
than the round complexity of Executor and we need additional properties of the
algorithm for further applications, we provide the following corollary.

######  Corollary 1.

Algorithm Executor can be transformed into algorithm ExecAck such that

  * •

ExecAck solves the acknowledged broadcast problem on every graph $G$, using
$O(1)$-bit labels and working in at most $3t$ rounds, where $t=O(D\log
n+\log^{2}n)$ is the number of rounds of the execution of Executor on $G$.

  * •

after an execution of ExecAck on $G$, each node knows the number of levels of
the broadcast tree $T_{\textsc{Executor}(G)}$, as well as its own level and
the level of its parent in $T_{\textsc{Executor}(G)}$.

###### Proof.

First, we use the labeling scheme of Executor for the _standard_ broadcast
problem with $3$-bit labels. By Lemma 1.(2), we can choose a path $P$ from the
root to a leaf in $T_{\textsc{Executor}(G)}$ with the last node $v_{P}$ of $P$
on the maximum level $l>t-3$ . Moreover, we add two extra bits to the labels
of Executor in order to mark all nodes from $P$ and to mark the last node
$v_{P}$ of $P$ (with the maximum level in $T_{\textsc{Executor}(G)}$).

Given the above described labels, the algorithm starts by an execution of
Executor in order to broadcast the original message stored in the source node
$s$. After reception of the broadcast message, $v_{P}$ knows that the
execution of the broadcast algorithm is finished and it also knows the number
of rounds $t$ of Executor. Then, in round $t+1$, $v_{P}$ sends a new message
containing the pair which consists of $t$ and the level of
$\textit{parent}(v_{P})$ (see Lemma 1.(3)).111In order to make it clear that
this message is not sent during the execution of Executor but in the next
phase of the algorithm, one can add an appropriate prefix in messages,
denoting the parts of the considered algorithm. We will omit this issue in
further description of algorithms. Then, each other marked node $v$ transmits
a message in the round following the reception of the pair
$(t,\textit{level}(v))$. The message of $v$ contains $t$ and
$\textit{level}(\textit{parent}(v))$. The root $s$ receives the value of $t$
in at most $t$ rounds. After reception of $t$, the root starts the second
execution of Executor with the value of $t$ as the broadcast message. Thus,
all nodes receive $t$ as the broadcast message and they know that the
execution of ExecAck is finished in $3t$ rounds. ∎

###  2.2 Encoding a message in labels

Now, we make an observation regarding the length of labels sufficient to store
(in a distributed way) an arbitrary message $M$ initially unknown to all
nodes, and subsequently make the message $M$ known to all nodes.

######  Lemma 2.

Let ExecAck be the acknowledged broadcast algorithm which satisfies Corollary
1. Then, an arbitrary message $M$ of size $m$ (initially unknown to nodes) can
be made known to all nodes of graph $G$ in $O(t)$ rounds using $O(1+m/t)$-bit
labels, where $t=O(D\log n+\log^{2}n)$ is the number of rounds of the
execution of ExecAck on $G$.

###### Proof.

By Lemma 1.(2) and Corollary 1, we can choose a path $P$ from the root to a
leaf in $T_{\textsc{Executor}}$ with a leaf on the maximum level $L>t/3-1$,
where $t$ is the number of rounds of the execution of ExecAck on $G$. The
tempting idea is to split the message $M$ into the labels of the path $P$ and
collect these messages by transmissions from the end of $P$ backward in the
direction of the root, similarly to the simple construction described in the
proof of Corollary 1. However, such a solution is insufficient, as the height
of the broadcast tree can be much smaller that the number of levels of that
tree (a node of $T_{\textsc{Executor}(G)}$ might have children of various
levels). Therefore, we leverage the property from Lemma 1.(1) and, for each
node $v$ on the path $P$ and each level $k$ such that $v$ has at least one
child of level $k$ in $T_{\textsc{Executor}(G)}$, we choose exactly one child
of $v$ of level $k$.

Then, we add one extra bit to the labels of ExecAck in order to mark all nodes
from $P$ and their chosen children, as described above. Apart from that, we
use the labeling of ExecAck.

Note that the number of marked nodes is at least $L/3>$ $t/9-1$, by Lemma
1.(1). Thus, we can split the bits of $M$ between the marked nodes such that
each node keeps at most $9\lceil m/t\rceil$ bits. In order to make $M$ known
to all nodes of the network, we use the following algorithm:

  1. 1.

First, ExecAck is executed. At the end of this part each node $v$ knows the
number of rounds of ExecAck, its own level $\textit{level}(v)$ and the level
of its parent, as shown in Corollary 1.

  2. 2.

Then, the message $M$ is gathered in the root $s$ of the broadcast tree.

This part of the algorithm is initiated by the node $v_{P}$l. Recall that $t$
is the number of rounds of the first part of the algorithm. Each marked node
$v$ sends the tuple which consists of its part of the message $M$ and
$\textit{level}(v)$ in the round $t+L-\textit{level}(v)+1$ together with all
other messages received during this part of the algorithm. As at most one node
from each level is marked, there is at most one transmitter in each round.
Therefore all messages stored in the marked nodes will be collected in the
root $s$ in round $t+L$, and the root can decode the whole message $M$ from
these received messages.

  3. 3.

Finally, the root $s$ broadcasts $M$ to all nodes of the graph using ExecAck
again.

∎

##  3 The Size Discovery Problem

In Section 3.1 we describe a labeling scheme for encoding the size of a graph
and an algorithm which makes use of this encoding to first collect information
about the size of the graph at some node and then broadcast this value using
an efficient broadcast algorithm. Then, in Section 3.2, we describe a much
faster size discovery algorithm with time complexity $O(\log^{2}n)$. Finally,
in Section 3.3, we show that this time complexity is asymptotically optimal
for labels of size $O(\log\log\Delta)$.

###  3.1 Efficient labeling scheme

We design a general labeling scheme of length $O(\log\log\Delta)$ and a size
discovery algorithm using this scheme, based on the broadcast algorithm
working with constant-length labels [8]. In Section 3.1.1 we prove a general
lemma which states that each tree with maximum degree $\Delta$ and size $n$
contains a subtree with maximum degree $O(\log\Delta)$ and size $\Omega(\log
n)$. Then, in Section 3.1.2, we describe a labeling scheme which yields a
solution of the size discovery problem using the result from Section 3.1.1.
Finally, in Section 3.1.3, we design an algorithm which solves the size
discovery problem using the labeling scheme from Section 3.1.2 in time
$O(D\log n+\log^{2}n)$, where $D$ is the diameter of the graph.

####  3.1.1 $\log\Delta$-degree subtrees of a tree

We prove a general lemma stating that, given a tree $T$ with maximum degree
$\Delta$ and $3$ bits of “local memory” at each node, and given a binary
string $M$ of length $\lceil\log(n+1)\rceil+2$, there exists a subtree
$T^{\prime}$ of $T$ with maximum degree $\lfloor\log\Delta\rfloor+1$, such
that $M$ can be split into the $3$-bit local memories of the nodes of
$T^{\prime}$.

######  Lemma 3.

Let $T=(V,E)$ be a tree with maximum degree $\Delta$, size $n$ and the root
$r\in V$. Let $M$ be a binary string of length $\lceil\log(n+1)\rceil+1$.
Then, there exists a subtree $T^{\prime}$ of $T$ rooted at $r$ and an
assignment of binary strings to nodes of $T^{\prime}$ such that:

  1. (a)

the number of children of each node of $T^{\prime}$ is at most
$\lfloor\log\Delta\rfloor+1$,

  2. (b)

the string assigned to each node of $T^{\prime}$ has length at most $3$,

  3. (c)

the string assigned to the root of $T^{\prime}$ has length $2$,

and the concatenation of all strings assigned to nodes of $T^{\prime}$ is $M$.

###### Proof.

In order to prove the lemma, we present a recursive algorithm for assigning
bits of an arbitrary binary string $M$ of size $\lceil\log(n+1)\rceil+1$ to
the nodes of $T$ such that the assignment will satisfy the stated properties.
Along with the construction, we present a proof of the lemma by induction on
the size $n$ of the tree.

For the basic step of induction, assume that $n=1$. Then $r$ has no children,
$\lceil\log(n+1)\rceil=1$ and therefore the length of ${M}$ is at most $2$ –
we can store the bits of $M$ in the root $r$.

For the inductive step, assume that the lemma holds for all trees with size
smaller than some $n>1$. Let ${M}$ be a binary string with at most
$\lceil\log{(n+1)}\rceil+1$ bits and let $T$ be a tree with $n$ nodes, the
root $r$ and the maximum degree $\Delta$. Let
$v_{0},\dots,v_{\lfloor\log{\Delta}\rfloor}$ be the children of $r$ in $T$
with the largest subtrees. Let $n_{v_{i}}$ denote the size of the subtree of
$T$ rooted in $v_{i}$. We will construct an assignment $\mathcal{A}$ of
substrings of $M$ to nodes such that the conditions (a)–(c) of the lemma are
satisfied and the subtree $T^{\prime}$ of nodes with assigned substrings
contains the root $r$ and some nodes from the subtrees rooted at
$v_{0},\dots,v_{\lfloor\log{\Delta}\rfloor}$. Split ${M}=$ $M[0]M[1]\cdots
M[\lceil\log(n+1)\rceil]$ into blocks
$B_{0},\dots,B_{\lfloor\log{\Delta}\rfloor}$ such that each block $B_{i}$
except the last one consists of $\lceil\log(n_{v_{i}}+1)\rceil+1$ bits of $M$
with indices in the range

$\left[\sum_{k=0}^{i-1}\left(\lceil\log{(n_{v_{k}}+1)}\rceil+1\right),\sum_{k=0}^{i}\left(\lceil\log{(n_{v_{k}}+1)}\rceil+1\right)-1\right]$

provided that
$\sum_{k=0}^{i}\left(\lceil\log{(n_{v_{k}}+1)}\rceil+1\right)-1\leq\lceil\log(n+1)\rceil+1$.
Otherwise, the block $B_{i}$ contains all remaining bits of $M$ with indices
larger than or equal to
$\sum_{k=0}^{i-1}\left(\lceil\log{(n_{v_{k}}+1)}\rceil+1\right)$.222Note that,
according to the above definition, some number of last blocks might be empty.
Then we recursively assign bits from the block $B_{i}$ to the tree rooted in
$v_{i}$. As $n_{v_{i}}<n$, we can use the inductive hypothesis: as the length
of $B_{i}$ is not larger than $\lceil\log(n_{v_{i}}+1)\rceil+1$, there exist
assignments of bits of $B_{i}$ for $i=0,\ldots,\lfloor\log\Delta\rfloor$
satisfying the conditions (a)–(c) of the lemma. In particular, the roots
$v_{0},\ldots,v_{\lfloor\log\Delta\rfloor}$ have at most $2$ bits assigned. In
the case that the number
$\sum_{k=0}^{\lfloor\log\Delta\rfloor}\left(\lceil\log{(n_{v_{k}}+1)}\rceil+1\right)$
of bits assigned to subtrees rooted at
$v_{0},\ldots,v_{\lfloor\log\Delta\rfloor}$ is smaller than
$\lceil\log(n+1)\rceil+1$, we assign the remaining suffix of $M$ such that:

  * •

the $i$th bit of the remaining suffix is assigned to $v_{i}$ for
$i\in[0,\lfloor\log\Delta\rfloor]$ (note that $v_{i}$ has been assigned only
$2$ bits before, by (c));

  * •

up to two last remaining bits are stored in the root $r$.

Now, it is sufficient to show that the number of assigned bits is at least
$\lceil\log{(n+1)}\rceil+1$. If the degree of the root $r$ is at least
$\lfloor\log\Delta\rfloor+1$, then all tress rooted in marked children can
store cumulatively
$\sum_{k=0}^{\lfloor\log\Delta\rfloor}\lceil\log{(n_{v_{k}}+1)}\rceil$ bits by
the induction hypothesis. As we choose nodes with the biggest subtrees,
$\sum_{k=0}^{\lfloor\log\Delta\rfloor}n_{v_{k}}\geq\frac{\lfloor\log\Delta\rfloor+1}{\Delta}n$.
Moreover, as described above, we can store additional
$\lceil\log\Delta\rceil+1$ bits in $v_{0},\ldots,v_{\lfloor\log\Delta\rfloor}$
and 2 bits in the root $r$. In total this gives

$\displaystyle\sum_{k=0}^{\lfloor\log\Delta\rfloor}\lceil\log{(n_{v_{k}}+1)}\rceil+\lceil\log\Delta\rceil+1+2$
$\displaystyle\geq\sum_{k=0}^{\lfloor\log\Delta\rfloor}\log{(n_{v_{k}}+1)}+\log\Delta+2$
$\displaystyle\geq\log\left(\prod_{k=0}^{\lfloor\log\Delta\rfloor}(n_{v_{k}}+1)\right)+\log\Delta+2$
$\displaystyle\geq\log\left(\left(\sum_{k=0}^{\lfloor\log\Delta\rfloor}n_{v_{k}}\right)+1\right)+\log\Delta+2$
$\displaystyle\geq\log\left(\frac{\lfloor\log\Delta+1\rfloor}{\Delta}n+1\right)+\log\Delta+2$
$\displaystyle\geq\log\left(\frac{n+1}{\Delta}\right)+\log\Delta+2$
$\displaystyle\geq\log{(n+1)}+2\geq\lceil\log{(n+1)}\rceil+1$

bits stored in the whole subtree.

If the root $r$ of the tree has $x<\lfloor\log\Delta\rfloor+1$ children then
we have in total

$\displaystyle\sum_{k=0}^{x-1}\lceil\log{(n_{v_{k}}+1)}\rceil+x+2$
$\displaystyle\geq\sum_{k=0}^{x-1}\log{(n_{v_{k}}+1)}+2$
$\displaystyle\geq\log\left(\prod_{k=0}^{x-1}(n_{v_{k}}+1)\right)+2$
$\displaystyle\geq\log\left(\left(\sum_{k=0}^{x-1}n_{v_{k}}\right)+1\right)+2$
$\displaystyle\geq\log\left(n-1+1\right)+2$
$\displaystyle\geq\log\left(n\right)+2$
$\displaystyle\geq\lceil\log{(n+1)}\rceil+1$

bits stored in the whole subtree. These inequalities conclude the proof of the
inductive step and thus give the proof of the lemma.

∎

####  3.1.2 Labeling scheme

In this section we describe the labeling scheme CompactLabels which combines
the so-called $\Delta$-learning primitive from [19], the construction of a
broadcast tree with help of the algorithm Executor from Theorem 1, and the
limited-degree subtree described in Lemma 3.

The labels will consist of the root bit and three disjoint blocks:
$\Delta$-block, BroadcastTree-block and Message-block.

$\Delta$-block and the root bit. First, we choose a node $r$ with the largest
degree $\Delta$ in the graph $G$, and mark $r$ using the one-bit flag root.
That is, $\textsc{root}_{r}=1$ and $\textsc{root}_{v}=0$ for each $v\neq r$.

Then, we describe $O(\log\log\Delta)$-bit strings called $\Delta$-blocks which
will be used to learn the value of $\Delta$ by the node $r$. The root $r$ is
assigned the pair $(x,0)$, where $x$ is the binary representation of the
integer $\lfloor\log\Delta\rfloor+1$. This integer is the size of the binary
encoding of $\Delta$. Then we choose $\lfloor\log\Delta\rfloor+1$ neighbors of
$r$ and assign them consecutive natural numbers in the range
$[1,\lfloor\log\Delta\rfloor+1]$. The $\Delta$-block of the $i$th chosen node
is equal to the pair $(a_{i},b_{i})$ where $a_{i}$ is the binary
representation of $i\in[\lfloor\log\Delta\rfloor+1]$ of length
$\lfloor\log(\lfloor\log\Delta\rfloor+1)\rfloor+1$, with leading zeros, and
$b_{i}$ is the $i$th bit of the binary representation of $\Delta$. The
$\Delta$-blocks of other nodes are equal to the tuple $(0,0)$. As the value of
$\log\Delta$ can be encoded on $O(\log\log\Delta)$ bits, the length of
$\Delta$-blocks is $O(\log\log\Delta)$.

BroadcastTree-block. We apply Corollary 1 to construct the broadcast tree
$T_{\textsc{Executor}}$ of the graph with root (source vertex) $r$ and assign
$O(1)$-bit labels to nodes, used by the acknowledged broadcast algorithm
ExecAck working in $O(D\log n+\log^{2}n)$ rounds (Corollary 1).

Message-block. Let $M$ be the binary representation of the size $n$ of the
graph. The message-block is the concatenation of two blocks: index and
message.

We apply Lemma 3 in order to construct a subtree $T^{\prime}$ of
$T_{\textsc{Executor}}$ such that the degree of $T^{\prime}$ is not larger
than $\lfloor\log\Delta\rfloor+1$ and each node of $T^{\prime}$ is assigned a
substring of $M$ of length at most $3$. To each node $v$ of $T^{\prime}$ apart
from the root we assign a natural number $k_{v}$ such that the numbers
assigned to the children of any node are consecutive integers starting from
$0$. For a node $v$ of $T^{\prime}$, the block index of fixed length
$O(\log\log\Delta)$ is the binary representation of the integer
$k_{v}\in[1,\lfloor\log\Delta\rfloor]+1$ (with leading zeros), where $v$ is
chosen as the child with number $k_{v}$ of its parent. The substring of length
at most 3 assigned to each node of $T^{\prime}$ according to Lemma 3 is the
block message of this node. The concatenation of these substrings of $M$ forms
the string $M$ and substrings are assigned to nodes of $T^{\prime}$ in post-
order, i.e., the substring assigned to a given node $v$ is situated in $M$
after the substrings assigned to the children of $v$ in $T^{\prime}$, and
substrings are assigned to the children $w$ in increasing order of $k_{w}$.
The blocks index and message of nodes outside of tree $T^{\prime}$ are the
string $(0)$.

Conceptually, the label of a node is the concatenation of the root bit, the
$\Delta$-block, the Broadcast Tree-block and the Message-block. In order to
mark separations between the different blocks, we use the standard trick: the
bit 1 is coded as 10, the bit 0 is coded as 01 and separations are coded as
00. This does not change the complexity of the label length, hence our
labeling scheme has length $O(\log\log\Delta)$.

####  3.1.3 A simple size discovery algorithm

In this section we describe a simple size discovery algorithm using the above
labeling scheme and working in time $O(D\log n+\log^{2}n)$. We will then show
how to improve this algorithm to get the optimal time $O(\log^{2}n)$.

We first design the size discovery algorithm AuxiliarySD, which uses the
labeling scheme described in the previous section. The algorithm AuxiliarySD
is a composition of three procedures, $\Delta$-learning, Ack-broadcast, and
Size-learning, corresponding to the three blocks of the labels described
above: $\Delta$-block, BroadcastTree-block and Message-block.

Procedure $\Delta$-learning.
This procedure lasts $\lfloor\log\Delta\rfloor+1$ rounds. In the $i$th round,
the node with $\Delta$-block $(a_{i},b_{i})$ for $i>0$ transmits the message
with two bits: $0$ and $b_{i}$. In each round all nodes except the root $r$
(i.e., the node with the root bit equal to $1$) ignore messages with the value
of the first bit equal to $0$ and $r$ stores consecutive bits $b_{i}$. The
root $r$ also knows the value of $\lfloor\log\Delta\rfloor+1$ stored in its
label, so it will know the number of rounds of the $\Delta$-Learning
procedure.

Procedure Ack-broadcast
We execute algorithm ExecAck from Corollary 1 with the source vertex $r$, the
labels from the BroadcastTree-block and the broadcast message equal to the
binary string encoding the value of $\Delta$. As we use the algorithm solving
the acknowledged broadcast problem, all nodes know the number of the last
round of this procedure.

Procedure Size-learning
The goal of this procedure is to learn the binary representation $M$ of the
size $n$ of the graph that is distributedly stored in nodes of the subtree
$T^{\prime}$ of the broadcast tree $T_{\textsc{Executor}}$, as described in
the previous section.

Let $L$ be the number of levels of the broadcast tree $T_{\textsc{Executor}}$.
The procedure Size-learning is split into phases $1,\ldots,L$ such that the
strings message stored in nodes from the level $L-i+1$ are transmitted to
their parents in phase $i$, together with messages containing strings message
received by those nodes from their subtrees. Each phase lasts
$\lfloor\log\Delta\rfloor+1$ rounds. At the beginning of the phase $i$, each
node $v$ of $T^{\prime}$ of level $L-i+1$ reconstructs its message from all
messages received in previous rounds and its own string message. As the
labeling scheme uses post-order encoding, the node $v$ first concatenates the
messages of its children in $T^{\prime}$ in the order of numbers assigned to
them and then adds its own string message at the end of the string to get
$M_{v}$, the part of $M$ stored in its subtree. Assume that the node $v$ of
level $L-i+1$ has index that is the binary representation of the integer
$k_{v}\in[1,\lfloor\log\Delta\rfloor+1]$. Then, $v$ transmits $M_{v}$ in the
round $k_{v}$ of phase $i$.

######  Lemma 4.

The algorithm AuxiliarySD solves the size discovery problem using a labeling
scheme of length $O(\log\log\Delta)$, and it works in time
$O(T_{\textsc{Executor}}(n,D)\cdot\log\Delta)$, where
$T_{\textsc{Executor}}(n,D)=O(D\log n+\log^{2}n)$ is the time of the broadcast
algorithm Executor from Theorem 1.

###### Proof.

Procedure $\Delta$-learning works in time $O(\log\Delta)$. Time complexity of
Procedure Ack-broadcast is $O(T_{\textsc{Executor}}(n,D))$ by Corollary 1.
Procedure Size-learning takes $O(\log\Delta)$ rounds for each round of
ExecAck. Thus, the claimed time complexity of AuxiliarySD follows from Theorem
1 and Corollary 1. The $O(\log\log\Delta)$ bound on the length of the labeling
scheme follows from Corollary 1 and Lemma 3.

In order to prove correctness, it remains to show that all messages of nodes
of $T^{\prime}$ will be successfully delivered to their parents during
Procedure Size-learning. As each node $v$ has (at most) one child with the
number $j\in[1,\lfloor\log\Delta\rfloor+1]$ in its Message-block, children of
$v$ will transmit in different rounds of the algorithm. Nevertheless, a child
$v^{\prime}$ of $v$ might collide with a child $u^{\prime}$ of another node
$u$ during an execution of Procedure Size-learning, provided that
$\textit{level}(u^{\prime})=\textit{level}(v^{\prime})$ and
$k_{u^{\prime}}=k_{v^{\prime}}$. However, as
$\textit{level}(u^{\prime})=\textit{level}(v^{\prime})$, the nodes
$u^{\prime}$ and $v^{\prime}$ receive the broadcast message from their parents
$u$, $v$ in the same round $l=\textit{level}(u^{\prime})$. Moreover, their
parents $u$, $v$ are different since $k_{u^{\prime}}=k_{v^{\prime}}$ and each
node might have at most one child with a given value of index. Thus, reception
of messages from $u$, $v$ by $u^{\prime}$ and $v^{\prime}$, respectively, in
the round $l$ implies that there is no edge $(u,v^{\prime})$ nor
$(v,u^{\prime})$ in the graph. This fact in turn contradicts our assumption
that the messages of $u^{\prime}$ and $v^{\prime}$ cause a collision
preventing delivery of their messages to the parents $u$ and $v$. ∎

Now, we combine Lemma 4 with Lemma 2 to construct an improved version of
AuxiliarySD, called GeneralSD. The goal is to get rid of the additional
$\log\Delta$ multiplicative factor in the time complexity of a size discovery
algorithm based on the broadcast algorithm Executor.

Given a graph $G$, we first compute the number $t_{G}$ of rounds of the
execution of Executor on $G$. If $t_{G}<\log n$, then we use the labeling
scheme and the algorithm from Lemma 4. As the number of levels of the tree
$T_{\textsc{Executor}}$ is not larger than the number of rounds of the
algorithm, the number of rounds of the size discovery algorithm is
$O(t_{G}\log\Delta)=$ $O(\log^{2}n)$.

If $t_{G}\geq\log n$, we use the constant-length labeling scheme and the
broadcasting algorithm ExecAck from Lemma 2, with the binary representation of
the size $n$ of the graph as the message $M$. Thus, we obtain an algorithm
which solves the size discovery problem in time $O(D\log n+\log^{2}n)$ using a
labeling scheme of length $O\left(1+\frac{\log n}{t_{G}}\right)=$ $O(1)$.

Finally, in order to make the nodes of the graph aware of the chosen variant
of the algorithm, we add one bit to all labels which contains the information
whether or not $t_{G}<\log n$. Given the value of this bit, the nodes work
according to instructions of the former or the latter algorithm described
above. Thus, we obtain the following result.

######  Theorem 2.

The algorithm GeneralSD solves the size discovery problem using a labeling
scheme of length $O(\log\log\Delta)$, and works in time $O(D\log
n+\log^{2}n)$.

###  3.2 Fast algorithm for size discovery

Now, we design the algorithm FastSD, which solves the size discovery problem
in time $O(\log^{2}n)$ using a labeling scheme with asymptotically optimal
length $O(\log\log\Delta)$. Actually, if the diameter of the graph is
$\Omega(\log n)$, constant-length labels are sufficient.

In Section 3.2.1, we generalize the recent labeling schemes for broadcast to
the multi-source broadcast problem. Then, in Section 3.2.2, we give the idea
of our new size discovery algorithm, using the multi-source broadcast
algorithm. Finally, in Section 3.2.3, we give details of our algorithm with
proofs of its correctness and efficiency.

####  3.2.1 Multi-source broadcast

For the purpose of faster size discovery, we need a generalization of the
result from [8] regarding the multi-source broadcast problem. Let $G=(V,E)$ be
a graph and let a non-empty set $S\subset V$ be the set of _sources_. Assuming
that all nodes from $S$ know the broadcast message $M$, the goal of _multi-
source broadcast_ is to deliver the message $M$ to all nodes of $G$. Let the
_distance_ from a node $v\in V$ to $S\subset V$ be the minimum of distances
from $v$ to $s$ in $G$, over all $s\in S$. Moreover, let the diameter $D_{S}$
of $G$ with respect to $S$ be the maximum of distances from $v$ to $S$, over
all $v\in V$.

We construct the multi-source broadcast algorithm MBroadcast through a simple
modification of the broadcast algorithm Executor from [8]. The labeling scheme
for the (single-source) broadcast algorithm from [8] is based on the
probabilistic broadcast algorithm from [3]. As one can see in Section 6.3 of
[8] (Lemmas 9 and 10), the probabilistic analysis depends merely on the length
of a shortest path from a node which knows the broadcast message initially to
a considered node $v$. More precisely, the only differences with respect to
Executor concern the definition of the sets $\text{FRONTIER}_{1}$ and
$\text{DOM}_{1}$, i.e., the set of uninformed nodes that have an informed
neighbor before round $1$ and the set of informed nodes that is a minimal
dominating set of $\text{FRONTIER}_{1}$. As there is exactly one informed node
$s$ at the beginning in the broadcast problem, we have
$\text{DOM}_{1}=\\{s\\}$ and $\text{FRONTIER}_{1}$ is equal to the set of
neighbors of $s$, in the labeling scheme used by Executor. For the multi-
source broadcast problem, we

  * •

set $\text{FRONTIER}_{1}=$ $\\{v\,|\,(s,v)\in E\text{ and }v\not\in S\\}$,

  * •

choose a subset of $S$ that is a minimum dominating set of
$\text{FRONTIER}_{1}$ and let this chosen subset of $S$ be $\text{DOM}_{1}$.

Then, the analysis from [8] works also for the multi-source broadcast problem
and it implies a multi-source broadcast algorithm MBroadcast using a constant-
length labeling scheme and working in time $O(D_{S}\log n+\log^{2}n)$.

######  Corollary 2.

Algorithm MBroadcast solves the multi-source broadcast problem using a
labeling scheme of length $O(1)$, and works in time $O(D_{S}\log
n+\log^{2}n)$, where $S$ is the set of sources.

Given the above multi-source broadcast algorithm, we can describe our faster
size discovery algorithm. For this purpose we introduce a few auxiliary
notions.

Let $T_{\text{BFS}}$ be a BFS tree of the graph, where the root of the tree is
an arbitrary node $s$. Moreover, let $V_{i}$ be the set of nodes at distance
$i$ from the root, called the layer $i$ of $T_{\text{BFS}}$. Thus, in
particular, $V_{0}=\\{s\\}$.

####  3.2.2 The idea of the $O(\log^{2}n)$-time size discovery algorithm

If the diameter $D$ of the graph $G$ is $O(\log n)$, we simply apply GeneralSD
which gives the desired $O(\log^{2}n)$ time bound. Otherwise, we conceptually
split the graph $G$ into subgraphs of small diameter and then distribute
information about the value of $n$ in these subgraphs separately. Still, we
have to assure that collisions caused by edges connecting different subgraphs
do not prevent successful execution of our subroutines in the considered
subgraphs. For brevity, we introduce the notation $\text{lg
}n=\lceil\log(n+1)\rceil$, i.e., $\text{lg }n$ is the length of the binary
representation of the natural number $n$. We say that a layer $V_{i}$ is
_green_ iff $\lfloor i/\text{lg }n\rfloor$ is an even number; i.e., the layers
$[j\text{lg }n,(j+1)\text{lg }n-1]$ are green for each even number $j\geq 0$.
The nodes from layers $[j\text{lg }n,(j+1)\text{lg }n-1]$ for even $j$ form
the $j$th _stripe_ $X_{j}$. Thus, we have the 0th, 2nd, 4th stripe and so on.
Moreover, two consecutive stripes $X_{j}$ and $X_{j+2}$ are “separated” by
nodes from the layers $V_{(j+1)\text{lg }n},V_{(j+1)\text{lg
}n+1},\ldots,V_{(j+2)\text{lg }n-1}$ which do not belong to any stripe. Nodes
from each stripe are called _green_. Moreover, nodes from the last layer
$V_{(j+1)\text{lg }n-1}$ of the $j$th stripe for each even $j$ are called
_super-green_.

Our algorithm FastSD (an abbreviation of Fast Size Discovery) either executes
GeneralSD (if $D=O(\log n)$) with appropriate labels or it consists of two
stages:

  * Stage 1: In each stripe separately and in parallel, we execute an algorithm which ensures that, at the end of the stage, all super-green nodes from the stripe (i.e., nodes from the last layer $(j+1)\text{lg }n+1$ of the stripe $j$) learn the value of $n$ at the end of the stage. We perform this task in two phases. For the first phase, we choose a minimal set $U_{j}$ of nodes from the first layer of the stripe (called a minimal BFS-cover) such that each super-green node in the stripe $j$ is reachable from this set $U_{j}$, i.e., there is a BFS-path from a node of $U_{j}$ to this node. Then, for each element of $u\in U_{j}$ we choose a path of length $\text{lg }n$ such that it is a shortest path from $u$ to the last layer $(j+1)\text{lg }n-1$ of the stripe $j$. Moreover, we guarantee that those paths are conflict-free, i.e., there are no edges connecting nodes on different layers of different paths from the chosen family of paths. For each such path, the value of $n$ is then encoded in $1$-bit parts along the nodes of the path. In Phase 1 we “collect” these $1$-bit parts in appropriate nodes from the BFS-cover $U_{j}$ and, in Phase 2, we use the multi-source broadcast algorithm MBroadcast with $U_{j}$ as the the set of sources and $D=\log n$ in order to broadcast the size $n$ to super-green nodes (i.e., the nodes on the layer $(j+1)\text{lg }n-1$). As the consecutive stripes are “separated” by $\log n$ layers, we can execute Phase 1 separately in each stripe without the risk that interferences between nodes from different stripes cause any problem.

  * Stage 2: Execute the multi-source broadcast algorithm MBroadcast (see Corollary 2) with $S$ equal to the set of all super-green nodes, i.e., $S$ composed of the nodes from the layers $(j+1)\text{lg }n-1$, where $j$ is even and $(j+1)\text{lg }n-1$ is not larger than the height of the BFS tree and $D_{S}=2\text{lg }n$. The broadcast message in the execution of MBroadcast is equal to the binary encoding of $n$, known to the nodes from $S$ after Stage 1. As each node of the graph is at distance $\leq 2\text{lg }n$ from some super-green node, all nodes learn the value of $n$ in Stage 2.

####  3.2.3 Details of algorithm FastSD

We say that a path $P=(x_{1},\ldots,x_{k})$ in a graph $G$ with a fixed source
node $s$ is a _BFS-path_ if, for each consecutive nodes $x_{i}$ and $x_{i+1}$
on $P$, the layer of $x_{i+1}$ is by one larger than the layer of $x_{i}$. In
other words, each edge of the path increases the distance from the source node
$s$ by one. Thus, in particular, we do not use edges connecting nodes from the
same layer. We say that $v$ is _BFS-reachable_ from $u$ if there exists a BFS-
path from $u$ to $v$.

In order to implement Stage 1 of FastSD, we first build a _BFS-cover_ of
stripe $X_{j}$ by the nodes from the first layer $V_{j\log n}$ of the stripe,
for each even $j$ (see Figure 1).

######  Definition 2 (BFS-cover).

For an even natural number $j$, the set of nodes $U_{j}\subseteq V_{j\log n}$
is a BFS-cover of the stripe $X_{j}=\bigcup_{i=j\text{lg }n}^{(j+1)\text{lg
}n-1}V_{i}$ if, for each node $v\in V_{(j+1)\text{lg }n-1}$, there exists a
BFS-path $u_{0},u_{1},\ldots,u_{\text{lg }n-1}=v$ such that $u_{i}\in
V_{j\text{lg }n+i}$ for each $i\in[0,\text{lg }n-1]$, and $u_{0}\in U_{j}$. In
other words, the path $u_{0},\ldots,u_{\text{lg }n-1}$ starts at some node
from the given BFS-cover $U_{j}$ and each edge of the path goes to the layer
with larger index.

We say that a BFS-cover $U_{j}$ of the stripe $X_{j}$ is a _minimal BFS-cover_
of the stripe $X_{j}$ if no proper subset $U^{\prime}$ of $U_{j}$ is a BFS-
cover of $X_{j}$. A set of BFS-paths $P_{1},\ldots,P_{k}$ is _conflict-free_
if, for each $i\neq j$, there is no edge $(x_{i},x_{j})$ in the graph such
that $x_{i}\in P_{i}$, $x_{j}\in P_{j}$, $x_{i}$ and $x_{j}$ belong to
different layers.

######  Lemma 5.

Let $U_{j}=\\{u_{1},\ldots,u_{k}\\}$ be a minimal BFS-cover of the stripe
$X_{j}$. Then, there exists a set of _conflict-free_ BFS-paths
$\\{P_{1},\ldots,P_{k}\\}$ such that, for each $i\in[k]$:

  * •

$P_{i}$ starts at $u_{i}$,

  * •

the final node of $P_{i}$ is a super-green node of the stripe $X_{j}$,

###### Proof.

As $U_{j}$ is a minimal BFS-cover, the following condition holds for each
$l\in[k]$: there exists a (supergreen) node $y_{l}\in V_{(j+1)\text{lg }n-1}$
in the stripe $X_{j}$, such that $u_{l}$ and $y_{l}$ are connected by a BFS-
path and there is no BFS-path from $u_{i}$ to $y_{l}$ for each $i\neq l$.
Indeed, if this property does not hold for some $l\in[k]$, then
$U_{j}\setminus\\{u_{l}\\}$ is also a BFS-cover which would contradict
minimality of $U_{j}$. A node $y_{l}$ satisfying the above stated property
will be called a _witness_ of $u_{l}$.

Given the above property, we choose the paths $P_{1},\ldots,P_{k}$ such that
$P_{l}$ is a BFS-path connecting $u_{l}$ with its witness $y_{l}$ and
therefore there is no BFS-path from any other element $u_{i}\in U_{j}$ to
$y_{l}$, for each $i\in[k]$, $i\neq l$. We claim that the paths
$P_{1},\ldots,P_{k}$ satisfy the properties stated in the lemma. For
contradiction, assume that there exists an edge $(x_{i},x_{l})$ such that
$x_{i}$ belongs to $P_{i}$, $x_{l}$ belongs to $P_{l}$, $i\neq l$, $x_{i}$ and
$x_{l}$ are located in different layers. As the layers of nodes are determined
by their depth in the BFS-tree $T_{\text{BFS}}$, each edge of the graph $G$
connects either nodes from consecutive layers or from the same layer. Thus,
without loss of generality we can assume that
$\textit{layer}(x_{i})=\textit{layer}(x_{l})+1$. This fact in turn implies
that there exists a BFS-path from $u_{l}$ to $y_{i}$, the witness of $u_{i}$.
Indeed, such a path contains edges of $P_{l}$ until $x_{l}$, then the edge
$(x_{l},x_{i})$ followed by the edges of $P_{i}$ starting from $x_{i}$. This
contradicts our choice of $y_{1},\ldots,y_{k}$ as witnesses of
$u_{1},\ldots,u_{k}$. Thus the chosen set of paths $\\{P_{1},\ldots,P_{k}\\}$
is conflict-free and satisfies the properties in the lemma. ∎

Let $M=M[1]M[2]\cdots M[\text{lg }n]$ be the binary representation of $n$. In
order to facilitate implementation of Stages 1 and 2 of FastSD, we construct
labels of nodes in a given (green) stripe $X$ in the following way (see Figure
1):

  1. 1.

A minimal BFS-cover $U=\\{u_{1},\ldots,u_{k}\\}$ of the stripe $X$ is chosen,
along with the set of conflict-free paths
$\mathcal{P}=\\{P_{1},\ldots,P_{k}\\}$ of length $\text{lg }n$, such that
$P_{i}$ starts at $u_{i}$ and ends at a node in the last layer of $X$ (i.e.,
at a supergreen node).

  2. 2.

The set $X_{\text{BFS}}\subseteq X$ is determined such that $x\in
X_{\text{BFS}}$ if $x$ is BFS-reachable from some element of the BFS-cover
$U$. (Observe that, although each node from the last layer of a stripe is BFS-
reachable from $U$ by the definition of a BFS-cover, it might be the case that
nodes on smaller layers of the stripe are not reachable from $U$.)

  3. 3.

The label of each node $v$ is a concatenation of the following strings:

    1. (a)

a 4-bit string composed of flags $\textsc{reach}_{v}$, $\textsc{super-
green}_{v}$, $\textsc{cover}_{v}$, $\textsc{paths}_{v}$ indicating whether $v$
is green and it belongs to $X_{\text{BFS}}$ of its stripe $X$, whether $v$ is
super-green, whether $v$ belongs to the chosen BFS-cover $U$ of its stripe,
and whether $v$ belongs to one of the chosen cover-free paths
$\mathcal{P}=\\{P_{1},\ldots,P_{k}\\}$ of its stripe, respectively;

    2. (b)

$M_{v}$: a one-bit string defined as follows. If $v$ is the $i$th node of a
path $P_{l}$ from the above set of conflict-free paths, then $M_{v}$ is equal
to $M[i]$; otherwise, the value of $M_{v}$ is 0;

    3. (c)

$B_{v}$: the constant-length label assigned to $v$ by the labeling scheme for
the multi-source broadcast algorithm MBroadcast, with the graph
$G^{\prime}=(V^{\prime},E^{\prime})$, where $V^{\prime}=X_{\text{BFS}}$,
$E^{\prime}$ is the set of edges of $G$ connecting nodes from
$X_{\text{BFS}}$, and the set of sources $S$ is equal to $U$.

    4. (d)

$\text{S2}_{v}$: the constant-length label assigned to $v$ by the labeling
scheme for the multi-source broadcast algorithm MBroadcast, with the
communication graph $G$, where the set of sources $S$ is equal to the set of
all super-green nodes (i.e., such nodes $v$ that $\textsc{super-
green}_{v}=1$).

Figure 1: An example illustrating the notions and terms from the construction
of FastSD. The edges denote paths of length $\frac{1}{2}\text{lg }n$. The set
$\\{u,v\\}$ is a minimal BFS-cover – the red edges show that each node from
the layer $(j+1)\text{lg }n-1$ is reachable from $\\{u,v\\}$ by a BFS-path.
The blue edges form a set of conflict-free BFS-paths described in Lemma 5. The
node $w$ is an example of a node which is not active in Phase 2 of Stage 1,
since $w\not\in X_{\text{BFS}}$. However, $w$ is at distance $\leq 2\text{lg
}n$ from some super-green node from the layer $(j-1)\text{lg }n-1$ (stripe
$j-2$) and therefore $w$ receives a message with the size of the graph in
Stage 2.

Using the above described labels, Stage 1 for a stripe $X$ is implemented as
follows:

Phase 1: collecting the value of $n$ at all nodes from the BFS-cover $U$.

  * •

Round 1: each super-green node $v$ from $\mathcal{P}$ (i.e., each $v$ such
that $\textsc{super-green}_{v}=1$ and $\textsc{paths}_{v}=1$) sends $M_{v}$.

  * •

Rounds $2,3,\ldots,\text{lg }n$: each node $v$ with $\textsc{paths}_{v}=1$
which received a message $M$ in the previous round sends the concatenation of
its bit $M_{v}$ and the received message $M$.

Phase 2: broadcast of the value of $n$ inside $X_{\text{BFS}}$.

Using the labels $B_{v}$, all nodes with $\textsc{reach}_{v}=1$ execute the
multi-source broadcast algorithm MBroadcast, where the set of sources $S$ is
equal to $U$ and the graph is $G^{\prime}=(V^{\prime},E^{\prime})$,
$V^{\prime}=X_{\text{BFS}}$ (determined by the flags $\textsc{cover}_{v}$) and
$E^{\prime}$ is the set of edges of $G$ connecting nodes from
$X_{\text{BFS}}$.

Stage 2 is an execution of the multi-source broadcast algorithm MBroadcast on
the whole graph $G$ using the labels $\text{S2}_{v}$ and thus with the source
set $S$ consisting of all super-green nodes (i.e., the nodes $v$ with
$\textsc{super-green}_{v}=1$).

######  Theorem 3.

Algorithm FastSD solves the size discovery problem in time $O(\log^{2}n)$
using a labeling scheme of length $O(\log\log\Delta)$.

###### Proof.

As the case when $D=O(\log n)$ follows directly from Theorem 2, we assume that
$D\geq\text{lg }n$. As there are no edges in a BFS-tree between nodes whose
layers differ by more than one, computations in different stripes with green
nodes do not interfere with each other, as the consecutive stripes are
separated by $\text{lg }n$ layers. Moreover, as the set of paths $\mathcal{P}$
in each stripe is conflict-free, Phase 1 works without conflicts, and finally
each node $u_{i}$ of the BFS-cover of the stripe (which is the source node of
the path $P_{i}$) receives the whole message $M$ containing the binary
representation of $n$, in $\text{lg }n$ rounds.

A potential problem with the implementation of Phase 2 might follow from the
fact that (most of) the nodes do not know the actual value of $n$ or $\text{lg
}n$ after Phase 1 and therefore they do not have access to information about
the round in which Phase 2 starts. Fortunately, the multi-source broadcast
algorithm requires only round synchronization of the set of source nodes $S$,
cf. Corollary 2. As the length of each path $P_{i}$ in the set of conflict-
free paths $\mathcal{P}$ of each stripe is exactly $\text{lg }n$, the nodes
from $U$ receive their messages during Phase 1 in the same round. As a minimal
BFS-cover $U$ of a stripe is equal to the set of sources for Phase 2 of Stage
1, we can implement Phase 2 despite the fact that most nodes do not know the
exact round number of the beginning of this phase.

In order to synchronize the beginning of Stage 2, we can use the fact that all
super-green nodes know the value of $n$ at end of Phase 2 of Stage 1.
Moreover, Phase 1 takes $\log n$ rounds and Phase 2 works in $O(D_{S}\log
n+\log^{2}n)$ rounds, where $D_{S}=\text{lg }n$, as we execute algorithm
MBroadcast on the set of BFS-reachable nodes from $U$ in each stripe. Thus,
the exact value of the upper bound $O(D\log n+\log^{2}n)$ on the time of an
execution of Phase 2 is also fully determined by $n$. As the value of $n$ is
known to the set of source nodes of an execution of the multi-source broadcast
algorithm in Stage 2 (recall that the set of sources is equal to the set of
super-green nodes of each stripe), those nodes are able to synchronize and
start an execution of Stage 2 simultaneously.

Recall that the set of super-green nodes is exactly the set of nodes of layers
$j\text{lg }n$ for even values of $j$. Thus, each node of the graph is at
distance at most $2\text{lg }n$ from a super-green node. Therefore, the multi-
source broadcast algorithm executed in Stage 2 delivers the value of $n$ to
all nodes of the graph.

Finally, let us emphasize the importance of the assumption that the diameter
of the graph is at least $\text{lg }n$. If the diameter of $G$ is smaller than
$\text{lg }n$ then there are no super-green nodes and therefore we are not
able to build conflict free BFS-paths with length $\text{lg }n$. This in turn
excludes the possibility of implementation of Stage 1. Hence we treat the case
when the number of layers is smaller than $\text{lg }n$ separately, by
executing GeneralSD. As the diameter $D$ of the graph is $O(\log n)$ in this
case, we obtain time complexity $O(D\log n+\log^{2}n)=O(\log^{2}n)$. ∎

###  3.3 Lower bound on time complexity of size discovery

In this section we show that the $O(\log^{2}n)$ time complexity of FastSD is
asymptotically optimal, as long as the length of the labeling scheme used by
the algorithm is $o(\log n)$. To this aim, we leverage a powerful technical
result from [1] originally proved as a part of a proof of the
$\Omega(\log^{2}n)$ lower bound on time complexity of broadcast in radio
networks, even for centralized algorithms.

Let $G=(U\cup V,E)$ be a bipartite graph, where $U,V$ are the parts of the
bipartition of $G$, i.e., $U\cap V=\emptyset$, and there are no edges between
nodes inside $U$ nor inside $V$, such that $|U|=|V|=n$ and there is no
isolated vertex in $U\cup V$. A _bipartite broadcast schedule_ for $G$ is a
sequence $U_{1},\ldots,U_{k}$ of subsets of $U$ such that, if one executes a
$k$-round radio network algorithm in $G$ with the set of transmitters in the
$i$th round equal to $U_{i}$ for each $i\in[k]$, then every node from $V$
receives (at least) one message during this execution of the algorithm. The
number of subsets $k$ is called the _size_ of the bipartite broadcast schedule
for $G$.

######  Theorem 4.

[1] There exists a constant $c>0$ such that, for each sufficiently large
natural number $n$, there exists a bipartite graph $G$ with sides of size $n$
such that the size of each bipartite broadcast schedule for $G$ is larger than
$c\log^{2}n$.

Equipped with Theorem 4, we are ready to prove the lower bound
$\Omega(\log^{2}n)$ on the time complexity of the size discovery problem with
short labels.

######  Theorem 5.

The time complexity of any algorithm solving the size discovery problem on all
graphs with size at most $n$, using labeling schemes of length smaller than
$\frac{1}{4}\log n$, is $\Omega(\log^{2}n)$.

###### Proof.

For the sake of contradiction assume that an algorithm $\mathcal{A}$ can solve
the size discovery problem on all graphs of size at most $n$ in time at most
$\frac{c}{2}\log^{2}n$, using labeling schemes of length smaller than
$\frac{1}{4}\log n$, where $c$ is the constant from Theorem 4. For
sufficiently large $m$, consider a sequence of bipartite graphs
$G_{1}=(U_{1}\cup V_{1},E_{1}),G_{2}=(U_{2}\cup
V_{2},E_{2}),\ldots,G_{m}=(U_{m}\cup V_{m},E_{m})$ such that the size of the
sides of $G_{i}$ is $m+i$ and the size of each bipartite broadcast schedule
for $G_{i}$ is larger than $c\log^{2}\left(2(m+i)\right)$. A sequence
$G_{1},G_{2},\ldots,G_{m}$ satisfying these conditions exists by Theorem 4.
Now, let $G^{\prime}_{i}$ be the graph obtained by adding a new node $s_{i}$
to $G_{i}$, connected by an edge with all nodes from $U_{i}$. Observe that
$G^{\prime}_{i}$ is connected for each $i\in[m]$. Thus, according to the above
assumptions and by the fact that $\mathcal{A}$ works in time at most
$\frac{c}{2}\log^{2}\left({2(m+i)+1}\right)$ on $G^{\prime}_{i}$, there exists
a node $v_{i}\in V_{i}$ for each $i\in[m]$, such that $v_{i}$ does not receive
any message during an execution of $\mathcal{A}$ on $G^{\prime}_{i}$. Nodes of
each graph $G^{\prime}_{i}$ have labels of size smaller than
$\frac{1}{4}\log(2(m+i)+1)$. Since
$\frac{1}{4}\log(2(m+i)+1)\leq\frac{1}{2}\log m$ for sufficiently large $m$,
all labels in all graphs $G^{\prime}_{i}$ have length at most $\frac{1}{2}\log
m$. Consequently, there are at most $2\sqrt{m}$ distinct labels assigned to
all nodes in all graphs $G^{\prime}_{i}$. Hence there exist $i,j\in[m]$,
$i\neq j$, such that the label of $v_{i}$ in $G^{\prime}_{i}$ and the label of
$v_{j}$ in $G^{\prime}_{j}$ are equal, while $v_{i}$ and $v_{j}$ do not
receive any message during executions of $\mathcal{A}$ on $G^{\prime}_{i}$ and
$G^{\prime}_{j}$, respectively. It follows that nodes $v_{i}$ and $v_{j}$ must
make the same decision concerning the size of graphs $G^{\prime}_{i}$ and
$G^{\prime}_{j}$, respectively. However, the sizes of these graphs are
different, which gives a contradiction. ∎

Since $O(\log\log\Delta)$ is $o(\log n)$ for any graph, and in view of the
lower bound $\Omega(\log\log\Delta)$ from [19] on the length of labeling
schemes permitting size discovery, Theorems 3 and 5 give the following
corollary.

######  Corollary 3.

Algorithm FastSD solves the size discovery problem on all graphs using a
labeling scheme of asymptotically optimal length $O(\log\log\Delta)$, and it
works in time $O(\log^{2}n)$, which is aymptotically optimal for size
discovery algorithms using asymptotically optimal labeling schemes.

##  4 Lower Bound on Lengths of Labels for Topology Recognition

We now start the investigation of the topology recognition problem. In this
section, we show that any algorithm for topology recognition in general graphs
requires a labeling scheme of length $\Omega(\log\Delta)$. This length is thus
exponentially larger than that sufficient to solve the easier problem of size
discovery. In fact, we will prove a stronger result: the above lower bound
holds even in the model with collision detection. Hence, till the end of this
section we assume that collision detection is available.

The proof is divided into two parts. We first show the lower bound of
$\Omega(\log n)$ for graphs of degree $2^{\Omega(\log n)}$. Second, we
generalize this result for graphs of arbitrary degree $\Delta$.

In our proof, we exploit the fact that each node in the graph $G$ has to learn
its degree. Intuitively, if the set $\\{\,deg(v)\mid v\in V\,\\}$ of node
degrees in $G$ is larger than the set $\\{\,\mathcal{L}(v)\mid v\in V\,\\}$ of
node labels then some two nodes $u,v\in V,$ such that $deg(u)\neq
deg(v)\land\mathcal{L}(u)=\mathcal{L}(v)$ have to learn their degrees through
their communication histories $\mathcal{H}$. We will construct a family of
graphs such that the labels have to be of length ${\Omega(\log\Delta)}$ so
that nodes with the same labels and different degrees could have different
communication histories.

We now formally define a communication history of a node for a given topology
recognition algorithm executed on a given graph. Intuitively, this is a record
of what the node learns during the execution of the algorithm (assuming
collision detection).

######  Definition 3.

(Communication history) Let $G=(V,E)$ be a graph and let $\mathcal{L}$ denote
a labeling scheme on $G$. Consider a topology recognition algorithm
$\mathcal{A}$ executed on $G$ and let $i$ be a round of this algorithm. For
each node $v\in V$, we define $\mathcal{H}_{i}(v)$ inductively such that
$\mathcal{H}_{i}(v)$ denotes the communication history of $v$ at the end of
the $i$th round of $\mathcal{A}$.

  * •

$\mathcal{H}_{0}(v)=\emptyset$, for all $v$.

  * •

If

    * –

$v$ transmits in the $i$th round, or

    * –

$v$ listens and more than one neighbor of $v$ transmits in the $i$th round (a
collission),

we append the special character #, denoting ”no message”, to $v$’s history,
i.e., $\mathcal{H}_{i}(v)=[\mathcal{H}_{i-1}(v),\texttt{\\#}]$,

  * •

If $v$ listens and none of its neighbors transmits in the $i$th round
(silence), we append $\varepsilon$ to $v$’s history, i.e.,
$\mathcal{H}_{i}(v)=[\mathcal{H}_{i-1}(v),\varepsilon]$.

  * •

If $v$ listens and successfully receives a message $m\in\\{0,1\\}^{*}$ in the
$i$th round (exactly one neighbor of $v$ transmits $m$), we append $m$ to
$v$’s history, i.e., $\mathcal{H}_{i}(v)=[\mathcal{H}_{i-1}(v),m]$.

$\mathcal{H}(v)$ denotes the communication history of $v$ at the end of the
last round of the execution of $\mathcal{A}$ on $G$.

###  4.1 The Lower Bound for Graphs with Large Degrees

In this section we define a family $\mathcal{G}$ of graphs of arbitrarily
large size $n$ with maximum degree $\Delta=2^{\Omega(\log n)}$, such that a
labeling scheme of the length $\Omega(\log n)$ is necessary to solve the
topology recognition problem on each suffciently large graph from this family.

Let $n$ be a sufficiently large natural number such that $n^{1/2}$ is an even
natural number. We construct an $n$-node graph $G_{n}=(V,E)$. The graph is
composed of $n^{1/2}$ components, each component is composed of $n^{1/2}$
nodes. Let $C_{i}$ denote the set of nodes from the $i$th component. Every
node is connected with every node from a different component, i.e., for every
$C_{i},C_{j}$ ($i\neq j$) and every pair of nodes $u\in C_{i},v\in C_{j}$ we
have $(u,v)\in E$. Let $C(v)$ denote the component to which a node $v$
belongs.

We now describe the set of edges connecting nodes of a component $C_{i}$
composed of $k=n^{1/2}$ nodes. We divide nodes of $C_{i}$ into two sets $A$
and $B$, each of size $k/2$. Let $a_{j}\in A$ denote the $j$th node from $A$,
and let $b_{j}\in B$ denote the $j$th node from $B$. Then, we connect $a_{j}$
with the first $j$ nodes from $B$:
$(a_{j},b_{1}),(a_{j},b_{2}),\dots,(a_{j},b_{j})\in E$. This concludes the
construction of $G_{n}$. Observe that each $G_{n}$ is connected. Note also
that for any component, the set of different degrees of nodes in this
component has size $k/2$. The degree of each node is in the range
$[n-2n^{1/2},n-n^{1/2}+1]$, since each component has size $n^{1/2}$. Note that
nodes of different degrees that have equal labels and equal communication
histories cannot learn that they have different degrees. The family
$\mathcal{G}$ consists of all graphs $G_{n}$, such that $n^{1/2}$ is an even
natural number.

An example of a graph from the family $\mathcal{G}$ is presented in Figure 2.

Figure 2: An illustration of the graph $G_{36}$ from the family $\mathcal{G}$.
The left picture depicts one component, the right picture depicts the whole
graph. Blue edges connect nodes from different components. For clarity, only
some of the inter-component edges are presented (each pair of nodes from
different components should be connected by an edge).

Observe that, for each natural number $n$, there is at most one graph of size
$n$ in the family $\mathcal{G}$.

Below, we make a simple but useful observation regarding lack of information
received by most of the nodes in graphs from $\mathcal{G}$ if at least two
nodes transmit in a round.

######  Fact 1.

If at least two nodes $u\neq v$ transmit in the $i$th round then, for every
node $w$ such that $C(w)\neq C(u)\land C(w)\neq C(v)$, $w$ does not hear any
message in the $i$th round.

We now define the canonical history, for a given graph $G$ from the family
$\mathcal{G}$ and a given topology recognition algorithm $\mathcal{A}$
executed on $G$. The canonical history is a specific communication history,
which will be common to many nodes of $G$ in the early stages of the execution
of a topology recognition algorithm. It has the property that a node with the
canonical history receives a message in a round $i$ iff every node in the
whole graph receives this message in this round.

######  Definition 4.

(Canonical history)

Fix a graph $G$ from the family $\mathcal{G}$, with a given labeling scheme
$\mathcal{L}$, and a topology recognition algorithm $\mathcal{A}$ executed on
$G$. With respect to $G$, $\mathcal{L}$ and $\mathcal{A}$, we define the
canonical history $\widehat{\mathcal{H}}_{i}$ at the end of the $i$th round as
follows:

  * •

$\widehat{\mathcal{H}}_{0}=\emptyset$.

  * •

$\widehat{\mathcal{H}}_{i}=[\widehat{\mathcal{H}}_{i-1},m]$, if there is
exactly one node in $G$ that transmits the message $m$ in the $i$th round.

  * •

$\widehat{\mathcal{H}}_{i}=[\widehat{\mathcal{H}}_{i-1},\texttt{\\#}]$, if at
least two nodes of $G$ transmit in round $i$,

  * •

$\widehat{\mathcal{H}}_{i}=[\widehat{\mathcal{H}}_{i-1},\varepsilon]$, if no
node of $G$ transmits in round $i$.

We then define the set of components sharing the canonical history.

######  Definition 5.

Fix a graph $G$ from the family $\mathcal{G}$, with a given labeling scheme
$\mathcal{L}$, and a topology recognition algorithm $\mathcal{A}$ executed on
$G$. We say that a node $v$ has the canonical history
$\widehat{\mathcal{H}}_{i}$ if $\mathcal{H}_{i}(v)=\widehat{\mathcal{H}}_{i}$
at the end of the $i$th round of the execution of $\mathcal{A}$ on $G$. A
component $C_{j}$ has the canonical history at the end of the $i$th round if
every node from that component has the canonical history at the end of this
round.

Let $\widehat{\mathcal{C}}_{i}$ denote the set of components of $G$ that have
the canonical history $\widehat{\mathcal{H}}_{i}$ at the end of the $i$th
round:

$\widehat{\mathcal{C}}_{i}=\\{\,C_{j}\mid\forall_{v\in
C_{j}}\mathcal{H}_{i}(v)=\widehat{\mathcal{H}}_{i}\,\\}.$

##### High-level idea of the proof of the lower bound.

A node with the canonical history does not have any information that
distinguishes it from other nodes with the canonical history, apart from its
label. In topology recognition, nodes with different degrees must make
different decisions (as each node has to situate itself in the graph), and
there are at least $\frac{1}{2}\sqrt{n}$ different degrees in each component
of a graph $G_{n}\in\mathcal{G}$. The communication history of all nodes at
the beginning is equal to the canonical history. We show that, in every round,
nodes from at most components can change their histories from the canonical to
a non-canonical one (Fact 4). Using this fact we show that some nodes change
their histories from the canonical one to non-canonical after at least
$\frac{1}{2}\sqrt{n}$ rounds. We also show that a node makes such a change
(from the canonical to non-canonical history) in round $i$ iff at least one
node from its component (call it a _trigger_) transmits a message in that
round (Lemma 7) and that nodes from at most one other component transmit
messages in that round (Fact 3). Using these properties we show that, for each
label $l$, at most two nodes with the label $l$ can be triggers. On the other
hand, we need a trigger in each component, so $\frac{1}{4}\sqrt{n}$ different
labels are needed which implies that the length of the labeling scheme is
$\Omega(\log n)$.

##### A detailed proof of the lower bound.

Below, we present a formal proof of the lower bound $\Omega(\log n)$ on the
length of a labeling scheme for topology recognition, following the above
described ideas.

######  Lemma 6.

Assume that a deterministic algorithm $\mathcal{A}$ solves the topology
recognition problem in every graph $G_{n}$ from the family $\mathcal{G}$ using
a labeling scheme $\mathcal{L}$ with at most $n^{1/4}$ distinct labels (for
$n>256$). Let $f$ be the time of the execution of $\mathcal{A}$ on $G_{n}$.
Then, the set of components that have the canonical history is empty after the
last round, i.e., $\widehat{\mathcal{C}}_{f}=\emptyset$.

###### Proof.

Recall that every component in $G_{n}$ has size $n^{1/2}$. For the sake of
contradiction, assume that $\widehat{\mathcal{C}}_{f}$ is nonempty. Pick any
$C_{j}\in\widehat{\mathcal{C}}_{f}$. Since there are at most $n^{1/4}$
distinct labels while the size of the set of degrees of nodes in $C_{j}$ is at
least $\frac{n^{1/2}}{2}$, there are at least two nodes $u,v\in C_{j}$ with
different degrees but with the same label and the same history
$\widehat{\mathcal{H}}_{f}$. These nodes must make the same decision upon
completion of $\mathcal{A}$ . Since algorithm $\mathcal{A}$ solves the
topology recognition problem, nodes $u$ and $v$ must output copies $R_{u}$ and
$R_{v}$ of $G_{n}$ with their respective positions $u^{*}$ and $v^{*}$ marked,
such that there exists an isomorphism $\phi$ from $R_{u}$ to $R_{v}$ with
$\phi(u^{*})=v^{*}$. This contradicts the fact that $u$ and $v$ have different
degrees in $G_{n}$. ∎

Let $\widehat{\mathcal{H}}$ be the sequence
$(\widehat{\mathcal{H}}_{0},\widehat{\mathcal{H}}_{1},\ldots)$ of canonical
histories for a given graph $G\in\mathcal{G}$ with a labeling scheme
$\mathcal{L}$ and for a topology recognition algorithm $\mathcal{A}$. We say
that a component $C_{j}$ leaves $\widehat{\mathcal{H}}$ in the $i$th round if
$C_{j}\in\widehat{\mathcal{C}}_{i-1}\land
C_{j}\notin\widehat{\mathcal{C}}_{i}$. If a component $C_{j}$ leaves
$\widehat{\mathcal{H}}$ in the $i$th round then there is a node $v\in C_{j}$
such that
$\mathcal{H}_{i-1}(v)=\widehat{\mathcal{H}}_{i-1}\land\mathcal{H}_{i}(v)\neq\widehat{\mathcal{H}}_{i}$,
i.e., $v$ stops having the canonical history in round $i$. Let us discuss all
possible cases when a component may leave $\widehat{\mathcal{H}}$.

######  Lemma 7.

A component $C_{j}$ may leave $\widehat{\mathcal{H}}$ in the $i$th round only
in the case when at least one node from $C_{j}$ and at most one node from some
other component $C_{k}$ ($k\neq j$) transmit in the $i$th round.

###### Proof.

First, let us argue that there can be at most one node transmitting in some
other component than $C_{j}$ when $C_{j}$ leaves $\widehat{\mathcal{H}}$ in
the $i$th round. Indeed, if there are two different nodes transmitting in some
other components $C_{k},C_{l}$ ($k\neq j\land l\neq j$ but it is not necessary
that $k\neq l$) then for every node $v$ in $C_{j}$
($C_{j}\in\widehat{\mathcal{C}}_{i-1}$) we have
$\mathcal{H}_{i}(v)=[\widehat{\mathcal{H}}_{i-1},\texttt{\\#}]$. Moreover, if
there are two nodes transmitting in the $i$th round then
$\widehat{\mathcal{H}}_{i}=[\widehat{\mathcal{H}}_{i-1},\texttt{\\#}]$,
according to Definition 4.

Second, we will show that there must be at least one node from $C_{j}$
transmitting in the $i$th round when $C_{j}$ leaves $\widehat{\mathcal{H}}$ in
the $i$th round. Pick any node $v\in C_{j}$ such that
$\mathcal{H}_{i-1}(v)=\widehat{\mathcal{H}}_{i-1}\land\mathcal{H}_{i}(v)\neq\widehat{\mathcal{H}}_{i}$.
Consider the case when some message $m$ was appended to the canonical history
$\widehat{\mathcal{H}}_{i-1}$, i.e.,
$\widehat{\mathcal{H}}_{i}=[\widehat{\mathcal{H}}_{i-1},m]$. Then, by
Definition 4, there is exactly one node transmitting in the $i$th round. If
that node is not in $C_{j}$ then every node from $C_{j}$ receives the message
$m$ and it does not leave $\widehat{\mathcal{H}}$ in the $i$th round. So, some
node from $C_{j}$ must transmit in the $i$th round. Now, consider the case
when $\widehat{\mathcal{H}}_{i}=[\widehat{\mathcal{H}}_{i-1},\texttt{\\#}]$.
Then, by Definition 4, at least two nodes are transmitting in $G$ in round
$i$. However, it follows from the fact proved in the previous paragraph that
at most one of those nodes could not be in $C_{j}$. Finally, consider the case
when $\widehat{\mathcal{H}}_{i}=[\widehat{\mathcal{H}}_{i-1},\varepsilon]$.
Then, by Definition 4, no node is transmitting in $G$ in round $i$. The set of
nodes with the canonical history after round $i$ is equal to the set of nodes
with the canonical history after round $i-1$ and therefore no component leaves
$\widehat{\mathcal{H}}$ in the $i$th round. Hence, at least one node from
$C_{j}$ must transmit in round $i$, provided that $C_{j}$ leaves
$\widehat{\mathcal{H}}$ in round $i$. ∎

Now, we state a few facts that will facilitate the proof of our lower bound.
First, we observe that nodes with equal labels and histories behave in the
same way.

######  Fact 2.

Let $v$ be a node with label $\mathcal{L}(v)=l$ such that $v$ has the
canonical history at the end of round $i-1$, i.e.,
$\mathcal{H}_{i-1}(v)=\widehat{\mathcal{H}}_{i-1}$. If $v$ transmits in the
$i$th round, then all nodes $u$ such that
$\mathcal{L}(u)=l\land\mathcal{H}_{i-1}(u)=\widehat{\mathcal{H}}_{i-1}$ also
transmit in the $ith$ round.

Lemma 7 directly implies that no component can leave $\widehat{\mathcal{H}}$
in a round in which nodes from more than two components send messages.

######  Fact 3.

If there are at least three nodes in three different components transmitting
in a round, then no component leaves $\widehat{\mathcal{H}}$ in that round.

As a component can leave $\widehat{\mathcal{H}}$ only if at least one node
from that component transmits (Lemma 7) and no component leaves
$\widehat{\mathcal{H}}$ in a round with transmitters from more than two
components (Fact 3), we get the following fact.

######  Fact 4.

In any given round at most two components may leave $\widehat{\mathcal{H}}$.

Using the above facts and Lemmas 6, 7, we are ready to prove a lower bound on
the length of a labeling scheme necessary to solve the topology recognition
problem.

######  Theorem 6.

Any algorithm solving the topology recognition problem in a graph $G_{n}$ from
the family $\mathcal{G}$, for $n>8^{4}$, requires a labeling scheme with more
than $n^{1/4}$ distinct labels.

###### Proof.

For a contradiction, assume that there exists an algorithm $\mathcal{A}$ that
solves the topology recognition problem in a graph $G_{n}$ from the family
$\mathcal{G}$, for $n>8^{4}$, using a labeling scheme $\mathcal{L}_{n}$ with
at most $n^{1/4}$ distinct labels. It follows from Lemma 6 that all components
leave $\widehat{\mathcal{H}}$ during the execution of $\mathcal{A}$ on
$G_{n}$.

Consider all rounds when some component leaves $\widehat{\mathcal{H}}$. Let
$S_{p}\subseteq C_{p}$ be the subset of nodes of $C_{p}$ that transmit a
message in the round when $C_{p}$ leaves $\widehat{\mathcal{H}}$. From Lemma 7
we know that $S_{p}$ is nonempty. From Fact 4 there are at most two components
leaving $\widehat{\mathcal{H}}$ in any given round. Thus, the number of rounds
when some component leaves $\widehat{\mathcal{H}}$ is at least
${\frac{n^{1/2}}{2}}$. Consider the $j$th round when at least one component
leaves $\widehat{\mathcal{H}}$. Let $l_{j}$ denote the label of an arbitrary
node $v$ such that $v$ transmits in that round and $v$ is in the component
that leaves $\widehat{\mathcal{H}}$ in that round.

Let $t$ be the number of rounds in which some component(s) left
$\widehat{\mathcal{H}}$. Consider the multiset
$L=\\{l_{1},l_{2},\dots,l_{t}\\}$. We claim that each label occurs at most
twice in $L$. Indeed, assume that there are three indicies $i,j,k$ ($i<j<k$)
such that $l_{i}=l_{j}=l_{k}$, i.e., there are at least three occurrences of
the same label in $L$. Assume that $l_{i},l_{j},l_{k}$ are labels of nodes
from components $C_{i},C_{j},C_{k}$, respectively. Assume that the round
$i^{\prime}$ was the $i$th round of the execution of $\mathcal{A}$ on $G$ in
which some component left $\widehat{\mathcal{H}}$, i.e., $l_{i}$ is the label
of a node that was transmitting in the $i^{\prime}$th round. Recall that
$C_{i},C_{j},C_{k}\in\widehat{\mathcal{C}}_{i^{\prime}-1}$, however,
$C_{i}\notin\widehat{\mathcal{C}}_{i^{\prime}}$ and
$C_{j},C_{k}\in\widehat{\mathcal{C}}_{i^{\prime}}$. According to the
definition of the sequence $L$, the choice of the values of $i$, $i^{\prime}$
and in view of Lemma 7, some node $u\in C_{i}$ transmits in the round
$i^{\prime}$, such that $\mathcal{L}_{n}(u)=l_{i}$ and $u$ has the canonical
history at least up to the $(i^{\prime}-1)$st round, i.e.,
$\mathcal{H}_{i^{\prime}-1}(u)=\widehat{\mathcal{H}}_{i^{\prime}-1}$. Our
assumptions imply that there are two other nodes $v,w$ such that they have the
same label as $u$ and the same canonical history up to the $(i^{\prime}-1)$st
round, i.e.,

$v\in C_{j}\land w\in C_{k},$
$\mathcal{L}_{n}(u)=\mathcal{L}_{n}(v)=\mathcal{L}_{n}(w),$
$\mathcal{H}_{i^{\prime}-1}(u)=\mathcal{H}_{i^{\prime}-1}(v)=\mathcal{H}_{i^{\prime}-1}(w)=\widehat{\mathcal{H}}_{i^{\prime}-1}.$

Fact 2 implies that all these nodes transmit in the $i^{\prime}$th round.
However, Fact 3 implies that no component leaves $\widehat{\mathcal{H}}$ in
round $i^{\prime}$, which contradicts our assumption that $C_{i}$ actually
leaves $\widehat{\mathcal{H}}$ in this round. This contradiction implies that
each label occurs at most twice in $L$. Hence there are at least
${\frac{n^{1/2}}{4}}$ different labels in the multiset $L$.

Recall that the algorithm $\mathcal{A}$ uses a labeling scheme on $G_{n}$ with
at most $n^{1/4}$ distinct labels. However, for all $n>8^{4}$ we have
$\frac{n^{1/2}}{4}>n^{1/4}$. This contradiction concludes the proof. ∎

######  Corollary 4.

Any algorithm solving the topology recognition problem in all graphs from the
family $\mathcal{G}$ requires a labeling scheme of length $\Omega(\log n)$ on
$G_{n}$.

###  4.2 The Lower Bound for Graphs with Arbitrary Degrees

In this section we show that, for all positive integers $\Delta<n$, there
exists a graph $H_{\Delta,n}$ of maximum degree $\Theta(\Delta)$ and of size
$\Theta(n)$, such that any algorithm solving the topology recognition problem
in $H_{\Delta,n}$ requires a labeling scheme of length $\Omega(\log\Delta)$.
In order to prove this lower bound we use the family $\mathcal{G}$ of graphs
$G_{n}$ of maximum degrees $2^{\Omega(\log n)}$, where $n$ is the size of the
graph, constructed in Section 4.1.

Choose arbitrary positive integers $\Delta<n$. We construct a $\Theta(n)$-node
graph $H_{\Delta,n}$ from $\Theta(n/\Delta)$ isomorphic copies of a graph
$G_{k}$ from $\mathcal{G}$, for some $k=\Theta(\Delta)$. Let $k$ be the
smallest natural number such that $k\geq\Delta$ and $\sqrt{k}$ is a natural
even number. Let $G^{\prime}_{\Delta}$ denote the graph obtained by the
following slight modification of the graph $G_{k}$: add a new special node $s$
connected to all other nodes of $G_{k}$. Let $G^{\prime(i)}_{\Delta}$, for all
$i=1,2,\dots,\lceil\frac{n}{\Delta}\rceil$, denote the $i$th isomorphic copy
of the graph $G^{\prime}_{\Delta}$. All these copies are pairwise disjoint.

The graph $H_{\Delta,n}$ contains the above $\lceil\frac{n}{\Delta}\rceil$
disjoint isomorphic copies $G^{\prime(i)}_{\Delta}$ of $G^{\prime}_{\Delta}$,
for all $i=1,2,\dots,\lceil\frac{n}{\Delta}\rceil$. Moreover, we ensure
connectivity of $H_{\Delta,n}$ in the following way. Let $s_{i}$ denote the
special node of $G^{\prime(i)}_{\Delta}$. We connect every $s_{i}$ with
$s_{i+1}$ for each $i=1,2,\dots,\lceil\frac{n}{\Delta}\rceil-1$ by an edge, as
well as $s_{\lceil\frac{n}{\Delta}\rceil}$ with $s_{1}$. Thus the special
nodes of all graphs $G^{\prime(i)}_{\Delta}$ are connected in a ring. As the
graph $G^{\prime}_{\Delta}$ is connected, the graph $H_{\Delta,n}$ is
connected as well. Moreover, $H_{\Delta,n}$ has maximum degree
$\Theta(\Delta)$ and size $\Theta(n)$.

######  Theorem 7.

For all sufficiently large positive integers $\Delta<n$, there exists a graph
of size $\Theta(n)$ and of maximum degree $\Theta(\Delta)$ such that any
topology recognition algorithm for this graph requires a labeling scheme with
more than $\Delta^{1/4}$ distinct labels.

###### Proof.

We will show that the above defined graphs $H_{\Delta,n}$ satisfy the
statement of the theorem.

In order to get a contradiction, assume that there exists an algorithm
$\mathcal{A}$ that solves the topology recognition problem in $H_{\Delta,n}$
using a labeling scheme with at most $\Delta^{1/4}$ distinct labels, for
$\Delta>8^{4}$. Then, we can construct an algorithm $\mathcal{A}^{\prime}$
that solves the topology recognition problem in $G_{\Delta}$ with at most
$\Delta^{1/4}$ distinct labels as follows.

Consider the component $G^{\prime(1)}_{\Delta}$ of $H_{\Delta,n}$. To each
node $v$ of $G_{\Delta}$ we assign the label $(\mathcal{L}(v),E)$ such that:

  * •

The value of $\mathcal{L}(v)$ is equal to the label of the corresponding node
of the component $G^{\prime(1)}_{\Delta}$ of $H_{\Delta,n}$.

  * •

The value of $E$ is equal to an encoding of all the messages sent by $s_{1}$
during an execution of $\mathcal{A}$ on $H_{\Delta,n}$ specifying the content
of messages and rounds of transmissions of these messages.

Note that the value $E$ is common to all nodes $v$ of $G_{\Delta}$, and hence
the number of distinct labels $(\mathcal{L}(v),E)$ is the same as the number
of distinct labels $\mathcal{L}(v)$, i.e., at most $\Delta^{1/4}$. Using the
above described labels, the algorithm $\mathcal{A}^{\prime}$ works on
$G_{\Delta}$ as follows. Each node $v$ works according to the algorithm
$\mathcal{A}$, using the value $\mathcal{L}(v)$ as its label, with the
following modification. After each round $t$, node $v$ modifies its
communication history in this round using $E$, as follows. If $v$ sends a
message in round $t$ or $v$ detects a collision in round $t$ or $s_{1}$ does
not send a message in round $t$, then the communication history of $v$ in this
round does not change. However, if $v$ listens in round $t$, $v$ does not
detect a collision in round $t$ and $s_{1}$ sends a message $m$ in round $t$,
then $v$ replaces the term of its communication history in round $t$ by:

  * •

the message $m$, if $v$ does not receive any message in round $t$,

  * •

the collision symbol #, if $v$ does receive a message in round $t$.

(Intuitively, $v$ simulates the message that it would receive from $s_{1}$ in
the graph $H_{\Delta,n}$ or the collission which would result from the
transmission of $s_{1}$.) In the next round $v$ uses the modified
communication history and executes algorithm $\mathcal{A}$. Hence, for every
round $t$, the communication history of node $v$ when the above defined
algorithm is executed on $G_{\Delta}$ is the same as the communication history
of the corresponding node in $G^{\prime(1)}_{\Delta}$ when $\mathcal{A}$ is
executed on $H_{\Delta,n}$. Using the assumption that $\mathcal{A}$ solves the
topology recognition problem in $H_{\Delta,n}$, we conclude that
$\mathcal{A}^{\prime}$ solves the topology recognition problem in $G_{\Delta}$
for $\Delta>8^{4}$. This is a contradiction with Theorem 6 that concludes the
proof.

∎

The following corollary of Theorem 7 is the main result of this section.

######  Corollary 5.

For all positive integers $\Delta<n$, there exists a graph of maximum degree
$\Theta(\Delta)$ and of size $\Theta(n)$, such that any algorithm solving the
topology recognition problem on this graph requires a labeling scheme of
length $\Omega(\log\Delta)$.

##  5 Topology Recognition: Labeling and Algorithm

Our final result is a topology recognition algorithm working for any graph of
maximum degree $\Delta$ using a labeling scheme of length $O(\log\Delta)$.
This length is optimal, in view of Corollary 5. Our algorithm works in time
$O\left(D\Delta+\min(n,\Delta^{2})\right)$. First, in Section 5.1 we focus on
constructing a BFS tree of the graph and efficient broadcast/gathering
algorithms working in this tree. Then, in Section 5.2, the main topology
recognition algorithm is presented, using the broadcast and gathering
subroutines from Section 5.1.

###  5.1 Broadcast-gathering primitive

In this section we describe a labeling scheme of length $O(\log\Delta)$ and
algorithms for the (acknowledged) broadcast and gathering problems using this
scheme. Both algorithm work in time $O(D\Delta)$.

Consider a graph $G=(V,E)$ of maximum degree $\Delta$ and diameter $D$, with a
root node $r\in V$. In the gathering problem, each node $v\in V$ has some
message $M_{v}$ and the root $r$ has to learn all messages $M_{v}$.

Denote by $\textit{layer}(v)$ the distance from $r$ to a node $v$. We say that
$v$ is at layer $i$ if $\textit{layer}(v)=i$. Let $V_{i}$ be the set of nodes
at layer $i$. The neighborhood of a node $v$ in $G$ is denoted by
$\mathcal{N}(v)$ and the set of neighbors of $v$ at layer $i$ is denoted by
$\mathcal{N}_{i}(v)$. We fix an arbitrary strict total ordering on nodes
denoted by $\prec$. For each node $v$, its label $\mathcal{L}(v)$ is equal to
the tuple $(r_{v},\textit{leaf}(v),a_{v},b_{v},g_{v},\Delta)$, where $r_{v}$
is the $1$-bit flag indicating whether $v$ is the root node $r$,
$\textit{leaf}(v)$ is the bit indicating whether $v$ has any neighbors on
higher layers than $\textit{layer}(v)$, $a_{v}$ is the bit used for
acknowledged broadcast, while both $b_{v}$ and $g_{v}$, called _broadcast-
label_ and _gather-label_ , are special integer values used for broadcast and
gathering respectively, described in more detail below. More precisely, the
label $\mathcal{L}(v)$ is the concatenation of bits $r_{v}$,
$\textit{leaf}(v)$, $a_{v}$, and binary representations of integers $b_{v}$,
$g_{v}$ and $\Delta$.

##### The idea of the broadcast/gather labels and algorithms.

For the broadcast problem, we split the nodes of each layer $i$ into subsets
$X_{0},\ldots,X_{\Delta-1}$, where $X_{j}$ is a maximal set of nodes of layer
$i$ not belonging $\bigcup_{k<j}X_{k}$ such that the sets of neighbors of
$X_{j}$ at layer $i+1$ are pairwise disjoint, exluding the neighbors of nodes
from $\bigcup_{k<j}X_{k}$. For $v\in X_{j}$ we set $b_{v}=j$. We observe that
all nodes from $X_{j}$ can transmit in the same round in order to deliver the
broadcast message to all their neighbors at layer $i+1$, excluding the
neighbors of the nodes from $\bigcup_{k<j}X_{k}$. This fact makes possible to
deliver the broadcast message from layer $i$ to layer $i+1$ in $\Delta$
rounds. For each node $v$ at layer $i+1$, the first node which successfully
transmits the broadcast message to $v$ becomes $\textit{parent}(v)$ and $v$
becomes its child.

For the gathering problem, we assign distinct gather-labels in the range
$[0,\Delta-1]$ to the children of each node. This assignment is required to
satisfy also the following additional restriction. If $u$ at layer $i+1$ is a
neighbor of $v$ at layer $i$ and $u$ is not a child of $v$, then the gather-
label of $u$ is not assigned to any child of $v$. With this restriction, the
nodes at level $i$ with a given value of the gather-label can transmit
successfully messages to their parents in the same round. Thanks to this
property, the values/messages stored in the nodes from the layer $i>0$ can be
gathered in their parents at layer $i-1$ in $O(\Delta)$ rounds.

More details, formal statement of the above mentioned properties with their
proofs and the final broadcast and gathering algorithms are described below.

####  5.1.1 Assignment of broadcast-labels and gather-labels

##### Assignment of the values $b_{v}$ and construction of a BFS-tree

For each layer $i$, we assign the values $b_{v}$ as follows. First, we take
any maximal subset $X_{0}$ of $V_{i}$ such that the sets of neighbors at layer
$i+1$ of elements of this set are pairwise disjoint. All nodes from
$\mathcal{N}_{i+1}(v)$ will be called children of $v$, for each $v\in X_{0}$.
Then, we construct sets $X_{1},X_{2},\dots,X_{\Delta-1}$ as follows. Assume
that the sets $X_{0},\dots,X_{j-1}$ are already constructed for $j>0$. We
define $X_{j}$ as a maximal subset of nodes $v$ at layer $i$ such that

  1. (a)

$v\notin X_{0}\cup\dots\cup X_{j-1}$,

  2. (b)

for each pair of nodes $v\neq u$ such that $v,u\in X_{j}$, we have

$\mathcal{N}_{i+1}(v)\cap\mathcal{N}_{i+1}(u)\setminus\left(\bigcup_{k=0}^{j-1}\bigcup_{x\in
X_{k}}\mathcal{N}_{i+1}(x)\right)=\emptyset.$

If a node $v\in X_{j}$ has a neighbor $u$ in $V_{i+1}$, such that no node from
$X_{k}$ is in $\mathcal{N}_{i}(u)$ for all $k<j$, we say that $v$ is the
_parent_ of $u$ and $u$ is a _child_ of $v$. Observe that the set of edges
determined by this parent-child relationship will form a BFS tree of the
graph, denoted $T_{\text{BFS}}$.

Below, we show that all nodes at layer $i$ belong to $X_{0}\cup\cdots\cup
X_{\Delta}$.

######  Lemma 8.

For each layer $i$, the union of the sets $X_{0}\cup\cdots\cup X_{\Delta}$
from this layer is equal to the set of all nodes at layer $i$.

###### Proof.

Let us check the sizes of the sets
$Z_{j}(v)=\mathcal{N}_{i+1}(v)\setminus\left(\bigcup_{k=0}^{j-1}\bigcup_{x\in
X_{k}}\mathcal{N}_{i+1}(x)\right)$ for each value of $j\in[0,\Delta]$. For
$j=0$ the size of $Z_{j}(v)$ is at most $\Delta$. For other values of $j$ we
have

  * •

Case 1: $v\in X_{k}$ for some $k<j$: then $Z_{j}(v)$ is empty.

  * •

Case 2: $v\notin X_{k}$ for all $k<j$.

From the maximality of $X_{j-1}$ we know that there exists
$u\in\mathcal{N}_{i+1}(v)$ which is also in $\mathcal{N}_{i+1}(v^{\prime})$
for some $v^{\prime}\in X_{j-1}$ and not in neighborhoods of any node from
$X_{0},\dots,X_{j-2}$. This fact implies that $|Z_{j}(v)|\leq|Z_{j-1}(v)|+1$
for each $0\leq j\leq k$.

The above properties imply that, for each node $v\not\in X_{0}\cup\cdots\cup
X_{j-1}$ at layer $i$, the size of $Z_{j}(v)$ is at most $\Delta-j$. This in
turn implies that $Z_{\Delta}(v)$ must be empty for each $v\not\in
X_{0}\cup\cdots\cup X_{\Delta-1}$. So each node $v$ at layer $i$ is in some
set $X_{0},X_{1},\dots,X_{\Delta}$. ∎

We set $b_{v}\leftarrow k$ for each node $v\in X_{k}$, where the sets
$X_{0},\ldots,X_{\Delta}$ are as above.

For the acknowledged broadcast, we choose some arbitrary leaf node with the
highest value of $\textit{layer}(v)$ and a path $P$ of length
$\textit{layer}(v)$, such that $P$ starts at $r$ and ends at $v$ in the tree
$T_{\text{BFS}}$ obtained through parent-child relationships described above.
The value of $a_{u}$ is set to $1$ for each node $u$ on the path $P$ while the
value $a_{w}$ is set to $0$ for each node $w$ outside of $P$.

##### Assignment of the values $g_{v}$.

As mentioned before, the bit $g_{v}$ of each node $v$ will be used in our
gathering algorithm. The value $g_{r}$ of the root node $r$ is equal to $0$.
Then we assign values $g_{v}$ layer by layer, assigning the values to nodes at
layer $i$ in phase $i$. In the $i$th phase, we order nodes at layer $i-1$
according to the ordering determined by the values of $b_{v}$, from the
smallest to the largest and, among nodes with the same value of $b_{v}$,
according to the ordering $\prec$. Let $v_{j}$ be the $j$th node at layer
$i-1$ in this order. We give the value $g_{u}$ to each child $u$ of $v_{j}$ in
the BFS-tree $T_{\text{BFS}}$, as follows. For a node $v$ at layer $i-1$, we
order its children at layer $i$ (i.e., its neighbors at layer $i$ which have
not been assigned gather-labels yet) according to $\prec$, and assign to each
of them the smallest non-negative integer not assigned earlier to any neighbor
of $v$ at layer $i$.

Below, we state some properties of gather-labels which will be relevant fo the
gathering algorithm presented in Section 5.1.2.

######  Lemma 9.

The integers $g_{v}$ have the following properties:

  1. (a)

$g_{v}\in[0,\Delta-1]$,

  2. (b)

$g_{v}\neq g_{u}$ for each $u\neq v$ such that
$\textit{parent}(u)=\textit{parent}(v)$,

  3. (c)

if $\textit{parent}(v)\neq\textit{parent}(u)$ and $g_{u}=g_{v}$ for some
$u\neq v$ at the same layer, then $u$ and $\textit{parent}(v)$ are not
connected by an edge.

###### Proof.

As each node at layer $i>0$ has a neighbor at layer $i-1$, each node will be
assigned a gather-label.

(a, b): The values of gather-labels belong to the range $[0,\Delta-1]$ because
of the upper bound $\Delta$ on the degrees of nodes and the rule that, for a
child of a node $v$, we choose the smallest non-negative integer not assigned
earlier to any other neighbor of $v$ at layer $i$. Property (b) follows from
the assigning rules.

(c): First, assume that the assignment of gather-labels to the children of
$\textit{parent}(v)$ is done before the assignment of gather-labels to the
children of $\textit{parent}(u)$. In this case, if $(u,\textit{parent}(v))\in
E$ then $u$ is a child of $\textit{parent}(v)$ which contradicts the
assumption $\textit{parent}(v)\neq\textit{parent}(u)$. Now, assume that the
assignment of gather-labels to the children of $\textit{parent}(u)$ is done
before the assignment of gather-labels to the children of
$\textit{parent}(v)$. In this case, if $(u,\textit{parent}(v))\in E$ then none
of the children of $\textit{parent}(v)$, including $v$, is assigned the
gather-label $g_{u}$ which contradicts the assumption $g_{u}=g_{v}$. ∎

Since the label $\mathcal{L}(v)$ of any node is a concatenation of three bits
and three representations of integers at most $\Delta$, our labeling scheme
has length $O(\log\Delta)$.

####  5.1.2 Broadcast and Gathering Algorithms

##### Broadcast algorithm.

Our broadcast algorithm BroadcastBFS works in phases. Let $D^{*}$ be the depth
of the tree $T_{\text{BFS}}$. Note that $D^{*}$ is $\Theta(D)$, where $D$ is
the diameter of the graph. In phase $i\in\\{0,...,D^{*}-1\\},$ we want to
deliver the message $M$ from layer $i$ to layer $i+1$ of $T_{\text{BFS}}$.
Each phase consists of $\Delta+1$ rounds, which gives $D^{*}(\Delta+1)$ rounds
in total. A node $v$ transmits only in round
$\textit{layer}(v)\cdot\Delta+b_{v}+1$. In the first round of the broadcast
algorithm only the root, i.e., the node with $r_{v}=1$ transmits. Every other
node $v$ registers the round number in which it receives a message for the
first time. From that information, it can deduce the value of
$\textit{layer}(v)$ and, as it knows the value of $\Delta$ from its label, it
is able to determine the round of its own transmission of the broadcast
message (which is equal to the $b_{v}$th round of the next phase).

##### Acknowledged broadcast.

For the acknowledged version AckBrBFS of broadcast, we first execute the above
broadcast algorithm BroadcastBFS. However, instead of sending just the
broadcast message $M$, each node $v$ transmits the pair $(0,M)$. When the
chosen node $v$ with $\textit{leaf}(v)=1$ and $a_{v}=1$ receives the message
$(0,M)$, it can determine the maximum layer $D^{*}$ in the tree
$T_{\text{BFS}}$ (based on the round number of reception of the message).
After the last round of broadcast, which is the round $D^{*}(\Delta+1)$, $v$
transmits the pair $(1,D^{*})$. Whenever a node $u$ with $a_{u}=1$ receives
the message $(1,D^{*})$, it transmits the same message in the next round. When
$(1,D^{*})$ reaches the root $r$, node $r$ starts the next execution of
BroadcastBFS with the broadcast message equal to $D^{*}+2D^{*}(\Delta+1)$,
i.e., the number of rounds of the whole execution of AckBrBFS.

##### Gathering algorithm.

The gathering algorithm GatherBFS starts by an execution of the acknowledged
broadcast algorithm AckBrBFS followed by another execution of the broadcast
algorithm BroadcastBFS with the broadcast message $M$ equal to the value of
$D^{*}$, which is known to the source node at the beginning of this execution.
After that, we can assume that each node $v$ knows $\textit{layer}(v)$ and
$D^{*}$. The main part of the gathering algorithm GatherBFS also consists of
$D^{*}$ phases $i=0,...D^{*}-1$, each phase lasting $\Delta$ rounds. If a node
is at layer $i$, it listens in phase $D^{*}-i-1$ and stores all messages
received in this phase in its local memory. A node $v$ at layer $D^{*}-i$
transmits in round $g_{v}$ of the $i$th phase. The message transmitted by $v$
contains its original message $M_{v}$ and all messages that $v$ received until
the round of its transmission. All the phases end in $D^{*}\Delta$ rounds and,
by Lemma 9, each node receives the messages transmitted by all its children.
In particular, the root receives messages of all nodes of the tree.

The description of the labeling scheme and the properties of the above
algorithms imply the following lemma.

######  Lemma 10.

The algorithms BroadcastBFS, AckBrBFS and GatherBFS solve the broadcast
problem, the acknowledged broadcast problem and the gathering problem,
respectively, using a labeling scheme of length $O(\log\Delta)$, and work in
time $O(D\Delta)$.

###  5.2 Topology recognition algorithm

In order to solve the topology recognition problem, we choose an arbitrary
node as the root $r$ and assign to each node $v$ the label which is the
concatenation of two binary strings: the label $\mathcal{L}(v)$ used by our
broadcast-gathering primitive and the binary representation of a natural
number $\mathcal{C}(v)$ called the _color_ of $v$ which is the color of $v$ in
some fixed distance-two vertex coloring of the graph $G$ with the set of
colors equal to $[1,\Delta^{2}]$. Given these labels, we execute the following
four-stage algorithm TopRec:

Stage 1. First, the acknowledged broadcast AckBrBFS is executed with the
modification that each node $v$ transmits the concatenation of the consecutive
substrings $g_{u}$ of the labels of nodes of the path from the root $r$ to
$v$, including $g_{v}$. This concatenation will be denoted by ID($v$).

Stage 2. Then, in the block of $\Delta^{2}$ rounds, each node $v$ such that
$\mathcal{C}(v)=i\in[1,\Delta^{2}]$ transmits in the round $i$ of the block,
sending the string ID($v$), and each node stores received messages in its
local memory.

Remark. If $\Delta^{2}>n$ then $\log\Delta\geq\frac{1}{2}\log n$. In this
case, in order to reduce the number of rounds of Stage 2 to
$\min(\Delta^{2},n)$, we extend the labeling by assigning to each node a
unique identifier in the range $[1,n]$ of length $O(\log n)=$ $O(\log\Delta)$.
Then, Stage 2 consists of $n$ rounds, where the node with the identifier $i$
transmits in round $i$ of the stage.

Stage 3. Next, we execute the gathering algorithm GatherBFS, where the message
$M_{v}$ of a node $v$ is equal to the set of IDs received by $v$ in Stage 2,
together with its own ID. The set of these messages, over all nodes $v$,
permits each node to reconstruct the topology of the graph and situate itself
in it.

Stage 4. Finally, we execute the broadcast algorithm BroadcastBFS, where the
message $M$ is equal to the set of messages of all nodes gathered at the root
$r$ in Stage 3.

######  Theorem 8.

The algorithm TopRec solves the topology recognition problem on every graph,
using a labeling scheme of length $O(\log\Delta)$. It works in time
$O(D\Delta+\min(n,\Delta^{2}))$.

###### Proof.

As shown in Lemma 10, Stages 1, 3 and 4 work in $O(D\Delta)$ rounds. Moreover,
as the children of each node in $T_{\text{BFS}}$ have different gather-labels,
the IDs assigned to nodes in Stage 1 are unique. In Stage 2, lasting
$\min(\Delta^{2},n)$ rounds, each node $v$ receives a message from each of its
neighbors in the graph $G$ and it learns the distinct IDs of these neighbors.
Hence the message $M_{v}$ that each node $v$ sends in Stage 3 contains the
information about the neighborhood of $v$ with distinct ID’s.Thus, in Stage 3,
the root gathers information about all edges in $G$ and it broadcasts this
information to all nodes in Stage 4. ∎

##  6 Conclusion

We constructed labeling schemes of asymptotically optimal length for size
discovery and topology recognition in arbitrary radio networks without
collision detection. We also designed algorithms to solve these problems using
these optimal schemes. Our results show that, for arbitrary radio networks,
the optimal length of labeling schemes permitting topology recognition is
exponentially larger than that permitting the easier problem of size
discovery.

In the case of size discovery, we showed that our algorithm using the labeling
scheme of optimal length $O(\log\log\Delta)$ has also asymptotically optimal
time among size discovery algorithms using optimal schemes for this problem.
However, for topology recognition, our algorithm using the labeling scheme of
optimal length $O(\log\Delta)$ works in time
$O\left(D\Delta+\min(\Delta^{2},n)\right)$ and we do not know how far this
time is from optimal. Hence the main open problem left by our research is the
following: What is the time of the fastest topology recognition algorithm
using a labeling scheme of optimal length $O(\log\Delta)$?

## References

  * [1] N. Alon, A. Bar-Noy, N. Linial, D. Peleg,  A lower bound for radio broadcast,  J. Comput. Syst. Sci. 43 (1991), 290–298, 1991.
  * [2] S. Alstrup, H. Kaplan, M.Thorup, U. Zwick, Adjacency labeling schemes and induced-universal graphs, SIAM Journal on Discrete Mathematics 33 (2019), 116137.
  * [3] R. Bar-Yehuda, O. Goldreich, and A. Itai,  On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization,  J. Comput. Syst. Sci., 45 (1992), 104–126.
  * [4] G. Bu, Z. Lotker, M. Potop-Butucaru, M. Rabie,  Lower and upper bounds for deterministic convergecast with labeling schemes,  Manuscript, HAL Id: hal-02650472, 2020.
  * [5] M. Chrobak, L. Gasieniec, W. Rytter, Fast broadcasting and gossiping in radio networks, Journal of Algorithms 43 (2002):177-189.
  * [6] A. Czumaj, P. Davies, Exploiting spontaneous transmissions for broadcasting and leader election in radio networks, Proc. 36th ACM Symposium on Principles of Distributed Computing (PODC 2017), 3-12.
  * [7] A. Czumaj, P. Davies, Deterministic communication in radio networks, SIAM J. of Computing 47 (2017), 218-240.
  * [8] F. Ellen and S. Gilbert,  Constant-length labelling schemes for faster deterministic radio broadcast,  Proc. 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020), 213–222.
  * [9] F. Ellen, B. Gorain, A. Miller, A. Pelc,  Constant-length labeling schemes for deterministic radio broadcast,  Proc. 31st Symposium on Parallelism in Algorithms and Architectures, (SPAA 2019), 171–178.
  * [10] Y. Emek, P. Fraigniaud, A. Korman, A. Rosen, Online computation with advice, Theoretical Computer Science 412 (2011), 2642–2656.
  * [11] P. Fraigniaud, A. Korman, E. Lebhar, Local MST computation with short advice, Theory Comput. Syst. 47 (2010), 920-933.
  * [12] P. Fraigniaud, D. Ilcinkas, A. Pelc, Communication algorithms with advice, J. Comput. Syst. Sci. 76 (2010), 222–232.
  * [13] E. Fusco, A. Pelc, R. Petreschi, Topology recognition with advice, Information and Computation 247 (2016), 254-265.
  * [14] L. Gasieniec, A. Pagourtzis, I. Potapov, T. Radzik, Deterministic communication in radio networks with large labels. Algorithmica 47 (2007), 97-117.
  * [15] L. Gasieniec, D. Peleg, Q. Xin, Faster communication in known topology radio networks, Distributed Computing 19 (2007), 289-300.
  * [16] M. Ghaffari, B. Haeupler, M. Khabbazian, Randomized broadcast in radio networks with collision detection, Proc. 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC 2013), 325 - 334.
  * [17] C. Glacet, A. Miller, A. Pelc, Time vs. information tradeoffs for leader election in anonymous trees, ACM Transactions on Algorithms 13 (2017), 31:1-31:41.
  * [18] B. Gorain, A. Pelc,  Short labeling schemes for topology recognition in wireless tree networks,  Proc. 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2017), 37–52.
  * [19] B. Gorain, A. Pelc,  Finding the size of a radio network with short labels,  Proc. 19th International Conference on Distributed Computing and Networking, (ICDCN 2018), 10:1–10:10.
  * [20] D. Ilcinkas, D. Kowalski, A. Pelc, Fast radio broadcasting with advice, Theoretical Computer Science, 411 (2012), 1544–1557.
  * [21] D. Kowalski, A. Pelc, Leader election in ad hoc radio networks: a keen ear helps, J. Comput. Syst. Sci. 79 (2013), 1164-1180.
  * [22] D. Kowalski, A. Pelc, Optimal deterministic broadcasting in known topology radio networks, Distributed Computing 19 (2007), 185-195.
  * [23] P. Montealegre, S. Perez-Salazar, I. Rapaport, I. Todinca, Graph reconstruction in the congested clique, J. Comput. Syst. Sci. 113, (2020) 1-17.