On Bootstrapping Topology Knowledge in Anonymous Networks

In this paper, we quantify the amount of “practical” information (

i.e.

views obtained from the neighbors, colors attributed to the nodes and links) to obtain “theoretical” information (

i.e.

the local topology of the network up to distance

k

) in anonymous networks. In more details, we show that a coloring at distance 2

k

+ 1 is necessary and sufficient to obtain the local topology at distance

k

that includes outgoing links. This bound drops to 2

k

when outgoing links are not needed. A second contribution of this paper deals with color bootstrapping (from which local topology can be obtained using the aforementioned mechanisms). On the negative side, we show that

(i)

with a distributed daemon, it is impossible to achieve deterministic color bootstrap, even if the whole network topology can be instantaneously obtained, and

(ii)

with a central daemon, it is impossible to achieve distance

m

when instantaneous topology knowledge is limited to

m

− 1. On the positive side, we show that

(i)

under the

k

-central daemon, deterministic self-stabilizing bootstrap of colors up to distance

k

is possible provided that

k

-local topology can be instantaneously obtained, and

(ii)

under the distributed daemon, probabilistic self-stabilizing bootstrap is possible for any range.