• Calendar

June 20, Tuesday
12:00 – 14:00

We study the problem of the amount of information about a network that must be known in order to efficiently accomplish an exploration or communication task. While previous results about exploration and communication in networks assumed particular partial information, such as the knowledge of the neighborhood, the knowledge of the network topology within some radius, or a partial map of the network, our approach is quantitative: we investigate the minimum total number of bits of information (minimum oracle size) that has to be known in order to perform efficient exploration or communication.

We present the approach by oracles on the examples of two problems. The first is exploration, a fundamental problem in mobile computing: a mobile agent has to traverse all edges of a network. The second is information dissemination, one of the basic communication primitives: a message held in one node of the network, called the source, has to be transmitted to all other nodes. If no restrictions are imposed, information dissemination is called broadcast. If only nodes that already got the source message can transmit, it is called wakeup.

For the exploration task we establish the minimum oracle size permitting exploration with competitive ratio below 2. For communication we show that the minimum oracle size to perform wakeup with a linear number of messages in an $n$-node network, is $\Theta (n \log n)$, while the broadcast with a linear number of messages can be achieved with an oracle of size $O(n)$. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast.

This is joint work with Pierre Fraigniaud and David Ilcinkas