9432716
Coordinated exception handling in distributed object systems: from model to system implementation
Exception handling in concurrent and distributed programs is a difficult task though it is often necessary. In many cases traditional exception mechanisms for sequential programs are no longer appropriate. One major difficulty is that the process of handling an exception may need to involve multiple concurrent components that are cooperating in pursuit of some global goal. Another complication is that several exceptions may be raised concurrently in different nodes of a distributed environment. Existing proposals and actual concurrent languages either ignore these difficulties or only cope with a limited form of them. The paper attempts a general solution, developed especially for distributed object systems, starting from a conceptual model, together with algorithms for coordinating concurrent components and resolving multiple exceptions, through to an actual system implementation. An industrial production cell is chosen as a case study to demonstrate the usefulness of the proposed model and algorithms. A system that supports coordinated atomic actions and exception resolution is implemented in distributed Ada 95 and examined through several performance-related experiments.
7149198
A fault-tolerant approach to secure information retrieval
Several private information retrieval (PIR) schemes were proposed to protect users' privacy when sensitive information stored in database servers is retrieved. However, existing PIR schemes assume that any attack to the servers does not change the information stored and any computational results. We present a novel fault-tolerant PIR scheme (called FT-PIR) that protects users' privacy and at the same time ensures service availability in the presence of malicious server faults. Our scheme neither relies on any unproven cryptographic assumptions nor the availability of tamper-proof hardware. A probabilistic verification function is introduced into the scheme to detect corrupted results. Unlike previous PIR research that attempted mainly to demonstrate the theoretical feasibility of PIR, we have actually implemented both a PIR scheme and our FT-PIR scheme in a distributed database environment. The experimental and analytical results show that only modest performance overhead is introduced by FT-PIR while comparing with PIR in the fault-free cases. The FT-PIR scheme tolerates a variety of server faults effectively. In certain fail-stop fault scenarios, FT-PIR performs even better than PIR. It was observed that 35.82% less processing time was actually needed for FT-PIR to tolerate one server fault.
2775894
Rigorous development of a safety-critical system based on coordinated atomic actions
This paper describes our experience using coordinated atomic (CA) actions as a system structuring tool to design and validate a sophisticated control system for a complex industrial application that has high reliability and safety requirements. Our study is based on the "Fault-Tolerant Production Cell", which represents a manufacturing process involving redundant mechanical devices (provided in order to enable continued production in the presence of machine faults). The challenge posed by the model specification is to design a control system that maintains specified safety and liveness properties even in the presence of a large number and variety of device and sensor failures. We discuss in this paper: i) a design for a control program that uses CA actions to deal with both safety-related and fault tolerance concerns, and ii) the formal verification of this design based on the use of model-checking. We found that CA action structuring facilitated both the design and verification tasks by enabling the various safety problems (e.g. clashes of moving machinery) to be treated independently. The formal verification activity was performed in parallel with the design activity the interaction between them resulted in a combined exercise in "design for validation".
11532584
Sequentially t-Diagnosable Systems: A Characterization and Its Applications
In the system level fault diagnosis area, the fundamental problem of characterizing sequentially t-diagnosable systems in the PMC model has remained open for more than two decades. We resolve this problem by providing a complete characterization of such systems. Our solution to the characterization problem leads to the correct identification of optimal sequentially t-diagnosable D/sub /spl delta/,k/ systems. Given a set of n units where n=2t+1, an optimal D/sub /spl delta/,k/ system can be constructed with just n([(t+2)/3]) tests, rather than n([t/2]+1) tests-a previously misjudged bound. An efficient algorithm for identifying the set of faulty units in a sequentially t-diagnosable D/sub /spl delta/,k/ system is given along the line of the proposed characterization, which is linear with respect to the number of tests in the system. >
5963621
Concurrent Exception Handling and Resolution in Distributed Object Systems
We address the problem of how to handle exceptions in distributed object systems. In a distributed computing environment, exceptions may be raised simultaneously in different processing nodes and thus need to be treated in a coordinated manner. Mishandling concurrent exceptions can lead to catastrophic consequences. We take two kinds of concurrency into account: 1) Several objects are designed collectively and invoked concurrently to achieve a global goal and 2) multiple objects (or object groups) that are designed independently compete for the same system resources. We propose a new distributed algorithm for resolving concurrent exceptions and show that the algorithm works correctly even in complex nested situations, and is an improvement over previous proposals in that it requires only O(n/sub max/N/sup 2/) messages, thereby permitting quicker response to exceptions.
11432676
Building Embedded Fault-Tolerant Systems for Critical Applications: An Experimental Study
An increasing range of industries have a growing dependence on embedded software systems, many of which are safety-critical, real-time applications that require extremely high dependability. Two fundamental approaches — fault avoidance and fault tolerance — have been proposed to increase the overall dependability of such systems. However, the increased cost of using the fault tolerance approach may mean that this increase in dependability is not worth the extra expense involved. We describe an experiment undertaken in order to establish whether or not software redundancy (or the multi-version design method) can offer increased dependability over the traditional single-version development approach when given the same level of resources. The results of this and a subsequent follow-up study are then given. The analytic results from these experiments show that despite the poor quality of individual versions, the multi-version method results in a safer system than the single-version solution. It is evident that regarding the single-version method as a “seem-to-be” safer design decision for critical applications is not generally justifiable.
45243230
Experiences in Modelling Feature Interactions with Coloured Petri Nets
A modern mobile phone supports many features: voice and data calls, text messaging, personal information management like phonebooks and calendars, WAP browsing, games, alarm clock, etc. All these features are packaged into a handset with a small display and a special purpose keypad. The limited user interface and the seamless intertwining of logically separate features cause many interactions between the software components in the UI of mobile phones. In this paper, we present an overview of our approach to modelling feature interactions in Nokia's mobile phones with explicit behavioral models of features. We use Coloured Petri Nets as the modeling language and the tool Design/CPN that provides a graphical, interactive user interface for constructing and simulating Coloured Petri Nets. We describe at a general level how we have created a graphical user interface for controlling and observing the simulations of models through an on-screen mock-up of a mobile phone. Then, we discuss the conrete results we have achieved by using our approach.
36507
Ranking definitions with supervised learning methods
This paper is concerned with the problem of definition search. Specifically, given a term, we are to retrieve definitional excerpts of the term and rank the extracted excerpts according to their likelihood of being good definitions. This is in contrast to the traditional approaches of either generating a single combined definition or simply outputting all retrieved definitions. Definition ranking is essential for the task. Methods for performing definition ranking are proposed in this paper, which formalize the problem as either classification or ordinal regression. A specification for judging the goodness of a definition is given. We employ SVM as the classification model and Ranking SVM as the ordinal regression model respectively, such that they rank definition candidates according to their likelihood of being good definitions. Features for constructing the SVM and Ranking SVM models are defined. An enterprise search system based on this method has been developed and has been put into practical use. Experimental results indicate that the use of SVM and Ranking SVM can significantly outperform the baseline methods of using heuristic rules or employing the conventional information retrieval method of Okapi. This is true both when the answers are paragraphs and when they are sentences. Experimental results also show that SVM or Ranking SVM models trained in one domain can be adapted to another domain, indicating that generic models for definition ranking can be constructed.
1910049
Quality is in the eye of the beholder: towards user-centric web-databases
The proliferation of database-driven web sites (or web-databases) has brought upon a plethora of applications where both Quality of Service (QoS) and Quality of Data (QoD) are of paramount importance to the end users. In our previous work, we have proposed Quality Contracts, a comprehensive framework for specifying multiple dimensions of QoS/QoD; we have also developed user-centric admission control and scheduling algorithms in web databases, whose goal is to maximize overall system performance. In this work, we turn our attention to the user side of the equation. Specifically, we propose to demonstrate how the adaptation of Quality Contracts (QCs) by the users can lead to vastly different performance results, both from the user point of view (i.e., user satisfaction) and also from the system point of view. Towards this, we propose to structure our demo in the form of an interactive game, where participants will be playing the role of users continuously adapting their QCs over time, while "playing" against system-generated users, who follow predetermined QC adaptation policies. Finally, we also propose to illustrate the effect of different admission control and scheduling policies.
21098955
Topological Peeling and Implementation
We present a new approach, called topological peeling, and its implementation for traversing a portion AR of the arrangement formed by n lines within a convex region R on the plane. Topological peeling visits the cells of AR in a fashion of propagating a "wave" of a special shape (called a double-wriggle curve) starting at a single source point. This special traversal fashion enables us to solve several problems (e.g., computing shortest paths) on planar arrangements to which previously best known arrangement traversal techniques such as topological sweep and topological walkm ay not be directly applicable. Our topological peeling algorithm takes O(K + n log(n + r)) time and O(n + r) space, where K is the number of cells in AR and r is the number of boundary vertices of R. Comparing with topological walk, topological peeling uses a simpler and more efficient way to sweep different types of lines, and relies heavily on exploring small local structures, rather than a much larger global structure. Experiments show that, on average, topological peeling outperforms topological walkb y 10 - 15% in execution time.
26138426
2-diameter of de Bruijn graphs
Binary strings are used as vertex labels or components of vertex labels. We will abbreviate “the vertex with label X” as “vertex x.” The binarji direcred de Briiijn graph of dimension n , denoted B ( n ) , has 2 ” vertices which are labeled with the binary strings of length n . There is an arc from any vertex x, x2 xn to the vertices x2x3 x,O and x2x3 x,, 1. We say that the ith coordinate of ,Y is x, . Any .u, is equal toOor l , andZ, = 1 x i . The undirected binary de Bruijn graph UB( n ) is obtained from B( n) by deleting the orientation of the arcs and omitting multiple edges and loops. It is well known that UB( n ) is 2-connected and that its diameter (maximum of the distances between all pairs of vertices) is equal to n . Due to their bounded maximum degree equal to 4 and their low diameter, de Bruijn graphs have been proposed as a possible good interconnection network for a parallel architecture [ 11. They have also been shown to solve a wide class of problems [ 21. For a k-connected graph, Hsu [ 4 ] introduced the notion of the kdiameter as follows: Given any two vertices x and y , a k-container between x and y is a set of k vertex disjoint paths between xand y . The length ofa k-container is the length of the longest of the k paths. The kdistance d k ( x , y ) between x and y is the minimum of the lengths of all the k-containers. Then, the k-diameter of a graph G is the maximum of d k ( x , y) for all pairs of vertices x and y . General results on the k-diameters of k-regular kconnected graphs can be found in [ 41 or [ 51. Results for some particular classes ofgraphs and many open problems can also be found in [ 41. It was shown by Pradhan and Reddy [ 7 ] that the 2diameter of U B ( n ) is less than or equal to 2n. The 2diameter is also obviously at least n. The aim of this paper was to prove that it is exactly n. In other words, between any two vertices of UB( n ) , there exist two internally vertex disjoint paths of length at most n. This gives a good measure of the fault tolerance of the graph [ 61. Let us first introduce some notation and recall some properties of the de Bruijn digraph B( n ) : Given two vertices x and y , we will denote f i x , y ] as a shortest path P from x to y . The length of this path, denoted by I PIX, y ] 1, is the number of edges in the path and is also the distance d ( x , y ) from x to y . P [ x , y ] also represents the set of vertices of the path, including its extremities.