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.     

Abductive logics in a belief revision framework

Abduction was first introduced in the epistemological context of scientific discovery. It was more recently analyzed in artificial intelligence, especially with respect to diagnosis analysis or ordinary reasoning. These two fields share a common view of abduction as a general process of hypotheses formation. More precisely, abduction is conceived as a kind of reverse explanation where a hypothesis H can be abduced from events E if H is a good explanation of E. The paper surveys four known schemes for abduction that can be used in both fields. Its first contribution is a taxonomy of these schemes according to a common semantic framework based on belief revision. Its second contribution is to produce, for each non-trivial scheme, a representation theorem linking its semantic framework to a set of postulates. Its third contribution is to present semantic and axiomatic arguments in favor of one of these schemes, ordered abduction, which has never been vindicated in the literature.     

Outlier Detection under Interval Uncertainty: Algorithmic Solvability and Computational Complexity

In many application areas,it is important to detect outliers. The traditional engineering approach to outlier detection is that we start with some normal values x₁, ...,x_n, compute the sample average E, the sample standard variation , and then mark a value x as an outlier if x is outside the k₀-sigma interval [E – k₀ , E + k₀ ] (for some pre-selected parameter k₀).In real life,we often have only interval ranges [ ] for the normal values x₁, ...,x_n. In this case,we only have intervals of possible values for the bounds and . We can therefore identify outliers as values that are outside all k₀-sigma intervals.Once we identify a value as an outlier for a fixed k₀, it is also desirable to find out to what degree this value is an outlier, i.e., what is the largest value k₀ for which this value is an outlier.In this paper,we analyze the computational complexity of these outlier detection problems, provide efficient algorithms that solve some of these problems (under reasonable conditions), and list related open problems.     

Adaptive controllers and root loci of minimum-phase systems

We consider the class of multi-input, multi-output, finite-dimensional, minimum-phase systemsx=Ax+Bu,y=Cx, where it is required that det(CB) # 0, but the state dimension is unknown. For this class, a simple universal adaptive high-gain controller-not based on any identification mechanism-is introduced that ensures exponential decay to zero of the solution of the closed-loop system. Moreover, the terminal system is almost always exponentially stable. The switching-type controller switches between constant gains at discrete points of time and is based on the simple Willems-Byrnes controlleru(t)=–k(t)y(t), k(t) ². The results are extended to solve the adaptive tracking problem for a certain class of reference signals.     

Lower Bounds on the Approximation Ratios of Leading Heuristics for the Single-Machine Total Tardiness Problem

The weakly NP-hard single-machine total tardiness scheduling problem has been extensively studied in the last decades. Various heuristics have been proposed to efficiently solve in practice a problem for which a fully polynomial time approximation scheme exists (though with complexity O(n ⁷/)). In this note, we show that all known constructive heuristics for the problem, namely AU, MDD, PSK, WI, COVERT, NBR, present arbitrarily bad approximation ratios. The same behavior is shown by the decomposition heuristics DEC/EDD, DEC/MDD, DEC/PSK, and DEC/WI.     

Choosing reference classes and building provisional models

A well-known problem in default logic is the ability of naive reasoners to explain bothg and ¬g from a set of observations. This problem is treated in at least two different ways within that camp.One approach is examination of the various explanations and choosing among them on the basis of various explanation comparators. A typical comparator is choosing the explanation that depends on the most specific observation, similar to the notion of narrowest reference class.Others examine default extensions of the observations and choose whatever is true in any extension, or what is true in all extensions or what is true in preferred extensions. Default extensions are sometimes thought of as acceptable models of the world that are discarded as more knowledge becomes available.We argue that the notions of specificity and extension lack clear semantics. Furthermore, we show that the problems these ideas were supposed to solve can be handled easily within a probabilistic framework.     

Expressiveness of Full First-Order Constraints in the Algebra of Finite or Infinite Trees

