Deterministic broadcasting in unknown radio networks
Andrzej Pelc, University of Quebec at Hull, Canada. 

We consider the problem of distributed deterministic broadcasting 
in radio networks of unknown topology and size. 
The network is synchronous. If a node $u$ can be reached from two 
nodes which send messages in the same round, none of the messages 
is received by $u$.
We assume that nodes are completely ignorant of the network: 
they know neither its topology, nor size, nor even their immediate
neighborhood. The initial knowledge of every node is limited to its 
own label. We study the time of deterministic broadcasting under 
this total ignorance scenario.

Previous research has concentrated on distributed randomized 
broadcasting algorithms working for unknown networks, and on 
deterministic off-line broadcasting algorithms assuming full knowledge 
of the radio network. Ours are the first broadcasting algorithms 
simultaneously distributed and deterministic, that work for arbitrary 
totally unknown radio networks.

This is joint work by B.S. Chlebus, L. Gasieniec, A. Gibbons, A. Pelc
and W. Rytter.