9422928
Fault-containing self-stabilization in asynchronous systems with constant fault-gap
This paper presents a new transformation which adds fault-containment properties to silent self-stabilizing algorithms. The transformation features a constant slow-down factor and the fault-gap—that is the minimal time between two containable faults—is also constant. The transformation scales well to arbitrarily large systems and avoids global synchronization. The presented transformation is the first with a constant fault-gap and requires no knowledge of the system size.
14030194
On Approximating Real-World Halting Problems
No algorithm can of course solve the Halting Problem, that is, decide within finite time always correctly whether a given program halts on a certain given input. It might however be able to give correct answers for ‘most' instances and thus solve it at least approximately. Whether and how well such approximations are feasible highly depends on the underlying encodings and in particular the Godelization (programming system) which in practice usually arises from some programming language. 
 
We consider BrainF*ck (BF), a simple yet Turing-complete real-world programming language over an eight letter alphabet, and prove that the natural enumeration of its syntactically correct sources codes induces a both efficient and dense Godelization in the sense of [Jakoby&Schindelhauer'99]. It follows that any algorithm M approximating the Halting Problem for BF errs on at least a constant fraction eM> 0 of all instances of size n for infinitely many n. 
 
Next we improve this result by showing that, in every dense Godelization, this constant lower bound e to be independent of M; while, the other hand, the Halting Problem does admit approximation up to arbitrary fraction δ> 0 by an appropriate algorithm Mδ handling instances of size n for infinitely many n. The last two results complement work by [Lynch'74].
14726830
Parallelizing XML data-streaming workflows via MapReduce
In prior work it has been shown that the design of scientific workflows can benefit from a collection-oriented modeling paradigm which views scientific workflows as pipelines of XML stream processors. In this paper, we present approaches for exploiting data parallelism in XML processing pipelines through novel compilation strategies to the MapReduce framework. Pipelines in our approach consist of sequences of processing steps that receive XML-structured data and produce, often through calls to ''black-box'' (scientific) functions, modified (i.e., updated) XML structures. Our main contributions are (i) the development of a set of strategies for compiling scientific workflows, modeled as XML processing pipelines, into parallel MapReduce networks, and (ii) a discussion of their advantages and trade-offs, based on a thorough experimental evaluation of the various translation strategies. Our evaluation uses the Hadoop MapReduce system as an implementation platform. Our results show that execution times of XML workflow pipelines can be significantly reduced using our compilation strategies. These efficiency gains, together with the benefits of MapReduce (e.g., fault tolerance) make our approach ideal for executing large-scale, compute-intensive XML-based scientific workflows.