We are interested in the expressiveness of constraints represented by general first order formulae, with equality as unique relation symbol and function symbols taken from an infinite set F. The chosen domain is the set of trees whose nodes, in possibly infinite number, are labelled by elements of F. The operation linked to each element f of F is the mapping (a ₁,..., a _n ) b, where b is the tree whose initial node is labelled f and whose sequence of daughters is a ₁,..., a _n .We first consider tree constraints involving long alternated sequences of quantifiers .... We show how to express winning positions of two-person games with such constraints and apply our results to two examples.We then construct a family of strongly expressive tree constraints, inspired by a constructive proof of a complexity result by Pawel Mielniczuk. This family involves the huge number (k), obtained by top down evaluating a power tower of 2's, of height k. By a tree constraint of size proportional to k, it is then possible to define a tree having exactly (k) nodes or to express the multiplication table computed by a Prolog machine executing up to (k) instructions.By replacing the Prolog machine with a Turing machine we show the quasi-universality of tree constraints, that is to say, the ability to concisely describe trees which the most powerful machine will never have time to compute. We also rediscover the following result of Sergei Vorobyov: the complexity of an algorithm, deciding whether a tree constraint without free variables is true, cannot be bounded above by a function obtained from finite composition of simple functions including exponentiation.Finally, taking advantage of the fact that we have at our disposal an algorithm for solving such constraints in all their generalities, we produce a set of benchmarks for separating feasible examples from purely speculative ones. Among others we notice that it is possible to solve a constraint of 5000 symbols involving 160 alternating quantifiers.     

Parallel algorithms for routing in nonblocking networks

We construct nonblocking networks that are efficient not only as regards their cost and delay, but also as regards the time and space required to control them. In this paper we present the first simultaneous weakly optimal solutions for the explicit construction of nonblocking networks, the design of algorithms and data-structures. Weakly optimal is in the sense that all measures of complexity (size and depth of the network, time for the algorithm, space for the data-structure, and number of processor-time product) are within one or more logarithmic factors of their smallest possible values. In fact, we construct a scheme in which networks withn inputs andn outputs have sizeO(n(logn)²) and depthO(logn), and we present deterministic and randomized on-line parallel algorithms to establish and abolish routes dynamically in these networks. In particular, the deterministic algorithm usesO((logn)⁵) steps to process any number of transactions in parallel (with one processor per transaction), maintaining a data structure that useO(n(logn)²) words.     

On the Numerical Solution of Some Semilinear Elliptic Problems – II

In the earlier paper [6], a Galerkin method was proposed and analyzed for the numerical solution of a Dirichlet problem for a semi-linear elliptic boundary value problem of the form –U=F(·,U). This was converted to a problem on a standard domain and then converted to an equivalent integral equation. Galerkins method was used to solve the integral equation, with the eigenfunctions of the Laplacian operator on the standard domain D as the basis functions. In this paper we consider the implementing of this scheme, and we illustrate it for some standard domains D.     

A Subdivision Scheme for Continuous-Scale B-Splines and Affine-Invariant Progressive Smoothing

Multiscale representations and progressive smoothing constitutean important topic in different fields as computer vision, CAGD,and image processing. In this work, a multiscale representationof planar shapes is first described. The approach is based oncomputing classical B-splines of increasing orders, andtherefore is automatically affine invariant. The resultingrepresentation satisfies basic scale-space properties at least ina qualitative form, and is simple to implement.The representation obtained in this way is discrete in scale,since classical B-splines are functions in , where k isan integer bigger or equal than two. We present a subdivisionscheme for the computation of B-splines of finite support atcontinuous scales. With this scheme, B-splines representationsin are obtained for any real r in [0, ), andthe multiscale representation is extended to continuous scale.The proposed progressive smoothing receives a discrete set ofpoints as initial shape, while the smoothed curves arerepresented by continuous (analytical) functions, allowing astraightforward computation of geometric characteristics of theshape.     

An operation-control scheme for authorization in computer systems

