With informed replication, each host constructs a core Core
based on its configuration and the configuration of other
hosts.1Unfortunately, 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
. 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
obtained from the
traces discussed in Section 4.