Salvage-Embeddings of Complete Trees
Sandeep N. Bhatt, Fan Chung, Frank Thomson Leighton, Arnold L. Rosenberg · SIAM Journal on Discrete Mathematics · 1995
A salvage-embedding (S-embedding) maps an M-leaf complete binary tree into $\mathcal{G}$ an ($N > M$)-leaf complete binary tree $\mathcal{H}$, the fraction G of whose leaves have been labeled GOOD. The S-embedding maps leaves of $\mathcal{G}$ one-to-one to GOOD leaves of $\mathcal{H}$; it may be many-to-one on internal nodes. The quality of an S-embedding depends on its harvest, the ratio $H\mathop = \limits^{def} M/GN$, and its congestion, the largest number of edges $\mathcal{G}$ that get “routed” across the same edge of $\mathcal{H}$. We study three scenarios. In the worst-case scenario, given any target harvest $H \leq \frac{1}{2}$, one can S-embed a $2^{\lfloor {\log ( HGN )} \rfloor }$-leaf $\mathcal{G}$ in $\mathcal{H}$ with congestion $\log \log N + $ a constant depending only on G and H, no matter how the GOOD leaves are distributed; this congestion cannot be lowered by more than a small constant factor. In the expected-case scenario—where leaves of $\mathcal{H}$ are labeled GOOD or not, independently, with fixed probability—with probability exceeding $1 - N^{ - \Omega ( 1 )} $, for any target harvest $H \leq 1/8$, one can S-embed a $2^{\lfloor {HN} \rfloor } $-leaf $\mathcal{G}$ in $\mathcal{H}$ with congestion $O( \log \log \log N )$. In the salvaging scenario, we present an algorithm that, in time $O( CN ( \log N )^{3C + 2} )$, S-embeds in a given a leaf-labeled $\mathcal{H}$ the largest possible $\mathcal{G}$, subject to the prespecified bound C on congestion. This work is inspired by the problem of salvaging a fault-free subnetwork of a leaf-tree machine—a tree architecture whose leaves hold “full-power” processors and whose nonleaf nodes hold “rudimentary” processors that route messages and perform simple combining tasks.