Dominik Pajak: Broadcast in stochastically varying networks

In this talk, we will study a problem of broadcast in radio networks,
where the graph of connections between the stations can vary in time.
The connections are divided into two sets: a set of reliable edges,
that are always present, and unreliable edges whose presence in the
graph in a given step is controlled by an adversary. The adversary is
parametrized by \tau and restricted in the following way. It defines a
distribution over the unreliable edges and in each step, a sample taken
from this distribution becomes active. The adversary is allowed to
change the distribution once every at least \tau steps. Our goal is to
study how parameter \tau influences the optimal time of two classical
problems: local broadcast (a single station needs to receive a message
from one of its neighbors) and global broadcast (a message from a
single source has to be delivered to all the stations).