Surviving catastrophes

With informed replication, each host $h$ constructs a core Core$(h)$ based on its configuration and the configuration of other hosts.¹Unfortunately, computing a core of optimal size is NP-hard, as we have shown with a reduction from SET-COVER [13]. Hence, we use heuristics to compute Core$(h)$. In this section, we first discuss a structure for representing advertised configurations that is amenable to heuristics for computing cores. We then describe four heuristics and evaluate via simulation the properties of the cores that they construct. As a basis for our simulations, we use the set of hosts $\mathcal{H}$ obtained from the traces discussed in Section 4.