We propose a comprehensive solution to handle memory-overflow problems in multitasking embedded systems thereby improving their reliability and availability. In particular, we propose two complementary techniques to address two significant causes of memory-overflow problems. The first cause is errors in estimating appropriate stack and heap memory requirement. Our first technique, called shared supplementary memory (SSM), exploits the fact that the probability of multiple tasks requiring more than their estimated amount of memory concurrently is low. Using analytical model and simulations, we show that reliability can be considerably improved when SSM is employed. Furthermore, for the same reliability, SSM reduces total memory requirement by as much as 29.31% The second cause is the presence of coding Mandelbugs, which can cause abnormal memory requirement. To address this, we propose a novel technique, called opportunistic micro-rejuvenation, which when combined with SSM, provide several advantages: preventing critical-time outage, resource frugality and dependability enhancement.

Networked multimedia applications require stringent quality of service (QoS) guarantees from the underlying data network. Many techniques have been proposed at the network layer to deliver acceptable QoS for such applications. In this paper, we explore providing network monitoring support in the application layer for QoS policies. We study the feasibility of a scalable network monitoring service that real-time applications may access to gather network status information in order to adapt to changing network conditions and take actions such as making application level routing decisions. We propose a scalable, low probing overhead monitoring service based on monitoring utilization on network devices traversed by multimedia traffic. Our motivation is to take advantage of often intersecting end-to-end paths traversed by multimedia traffic in an enterprise setting. We empirically assess the QoS improvements resulting from a service that monitors network utilization for an application involving dynamic server selection on a real production network. Specifically, we compare the performance of various dynamic server selection strategies for multimedia streaming including random selection, round-trip time based selection, proximity based selection, and utilization based selection. Our results indicate that compared to random selection, server selection strategies that rely on our network utilization based monitoring scheme result in significantly lower end-to-end delay and packet loss in streaming sessions. Compared to round-trip time based selection, our scheme results in comparable end-to-end delay and loss figures while incurring significantly lower probing cost

The presence of physical obstacles and radio interfer-ence results in the so called “shadow regions ” in wireless networks. When a mobile station roams into a shadow re-gion, it loses its network connectivity. In cellular networks, in order to minimize the connection unreliability, careful cell planning is required to prevent the occurrance of the shadow regions in the first place. In 802.11b/g wireless LANs, however, due to the limited frequency spectrum, it is not always possible to prevent a shadow region by adding another cell at a different frequency. Our contribution in this paper is to propose the alternate approach of tolerating the existence of “shadow regions ” as opposed to prevention in order to enhance the connection dependability. A redundant access point (AP) is placed in

We present a model for analyzing the reliability of component based software systems. Each software component is described as a finite state machine whose transitions have failure probabilities that reflect the unreliable execution of elementary component operations. Alternatively, we model a component as a finite state machine with an associated reliability figure that expresses the overall reliability of the component. Using our model, we prove that there is no algorithm that can accurately calculate the reliability of a system of finite state machines with known or estimated overall reliabilities or transition failure probabilities. The same negative result holds even if we only want to approximate the system reliability.

Summary form only given, as follows. J. Von Neumann (1956) and E.F. Moore and C.F. Shannon (1956) discussed building reliable automata and relay circuits (hardware) using less reliable components. They show that carefully designed replication of components in a hardware system can increase the probability of failure free operation of that system. There is a powerful trend in the industry now to build software systems using as many software components as possible. These components might be commercial off the shelf (COTS) or in-house software libraries and modules; we call all such components reusable software components. We argue that the reliability of such a software system can be improved not only by replicating the software components, but also by active monitoring, checkpointing and rejuvenation, and providing facilities for cold, warm and hot fail over/restart of those components. These capabilities themselves can be built as reusable software modules that can be linked to the actual system components. We present the architecture of such a software system and a preliminary analysis to show the feasibility of this approach for building reliable software systems using reusable software components. Research into analyzing the reliability of such systems is gaining attention. These facilities provide diversity in the execution environment of a software component leading to a higher level of reliability of the software system, much as replication provides diversity in the physical environment of a hardware component giving rise to improved reliability of the hardware system that Von Neumann and others have pioneered.

A method of execution retry for bypassing software faults in message-passing applications is described in this paper. Based on the techniques of checkpointing and message logging, we demonstrate the use of message replaying and message reordering as two mechanisms for achieving localized and fast recovery. The approach gradually increases the rollback distance and the number of affected processes when a previous retry fails, and is therefore named progressive retry. Examples from telecommunications software systems and performance measurements from an application-level implementation are described to illustrate the benefits of the scheme.

Checkpointing with rollback-recovery is a well known technique to reduce the completion time of a program in the presence of failures. While checkpointing is corrective in nature, rejuvenation refers to preventive maintenance of software aimed to reduce unexpected failures mostly resulting from the "aging" phenomenon. In this paper, we show how both these techniques may be used together to further reduce the expected completion time of a program. The idea of using checkpoints to reduce the amount of rollback upon a failure is taken a step further by combining it with rejuvenation. We derive the equations for expected completion time of a program with finite failure free running time for the following three cases when; (a) neither checkpointing nor rejuvenation is employed, (b) only checkpointing is employed, and finally (c) both checkpointing and rejuvenation are employed.We also present numerical results for Weibull failure time distribution for the above three cases and discuss optimal checkpointing and rejuvenation that minimizes the expected completion time. Using the numerical results, some interesting conclusions are drawn about benefits of these techniques in relation to the nature of failure distribution.

Systems which translate queries written using a high-level conceptual model of a database into sequences of commands based on another model of the database are studied here. We take the view that these translators are similar to, albeit simpler than, the compilers for programming languages. Motivated by the recent interest in describing all the aspects of a compiler by an attributed grammar, we specify the formal syntax and semantics of two working database translators using attributed grammars. All the precise details about the parsing, the code optimization and the rules for preserving the query semantics are captured by those grammars. It is hoped that this approach brings the understanding of query languages closer to that of programming languages, and opens the possibility of applying the emerging technology of semantics-directed compiler construction to build query language translator-generators and to prove those translators correct.

This paper proves the correctness of a translation from HISEL, a relational database query language, to HI, a hierarchical query language.The four components of Morris' [7] program are established. Appropriate semantics for the two languages are defined. A translation function is defined and an L-attributed grammar capturing the translation function is exhibited. The transformation of database trees into database relations is specified.

Let $\mathcal {P}_{g(n)} $ denote the class of languages acceptable by polynomial-time bounded Turing machines making at most $g(n)$ nondeterministic moves on inputs of length n. For any constructible $g(n)$,$\mathcal {P} \subseteq \mathcal {P}_{g(n)} \subseteq \mathcal {N}\mathcal {P}$The classes $\mathcal {P}_{g(n)} $, for various $g(n)$ of the form $(\log n)^k ,k \geqq 1$, are relativized and the relationships among those relativized classes are studied. In particular, oracle sets are constructed which (1) make all the relativized classes equal (this follows from Baker, Gill and Solovay (1975)); (2) make all the classes associated with powers of $\log n$ different; (3) for any k, make all the classes below $(\log n)^k $ different while the kth power class is equal to relativized $\mathcal {NP}$. Results regarding closure of the $(\log n)^k $ classes under complementation are also given.

Nondeterminism is one of the most elusive concepts in computing.