Name
Abstract | ||
|---|---|---|
A salvage-embedding (S-embedding) maps an $M$-leaf complete binary tree $\cal G$ into an $(N M)$-leaf complete binary tree $\cal H$, the fraction $G$ of whose leaves have been labeled {\sc good}. The S-embedding maps leaves of $\cal G$ one-to-one to {\sc good} leaves of $\cal H$; it may be many-to-one on internal nodes. The quality of an S-embedding depends on its harvest, the ratio $H \eqdef M/GN$, and its congestion, the largest number of edges of $\cal G$ that get "routed" across the same edge of $\cal H$. We study three scenarios. In the worst-case scenario, given any target harvest $H \leq 1/2$, one can S-embed a $2^{\lfloor \log (HGN) \rfloor}$-leaf $\cal G$ in $\cal H$ with congestion $\log \log N +$ a constant depending only on $G$ and $H$, no matter how the {\sc good} leaves are distributed; this congestion cannot be lowered by more than a small constant factor. In the expected-case scenario---where leaves of $\cal H$ are labeled {\sc 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 $\cal G$ in $\cal 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 $\cal H$ the largest possible $\cal 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. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1137/S089548019224127X | SIAM J. Discrete Math. |
Keywords | Field | DocType |
complete trees,cal g,n m,leaf complete binary tree,cal h,worst-case scenario,tree architecture,salvaging scenario,target harvest,m-leaf complete binary tree,s-embedding map,expected-case scenario,dilation,fault tolerance,binary tree,synchronization networks | Tree architecture,Discrete mathematics,Binary logarithm,Combinatorics,Parallel processing,Binary tree,Omega,Mathematics | Journal |
Volume | Issue | ISSN |
8 | 4 | 0895-4801 |
Citations | PageRank | References |
1 | 0.36 | 3 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sandeep N. Bhatt | 1 | 448 | 51.33 |
| Fan R. K. Chung | 2 | 259 | 41.54 |
| Frank Thomson Leighton | 3 | 2365 | 493.65 |
| Arnold L. Rosenberg | 4 | 2107 | 640.21 |