Use knowledge to learn faster: Topology recognition with advice

Topology recognition is one of the fundamental distributed tasks in networks. Each node of an anonymous network has to deterministically produce an isomorphic copy of the underlying graph, with all ports correctly marked. This task is usually unfeasible without any a priori information. Such information can be provided to nodes as advice. An oracle knowing the network can give a (possibly different) string of bits to each node, and all nodes must reconstruct the network using this advice, after a given number of rounds of communication. During each round each node can exchange arbitrary messages with all its neighbors and perform arbitrary local computations. The time of completing topology recognition is the number of rounds it takes, and the size of advice is the maximum length of a string given to nodes. We investigate tradeoffs between the time in which topology recognition is accomplished and the minimum size of advice that has to be given to nodes. We provide upper and lower bounds on the minimum size of advice that is sufficient to perform topology recognition in a given time, in the class of all graphs of size n and diameter D ≤ αn, for any constant α < 1. In most cases, our bounds are asymptotically tight. More precisely, if the allotted time is D - k , where 0 < k ≤ D , then the optimal size of advice is Θ((n2 log n)/(D - k +1)). If the allotted time is D, then this optimal size is Θ(n log n). If the allotted time is D + k , where 0 < k ≤ D/2, then the optimal size of advice is Θ(1 + (log n)/k). The only remaining gap between our bounds is for time D + k , where D/2 < k ≤ D . In this time interval our upper bound remains O(1+(log n)/k), while the lower bound (that holds for any time) is 1. This leaves a gap if D ε o(log n). Finally, we show that for time 2D +1, one bit of advice is both necessary and sufficient. Our results show how sensitive is the minimum size of advice to the time allowed for topology recognition: allowing just one round more, from D to D + 1, decreases exponentially the advice needed to accomplish this task. © Springer-Verlag 2013