The access-control authorization scheme, which is being used for the protection of operating systems, is found to be inadequate in other areas, such as in databases and information systems. A new authorization scheme, which is a natural extension of access control, is proposed. The new scheme, which is called operation control, is shown to be superior to the accesscontrol scheme in a number of ways. In particular, it facilitates more natural and efficient representations of policies, particularly the type of complex policies that appear in information systems, it facilitates enforcement by compile-time validation due to a greater stability of authority states, and it reduces the need for revocation.This work was partially supported by Grant DAHCIS-73-G6 of the Advanced Research Project Agency of the US government. This paper is a modified version of the paper An Activator-based protection scheme, July 1976 (SOSAP-TR-25).     

Nonlinear multigrid methods for total variation image denoising

The classical image denoising technique introduced by Rudin, Osher, and Fatemi [17] a decade ago, leads to solve a constrained minimization problem for the total variation (TV) of the image. The formal first variation of the minimization problem is a nonlinear and highly anisotropic boundary value problem. In this paper, a computational PDE method based on a nonlinear multigrid scheme for restoring noisy images is suggested. Here, we examine different discretizations for the Euler–Lagrange equation as well as different smoothers within the multigrid scheme. Then we describe the iterative total variation regularization scheme, which starts with an isotropic (smooth) problem and leads to smooth edges in the image. Within the iteration the problem becomes more and more anisotropic and converges to an image with sharp edges. Finally, we present some experimental results for synthetic and real images.     

Sequentielle Analyse kontextfreier Sprachen

Summary Sequential analysis of context-free languages. Since 1965 several methods to solve the word problem for context-free languages in no more than cn ³steps have been published where c is a constant and n the length of the word [2, 5, 7]. The procedure to be described is a sequential procedure that means that the word which is to be analyzed has to be read monotonic from left to right and that the word problem is decided for each partial word. The method consists in constructing a growing automaton whose wiring (in a physical way of speaking) grows only quadratically. From a monotonicity of property of signal propagation in our automata we can conclude that the procedure can be implemented on a RAM (random access machine) in such a way that the word problem is decided in at most cn ³steps.     

Numerical stability of a quadratic method for solving systems of non linear equations

In this paper the numerical stability of a recent method to solve systems of nonlinear equations is studied. This method, based on the -algorithm, has a quadratic convergence without calculating any derivatives and under quite benevolent conditions. The numerical stability of this algorithm is studied using the theory of theA-stability for the propagation of round-off errors in the numerical integration of differential equations.

---

Numerische Stabilität einer quadratisch konvergenten Methode zur Lösung von Systemen nicht-linearer Gleichungen

Zusammenfassung In diesem Artikel wird die numerische Stabilität einer neuen Methode zur Lösung von Systemen nicht-linearer Gleichungen studiert. Diese Methode, sie basiert auf dem -Algorithmus, ist unter schwachen Voraussetzungen und ohne Verwendung von Ableitungen quadratisch konvergent. Die Stabilität dieses Algorithmus wird unter Verwendung der Theorie derA-Stabilität bezüglich der Fortpflanzung von Rundungsfehlern bei der numerischen Integration von Differentiagleichungen studiert.

     

Two and three-quarter dimensional meshing facilitators

This paper presents generated enhancements for robust two and three-quarter dimensional meshing, including: (1) automated interval assignment by integer programming for submapped surfaces and volumes, (2) surface submapping, and (3) volume submapping. An introduction to the simplex method, an optimization technique of integer programming, is presented. Simplification of complex geometry is required for the formulation of the integer programming problem. A method of i-j unfolding is defined which explains how irregular geometry can be realigned into a simplified form that is suitable for submap interval assignment solutions. Also presented is the processes by which submapping eliminates the decomposition of surface geometry, through a pseudodecomposition process, producing suitable mapped meshes. The process of submapping involves the creation of interpolated virtual edges, user defined vertex types and i-j-k space traversals. The creation of interpolated virtual edges is the method by which submapping automatically subdivides surface geometry. The interpolated virtual edge is formulated according to an interpolation scheme using the node discretization of curves on the surface. User defined vertex types allow direct user control of surface decomposition and interval assignment by modifying i-j-k space traversals. Volume submapping takes the geometry decomposition to a higher level by using mapped virtual surfaces to eliminate decomposition of complex volumes.     

Transformation of programs for fault-tolerance

