Advertised configurations

Our heuristics are different versions of greedy algorithms: a host $h$ repeatedly selects other hosts to include in Core$(h)$ until some condition is met. Hence we chose a representation that makes it easier for a greedy algorithm to find good candidates to include in Core$(h)$. This representation is a three-level hierarchy.

The top level of the hierarchy is the operating system that a host runs, the second level includes the applications that run on that operating system, and the third level are hosts. Each host runs one operating system, and so each host is subordinate to its operating system in the hierarchy (we can represent hosts running multiple virtual machines as multiple virtual hosts in a straightforward manner). Since most applications run predominately on one platform, hosts that run a different operating system than $h$ are likely good candidates for including in Core$(h)$. We call the first level the containers and the second level the sub-containers. Each sub-container contains a set of hosts. Figure 3 illustrates these abstractions using the configurations of Example 3.1.

More formally, let $\cal O$ be the set of canonical operating system names and $\cal C$ be the set of containers. Each host $h$ has an attribute $h.os$ that is the canonical name of the operating system on $h$. The function $m_c: {\cal O} \rightarrow {\cal C}$ maps operating system name to container; thus, $m_c(h.os)$ is the container that contains $h$.

Figure 3: Illustration of containers and sub-containers.

Let $h.apps$ denote the set of canonical names of the applications that are running on $h$, and let $\cal A$ be the canonical names of all of the applications. We denote with ${\cal S}$ the set of sub-containers and with $m_s: \mathcal{C} \rightarrow 2^{\cal S}$ the function that maps a container to its sub-containers. The function $m_h: {\cal C} \times {\cal A} \rightarrow {\cal S}$ maps a container and application to a sub-container; thus, for each $a \in h.apps$, host $h$ is in each sub-container $m_h(m_c(h.os), a)$.

At this high level of abstraction, advertising a configuration is straightforward. Initially $\mathcal{C}$ is empty. To advertise its configuration, a host $h$ first ensures that there is a container $c \in {\cal C}$ such that $m_c(h.os) = c$. Then, for each attribute $a \in h.apps$, $h$ ensures that there is a sub-container $m_h(c, a)$ containing $h$.