Search

A classical theme in recursion theory is the question whether for a set A and n given elements x1,...,xn, an oracle machine having access to an oracle B can determine which of the elements xi belong to A. And if yes, how many queries are necessary? Here, B = A is possible and leads to interesting special cases of the general question In the present paper we adapt classical notions in this area of bounded query computations to real number algorithms as formalized by Blum, Shub, and Smale and analyze them in the new framework. Among the results obtained we find: A real version of a non-speedup theorem based on real quantifier elimination, some basic properties about selective real sets, and a way to construct natural terse sets in ℝ by applying the implicit function theorem. The purpose of the paper is on presenting some interesting questions and basic results as an appertizer to intensify research into this direction. [ABSTRACT FROM AUTHOR]

In this paper, we study to what extent decidability is connected to universality. A natural context for such a study is provided by the axiomatic theory of computability, automata and algorithms. In Section 2, we introduce necessary concepts, constructions, axioms, postulates, conditions and problems. Section 3 contains the main results of the paper. In particular, it is demonstrated (Theorems 1 and 2) that undecidability of algorithmic problems does not depend on existence of universal algorithms and may be caused by weaker conditions. At the same time, results of Theorems 2 and 3 demonstrate that decidability is incompatible with universality. It is also proved (Theorem 5) that sufficiently big classes of total algorithms/automata, such as the class of all primitive recursive functions, cannot have universal algorithms/automata. [ABSTRACT FROM AUTHOR]

This paper describes a failure scenario in the known self-stabilizing algorithm for knot detection in directed graphs, occurring due to incorrect computation of certain variables. A modified algorithm is proposed, which overcomes the shortcomings of the known algorithm. [ABSTRACT FROM AUTHOR]

This paper presents a new lower bound for the model-checking algorithm based on solving parity games due to Stevens and Stirling. We outline a family of games of linear size on which the algorithm requires exponential time. [ABSTRACT FROM AUTHOR]

Checkpoint is a designated place in a program at which normal process is interrupted specifically to preserve the status information necessary to allow resumption of processing at a later time. A checkpoint algorithm for mobile distributed systems needs to handle many new issues like: mobility, low bandwidth of wireless channels, lack of stable storage on mobile nodes, disconnections, limited battery power and high failure rate of mobile nodes. These issues make traditional checkpointing techniques unsuitable for such environments. Minimum-process coordinated checkpointing is an attractive approach to introduce fault tolerance in mobile distributed systems transparently. This approach is domino-free, requires at most two checkpoints of a process on stable storage, and forces only a minimum number of processes to checkpoint. But, it requires extra synchronization messages, blocking of the underlying computation or taking some useless checkpoints. In this paper, we design a minimum-process checkpointing algorithm for mobile distributed systems, where no useless checkpoint is taken. We reduce the blocking of processes by allowing the processes to do their normal computations, send messages and receive selective messages during their blocking period. [ABSTRACT FROM AUTHOR]

Sense of direction is a property of the edge-labeling of a network whose availability facilitates computations and often decreases their complexity. In this paper we consider the problem of providing a sense of direction to an anonymous, unoriented torus. The edges of the torus are initially labeled arbitrarily, and they have to be relabeled with a classical compass sense of direction. We first describe an algorithm where the relabeling of the edges is performed by a mobile agent that carries a token. The algorithm is optimal both in terms of number of tokens (with no tokens the task cannot be performed), and in terms of number of moves. We then show that the same technique can be used to orient the torus in the classical message-passing environment, thus obtaining an orientation algorithm that improves all the existing ones in this setting. [ABSTRACT FROM AUTHOR]

Recent advances in scheduling and networking have paved the way for efficient exploitation of large-scale distributed computing platforms such as computational grids and huge clusters. Such infrastructures hold great promise for the highly resource-demanding task of verifying and checking large models, given that model checkers would be designed with a high degree of scalability and flexibility in mind. In this paper we focus on the mechanisms required to execute a high-performance, distributed, symbolic model checker on top of a large-scale distributed environment. We develop a hybrid algorithm for slicing the state space and dynamically distribute the work among the worker processes. We show that the new approach is faster, more effective, and thus much more scalable than previous slicing algorithms. We then present a checkpoint-restart module that has very low overhead. This module can be used to combat failures, the likelihood of which increases with the size of the computing plat-form. However, checkpoint-restart is even more handy for the scheduling system: it can be used to avoid reserving large numbers of workers, thus making the distributed computation work-efficient. Finally, we discuss for the first time the effect of reorder on the distributed model checker and show how the distributed system performs more efficient reordering than the sequential one. We implemented our contributions on a network of 200 processors, using a distributed scalable scheme that employs a high-performance industrial model checker from Intel. Our results show that the system was able to verify real-life models much larger than was previously possible. [ABSTRACT FROM AUTHOR]

In this paper, we propose a resource estimation algorithm which considers imprecise system characteristics and multiple design attributes. The algorithm is based on a polynomial-time process called inclusion scheduling. Inclusion scheduling takes imprecise system information and generates an averagely good schedule with respect to a design goal. The schedule is associated with various properties. These information are used to determine the initial resource bounds subject to the design goal. Experimental results showing the effectiveness of the approach by comparing the design configuration generated by the traditional algorithm and the approach are presented. [ABSTRACT FROM AUTHOR]