In this paper we describe how a program constructed for afault-free system can be transformed into afault-tolerant program for execution on a system which is susceptible to failures. A program is described by a set of atomic actions which perform transformations from states to states. We assume that a fault environment is represented by a programF. Interference by the fault environmentF on the execution of a programP can then be described as afault-transformation which transformsP into a program (P). This is proved to be equivalent to the programPP _F , whereP _F is derived fromP andF, and defines the union of the sets of actions ofP andF _P . A recovery transformation transformsP into a program (P) =PR by adding a set ofrecovery actions R, called arecovery program. If the system isfailstop and faults do not affect recovery actions, we have ((P))=(P)R=PP _F R We illustrate this approach to fault-tolerant programming by considering the problem of designing a protocol that guarantees reliable communication from a sender to a receiver in spite of faults in the communication channel between them.     

A Numerical Modeling of Rayleigh–Marangoni Steady Convection in a Non-Uniform Differentially Heated 3D Cavity

A numerical study of a buoyancy driven convection flow in presence of thermocapillarity has been developed. The fluid is a silicone oil (Prandtl number equal to 105) contained in a three-dimensional box bounded by rigid and impermeable walls with top free surface exposed to a gaseous phase. At the lateral box walls a different non-uniform temperature distribution is assumed so to induce horizontal convection and to keep separated thermocapillary and buoyancy effects. The vorticity-velocity formulation of the time-dependent Navier–Stokes equations for a non-isothermal incompressible fluid is used. A procedure based on a linearized fully implicit finite difference second order scheme has been adopted. We obtained very complex steady configurations for several values of the temperature difference at the lateral walls, T=30, 40 and 50°C. Along the direction perpendicular to the lateral walls, for T increasing, we observe a physically meaningful growth of heat transfer. Confidence in these results is supported by a comparison with recent experimental and numerical observations.     

A mobility-aware dynamic database caching scheme for wireless mobile computing and communications

This paper describes a mobility-aware dynamic database caching scheme for wireless mobile computing and communications. A mobile-floating agent scheme is proposed, in which caching techniques are cognizant of the mobile nature of mobile users and the location-sensitive nature of mobile systems. The mobile-floating agent maintains a second class cache in the fixed network and employs Barbara's invalidation reports broadcasting cache consistency strategies to maintain a dynamic cache consistent with the first class cache in the mobile client. The invalidation reports broadcasting scheme is combined with knowledge of the mobility behavior of each individual mobile user and broadcasts of invalidation reports only occur within the user's mobility area. The evaluation results show that, for a large system (200 cells), this scheme can reduce the system cost by more than 87%, for even highly mobile users, compared with a fully replicated database system.Recommended by: Daniel Barbara, Ravi Jain and Narayanan Krishnakumar     

Supervisory control using variable lookahead policies

This paper deals with the efficient on-line calculation of supervisory controls for discrete event systems (DES's) in the framework of limited lookahead control policies (or LLPs) that we introduced in previous papers. In the LLP scheme, the control action after a given trace of events has been executed is calculated on-line on the basis of anN-step ahead projection of the behavior of the DES. To compute these controls, one must calculate after the execution of each event the supremal controllable sublanguage of a finite language with respect to another finite larger language. In our previous work, we showed how the required supremal controllable sublanguage calculation can be performed by using a backward dynamic programming algorithm over the nodes of the tree representation of these two languages. In this paper, we pursue the same approach for the calculation of LLP controls, but instead we adopt a forward calculation procedure over theN-level tree of interest. This forward procedure improves upon previous work by avoiding the explicit consideration of all the nodes of theN-level tree, while still permitting tree-to-tree recursiveness as enabled events are executed by the system. The forward search ends whenever a control decision can be made unambiguously or whenever the boundary of theN-level tree is reached, whichever comes first. This motivates the name Variable Lookahead Policy (or VLP) for this implementation of the LLP supervisory control scheme. This paper presents a general VLP algorithm and studies the properties of several special cases of it. The paper also discusses the implementation of the VLP algorithms and presents computational results regarding the application of these algorithms to a time-varying DES.