On the complexity of distributed BFS in ad hoc networks with spontaneous wake-up
Krzysztof Krzywdziński, Dariusz Kowalski
Abstract
We study time and message complexity of the problem of building a BFS tree
by a spontaneously awaken node in ad hoc network.
Computation is in synchronous rounds, and messages are sent
via point-to-point bi-directional links.
Network topology is modeled by an undirected graph.
Each node knows only its own id and the id's of its neighbors in the network
and no pre-processing is allowed;
therefore the solutions to the problem of spanning a BFS tree
in this setting must be distributed.
We deliver a deterministic distributed solution that trades time for messages, mainly,
with time complexity $O(\diam\cdot\min(\diam,n/f(n)) \cdot \log \diam \cdot \log n)$ and
with the number of point-to-point messages sent
$O(n\cdot(\min(\diam,n/f(n)) + f(n)) \cdot \log \diam \cdot \log n)$,
for any $n$-node network with diameter $\diam$ and
for any monotonically non-decreasing sub-linear integer function $f$.
Function $f$ in the above formulas come from the threshold value on node
degrees used by our algorithms, in the sense that nodes with degree at
most $f(n)$ are treated differently that the other nodes.
This yields the first BFS-finding deterministic distributed algorithm in ad hoc networks working
in time $o(n)$ and with $o(n^2)$ message complexity, for some suitable functions
$f(n)=o(n/\log^2 n)$, provided $\diam=o(n/\log^4 n)$.
Full Text: PDF PostScript