  We address the problem of computing a Minimal Dominating Set in highly
dynamic distributed systems. We assume weak connectivity, i.e., the network may
be disconnected at each time instant and topological changes are unpredictable.
We make only weak assumptions on the communication: every process is infinitely
often able to communicate with other processes (not necessarily directly). Our
contribution is threefold. First, we propose a new definition of minimal
dominating set suitable for the context of time-varying graphs that seems more
relevant than existing ones. Next, we provide a necessary and sufficient
topological condition for the existence of a deterministic algorithm for
minimal dominating set construction in our settings. Finally, we propose a new
measure of time complexity in time-varying graph in order to to allow fair
comparison between algorithms. Indeed, this measure takes account of
communication delays attributable to dynamicity of the graph and not to the
algorithms.
