14212270
Practical issues in the use of ABFT and a new failure model
We study the behavior of algorithm based fault tolerance (ABFT) techniques under faults injected according to a quite general fault model. Besides the problem of roundoff error in floating point arithmetic we identify two further weakpoints, namely lack of protection of data during input and output, and incorrect execution of the correctness checks. We propose the robust ABFT technique to handle those weakpoints. We then generalize it to programs that use assertions, where similar problems arise, leading to the technique of robust assertions, whose effectiveness is shown by fault injection experiments on a realistic control application. With this technique a system follows a new failure model, that we call fail-bounded, where with high probability all results produced are either correct or, if wrong, they are within a certain bound of the correct value, whose exact value depends on the output assertions used. We claim that this failure model is very useful to describe the behavior of many low redundancy systems.
35428904
Portable checkpointing and recovery
This paper presents a checkpointing scheme that was implemented in a parallel library that runs on top of CHIMP/MPI. The main goals of the checkpointing mechanism are portability and efficiency. It runs on every platform supported by MPI in a machine-independent way. The scheme allows the migration of checkpoints and offers a flexible recovery mechanism based on data-reconfiguration. Some performance results will be presented at the end of the paper together with some techniques that can be used to increase the efficiency of the checkpointing mechanism.
11033391
System-level versus user-defined checkpointing
Checkpointing and rollback recovery is a very effective technique to tolerate transient faults and preventive shutdowns. In the past, most of the checkpointing schemes published in the literature were supposed to be transparent to the application programmer and implemented at the operating-system level. In recent years, there has been some work on higher-level forms of checkpointing. In this second approach, the user is responsible for the checkpoint placement and is required to specify the checkpoint contents. We compare the two approaches: system-level and user-defined checkpointing. We discuss the pros and cons of both approaches and we present an experimental study that was conducted on a commercial parallel machine.
22782109
A Fault-Tolerant Mechanism for Simple Controllers
There are many industrial controllers where no systematic fault-tolerant mechanisms are included because of cost constraints. This paper addresses that problem by making a proposal for a simple and low-cost fault-tolerant technique, yet very effective, that can be used even in the simplest controllers. The mechanism is able of tolerating both hardware and software faults. It uses behaviour-based error detection, with checkpointing and rollback, to give resiliency to the application. The programs are made of possibly non-deterministic processes that communicate solely by messages. The technique, called RP-Actions, also guarantees that the recovery is domino-effect free. Software bugs are caught by acceptance tests as in recovery blocks. Forward error recovery is used for time, since time cannot be rolled back. Several implementations of the proposed mechanisms were made — we present in this paper some important results.
35292815
WPVM: parallel computing for the people
This paper presents WPVM, a PVM implementation for the “MS Windows” — Microsoft Windows Operating System. WPVM stands for “Windows Parallel Virtual Machine” and intends to exploit the potential computational power of the small and medium PC LANs that proliferate in corporations and universities. As the original PVM [1–2], WPVM creates the abstraction of a parallel machine from a cluster of computers connected by a network. This virtual machine appears as a single and manageable resource to the programmer. The difference is that the target machines for WPVM are personal computers with MS Windows instead of UNIX machines. However, this system is compatible with the original PVM, meaning that we can use virtual machines composed simultaneously of UNIX and MS Windows machines.
11507520
Web-based Metacomputing with JET
8215557
Time Equations for Lazy Functional (Logic) Languages
There are very few approaches to measure the execution costs of lazy functional (logic) programs. The use of a lazy execution mechanism implies that the complexity of an evaluation depends on its context, i.e., the evaluation of the same expression may have different costs depending on the degree of evaluation required by the different contexts where it appears. In this paper, we present a novel approach to complexity analysis of functional (logic) programs. We focus on the construction of equations which compute the time-complexity of expressions. In contrast to previous approaches, it is simple, precise—i.e., it computes exact costs rather than upper/lower bounds—, and fully automatic.
206855912
An algorithm to compare OO-conceptual schemas
In this paper, an algorithmic study of how to compare object-oriented conceptual schemas in a data migration context is carried out. An algorithm is presented based on the tree-comparison technique that compares conceptual schemas. The algorithm uses semantic information in order to optimize efficiency. A template of the equivalences and differences between two schemas is generated in an automatic way. The template shows the results in terms of insertions, updates and deletions. This work is the first phase in a tool which performs the automatic migration of databases starting from the differences detected.
62642642
GRASP—a new search algorithm for satisfiability
This paper introduces GRASP (Generic seaRch Algorithm for the Satisfiability Problem), an integrated algorithmic framework for SAT that unifies several previously proposed search-pruning techniques and facilitates identification of additional ones. GRASP is premised on the inevitability of conflicts during search and its most distinguishing feature is the augmentation of basic backtracking search with a powerful conflict analysis procedure. Analyzing conflicts to determine their causes enables GRASP to backtrack non-chronologically to earlier levels in the search tree, potentially pruning large portions of the search space. In addition, by "recording" the causes of conflicts, GRASP can recognize and preempt the occurrence of similar conflicts later on in the search. Finally, straightforward bookkeeping of the causality chains leading up to conflicts allows GRASP to identify assignments that are necessary for a solution to be found. Experimental results obtained from a large number of benchmarks, including many from the field of test pattern generation, indicate that application of the proposed conflict analysis techniques to SAT algorithms can be extremely effective for a large number of representative classes of SAT instances.
9584994
A Traffic Differentiation Method for IPv6 over ATM Networks
At present, the number of Internet users continues to increase dramatically, accompanied by the large-scale introduction of new applications with multimedia capabilities. New users and applications are constantly demanding better performance from the Internet, if possible with some forms of quality of service (QoS) guarantees. Knowing that no single technology is able to provide such guarantees in the Internet environment — which, by definition is a multi-technology environment — the exploration of promising technologies capable of traffic differentiation that are applicable to parts of the Internet appears as a possible way forward. This paper addresses and explores the benefits of the Internet Protocol version 6 (IPv6) and Asynchronous Transfer Mode (ATM) integration in multimedia environments. A method for traffic differentiation in IPv6-over-ATM networks is proposed, based on the mapping of different IPv6 flows into the address resolution functions of ATM. The proposal is evaluated in terms of introduced overhead, by means of simulation studies, supported by an experimental platform and an IPv6-over-ATM simulator developed for this purpose.
15739638
Identification of Document Language is Not yet a Completely Solved Problem
Existing Language Identification (LID) approaches do reach 100% precision, in most common situations, when dealing with documents written in just one language, and when those documents are large enough. However, LID approaches do not provide a reliable solution for some situations: when there is need to discriminate the correct variant of the language used in a text, for example, European or Brazilian variants of Portuguese, UK or USA English variants, or any other language variants. Another hard context occur with small touristic advertisements on the web, addressing foreigners but using local language to name most local entities. In this paper, we present a fully statistics- based LID approach which learns the most discriminant information according to each context, and identifies the correct language or language variant a text is written in. This methodology is shown to be correct for normal texts and maintains its robustness in hard LID contexts.