  We investigate a special case of hereditary property that we refer to as {\em
robustness}. A property is {\em robust} in a given graph if it is inherited by
all connected spanning subgraphs of this graph. We motivate this definition in
different contexts, showing that it plays a central role in highly dynamic
networks, although the problem is defined in terms of classical (static) graph
theory. In this paper, we focus on the robustness of {\em maximal independent
sets} (MIS). Following the above definition, a MIS is said to be {\em robust}
(RMIS) if it remains a valid MIS in all connected spanning subgraphs of the
original graph. We characterize the class of graphs in which {\em all} possible
MISs are robust. We show that, in these particular graphs, the problem of
finding a robust MIS is {\em local}; that is, we present an RMIS algorithm
using only a sublogarithmic number of rounds (in the number of nodes $n$) in
the ${\cal LOCAL}$ model. On the negative side, we show that, in general
graphs, the problem is not local. Precisely, we prove a $\Omega(n)$ lower bound
on the number of rounds required for the nodes to decide consistently in some
graphs. This result implies a separation between the RMIS problem and the MIS
problem in general graphs. It also implies that any strategy in this case is
asymptotically (in order) as bad as collecting all the network information at
one node and solving the problem in a centralized manner. Motivated by this
observation, we present a centralized algorithm that computes a robust MIS in a
given graph, if one exists, and rejects otherwise. Significantly, this
algorithm requires only a polynomial amount of local computation time, despite
the fact that exponentially many MISs and exponentially many connected spanning
subgraphs may exist.
