Fast fault-tolerant parallel communication and on-line maintenance for hypercubes using information dispersal

A space-efficient Information Dispersal Algorithm (IDA) is applied to fault-tolerant parallel communication in the hypercube. LetN denote the size of the network. Our routing scheme runs in 2·logN+1 time using constant size buffers (if the routing information is not counted). Its probability of successful routing is at least 1–N ^{–2.419·logN+1.5}, proving Rabin's conjecture. The scheme runswithin the said time bound without queueing delay, and it toleratesO(N) random link failures with high probability.Optimal on-line and efficient wire maintenance on the hypercube can be realized if our fault-tolerant routing scheme is used. Let denote the total number of links in the hypercube. It is shown that a constant fraction (/352) of the wires can be disabled simultaneously without disrupting the ongoing computation or degrading the routing performance much. This property suggests various on-line maintenance procedures.This research was supported by NSF Grant MCS-8121431 at Harvard University. This paper is based on Chapters 4, 5, and 8 of the author's Ph.D. dissertation.     

Planar-optical mesh-connected tree interconnects: a feasibility study

The mesh-connected tree is a two-dimensional interconnect topology that combines aspects of a conventional tree network and a two-dimensional nearest-neighbor mesh network. Because of its topological features, a mesh-connected tree has the potential to be implemented with planar optoelectronic interconnect concepts. We examine the feasibility of employing vertical-to-surface-transmissionelectro-photonic optical array switches together with planar micro-optical components for the future implementation of an optoelectronic mesh-connected tree interconnect.     

Spreading of Messages in Random Graphs

Consider the following model on the spreading of messages. A message initially convinces a set of vertices, called the seeds, of the Erdős-Rényi random graph G(n,p). Whenever more than a ρ∈(0,1) fraction of a vertex v’s neighbors are convinced of the message, v will be convinced. The spreading proceeds asynchronously until no more vertices can be convinced. This paper derives lower bounds on the minimum number of initial seeds, min-seed(n,p,d,r)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho), needed to convince a δ∈{1/n,…,n/n} fraction of vertices at the end. In particular, we show that (1) there is a constant β>0 such that min-seed(n,p,d,r)=W(min{d,r}n)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho)=\Omega(\min\{\delta,\rho\}n) with probability 1−n ^−Ω(1) for p≥β (ln (e/min {δ,ρ}))/(ρ n) and (2) min-seed(n,p,d,1/2)=W(dn/ln(e/d))\mathrm{min\hbox{-}seed}(n,p,\delta,1/2)=\Omega(\delta n/\ln(e/\delta)) with probability 1−exp (−Ω(δ n))−n ^−Ω(1) for all p∈[ 0,1 ]. The hidden constants in the Ω notations are independent of p.     

On the construction and complexity of the bivariate lattice with stochastic interest rate models

Complex financial instruments with multiple state variables often have no analytical formulas and therefore must be priced by numerical methods, like lattice ones. For pricing convertible bonds and many other interest rate-sensitive products, research has focused on bivariate lattices for models with two state variables: stock price and interest rate. This paper shows that, unfortunately, when the interest rate component allows rates to grow in magnitude without bounds, those lattices generate invalid transition probabilities. As the overwhelming majority of stochastic interest rate models share this property, a solution to the problem becomes important. This paper presents the first bivariate lattice that guarantees valid probabilities. The proposed bivariate lattice grows (super)polynomially in size if the interest rate model allows rates to grow (super)polynomially. Furthermore, we show that any valid constant-degree bivariate lattice must grow superpolynomially in size with log-normal interest rate models, which form a very popular class of interest rate models. Therefore, our bivariate lattice can be said to be optimal.     

A Valid and Efficient Trinomial Tree for General Local-Volatility Models

Computational Economics - The local-volatility model assumes the instantaneous volatility is a deterministic function of the underlying asset price and time. The model is very popular because it...     

An exact subexponential-time lattice algorithm for Asian options

Asian options are popular financial derivative securities. Unfortunately, no exact pricing formulas exist for their price under continuous-time models. Asian options can also be priced on the lattice, which is a discretized version of the continuous- time model. But only exponential-time algorithms exist if the options are priced on the lattice without approximations. Although efficient approximation methods are available, they lack accuracy guarantees in general. This paper proposes a novel lattice structure for pricing Asian options. The resulting pricing algorithm is exact (i.e., without approximations), converges to the value under the continuous-time model, and runs in subexponential time. This is the first exact, convergent lattice algorithm to break the long-standing exponential-time barrier. An early version of this paper appeared in the Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2004. T.-S. Dai was supported in part by NSC grant 94-2213-E-033-024. Y.-D. Lyuu was supported in part by NSC grant 94-2213-E-002-088.