CSL model checking algorithms for QBDs

We present an in-depth treatment of model checking algorithms for a class of infinite-state continuous-time Markov chains known as quasi-birth death processes. The model class is described in detail, as well as the logic CSL to express properties of interest. Using a new property-independency concept, we provide model checking algorithms for all the CSL operators. Special emphasis is given to the time-bounded until operator for which we present a new and efficient computational procedure named uniformization with representatives. By the use of an application-driven dynamic stopping criterion, the algorithm stops whenever the property to be checked can be certified (or falsified). A comprehensive case study of a connection management system shows the versatility of our new algorithms.     

Symbolic model checking for self-stabilizing algorithms

A distributed system is said to be self-stabilizing if it converges to safe states regardless of its initial state. In this paper we present our results of using symbolic model checking to verify distributed algorithms against the self-stabilizing property. In general, the most difficult problem with model checking is state explosion; it is especially serious in verifying the self-stabilizing property, since it requires the examination of all possible initial states. So far applying model checking to self-stabilizing algorithms has not been successful due to the problem of state explosion. In order to overcome this difficulty, we propose to use symbolic model checking for this purpose. Symbolic model checking is a verification method which uses Ordered Binary Decision Diagrams (OBDDs) to compactly represent state spaces. Unlike other model checking techniques, this method has the advantage that most of its computations do not depend on the initial states. We show how to verify the correctness of algorithms by means of SMV, a well-known symbolic model checker. By applying the proposed approach to several algorithms in the literature, we demonstrate empirically that the state spaces of self-stabilizing algorithms can be represented by OBDDs very efficiently. Through these case studies, we also demonstrate the usefulness of the proposed approach in detecting errors     

Decision-diagram-based techniques for bounded reachability checking of asynchronous systems

Bounded reachability analysis and bounded model checking are widely believed to perform poorly when using decision diagrams instead of SAT procedures. Recent research suggests this to be untrue with regards to synchronous systems and, in particular, digital circuits. This article shows that the belief is also a myth for asynchronous systems, such as models specified by Petri nets. We propose several Bounded Saturation approaches to compute bounded state spaces using decision diagrams. These approaches are based on the established Saturation algorithm, which benefits from a non-standard search strategy that is very different from breadth-first search, but employ different flavors of decision diagrams: multi-valued decision diagrams, edge-valued decision diagrams, and algebraic decision diagrams. We apply our approaches to studying deadlock as a safety property. Our extensive benchmarking shows that our algorithms often, but not always, compare favorably against two SAT-based approaches that are advocated in the literature. Research supported by the NSF under grants CNS-0501747 and CNS-0501748 and by the EPSRC under grant GR/S86211/01. An extended abstract of this article appeared in the proceedings of the 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), LNCS~4424, pp.~648–663, 2007, Springer.     

A dynamic debugger for asynchronous distributed algorithms

LPdbx is a distributed runtime debugger for loosely coupled parallel processors with an iconic interface. When a program suspends, users can insert additional breakpoints and examine global variables, structures, and pointer references. It has been used to debug banking and transportation applications and is available for distribution     

Parallel asynchronous team algorithms: convergence and performanceanalysis

This paper formalizes a general technique to combine different methods in the solution of large systems of nonlinear equations using parallel asynchronous implementations on distributed-memory multiprocessor systems. Such combinations of methods, referred to as team algorithms, are evaluated as a way of obtaining desirable properties of different methods and a sufficient condition for their convergence is derived. The load flow problem of electrical power networks is presented as an example problem that, under certain conditions, has the characteristics to make a team algorithm an appealing choice for its solution. Experimental results of an implementation on an Intel iPSC/860 Hypercube are reported, showing that considerable speedup and robustness can be obtained using team algorithms     

Distributed asynchronous deterministic and stochastic gradient optimization algorithms

We present a model for asynchronous distributed computation and then proceed to analyze the convergence of natural asynchronous distributed versions of a large class of deterministic and stochastic gradient-like algorithms. We show that such algorithms retain the desirable convergence properties of their centralized counterparts, provided that the time between consecutive interprocessor communications and the communication delays are not too large.     

Asymptotic agreement and convergence of asynchronous stochastic algorithms

In this paper, we present results on the convergence and asymptotic agreement of a class of asynchronous stochastic distributed algorithms which are in general time-varying, memory-dependent, and not necessarily associated with the optimization of a common cost functional. We show that convergence and agreement can be reached by distributed learning and computation under a number of conditions, in which case a separation of fast and slow parts of the algorithm is possible, leading to a separation of the estimation part from the main algorithm.     

Redundancy checking algorithms based on parallel novel extension rule

Abstract

Redundancy checking (RC) is a key knowledge reduction technology. Extension rule (ER) is a new reasoning method, first presented in 2003 and well received by experts at home and abroad. Novel extension rule (NER) is an improved ER-based reasoning method, presented in 2009. In this paper, we first analyse the characteristics of the extension rule, and then present a simple algorithm for redundancy checking based on extension rule (RCER). In addition, we introduce MIMF, a type of heuristic strategy. Using the aforementioned rule and strategy, we design and implement RCHER algorithm, which relies on MIMF. Next we design and implement an RCNER (redundancy checking based on NER) algorithm based on NER. Parallel computing greatly accelerates the NER algorithm, which has weak dependence among tasks when executed. Considering this, we present PNER (parallel NER) and apply it to redundancy checking and necessity checking. Furthermore, we design and implement the RCPNER (redundancy checking based on PNER) and NCPPNER (necessary clause partition based on PNER) algorithms as well. The experimental results show that MIMF significantly influences the acceleration of algorithm RCER in formulae on a large scale and high redundancy. Comparing PNER with NER and RCPNER with RCNER, the average speedup can reach up to the number of task decompositions when executed. Comparing NCPNER with the RCNER-based algorithm on separating redundant formulae, speedup increases steadily as the scale of the formulae is incrementing. Finally, we describe the challenges that the extension rule will be faced with and suggest possible solutions.     

Designing fast LTL model checking algorithms for many-core GPUs

Recent technological developments made various many-core hardware platforms widely accessible. These massively parallel architectures have been used to significantly accelerate many computation demanding tasks. In this paper, we show how the algorithms for LTL model checking can be redesigned in order to accelerate LTL model checking on many-core GPU platforms. Our detailed experimental evaluation demonstrates that using the NVIDIA CUDA technology results in a significant speedup of the verification process. Together with state space generation based on shared hash-table and DFS exploration, our CUDA accelerated model checker is the fastest among state-of-the-art shared memory model checking tools.     

Recognition of 3-D objects by forward checking constrained search

An attempt to recognize 3-D objects from range images is described. Objects are represented by surface patches obtained by segmenting image at depth or orientation discontinuity. To find the best matching pairs between model surface patches (MSPs) and scene surface patches (SSPs), we use forward checking constrained tree search that is a sequential constrained tree search with a forward checking mechanism. It checks geometric constraints between current partial matching pairs and unexplored possible pairs and drastically reduces the number of candidate MSPs matchable to unexplored SSPs. Futhermore, it yields powerful search termination criteria. As an alternative to the sequential search method, we also applied the optimal search algorithm (A^*). To verify advantages of the forward checking, we evaluated the perfomance of the matching algorithms using real range images. The experimental results demonstrated significant gains in computation. Comparing with other methods, our approach is particularly advantageous for the difficult problems in that model objects are very much similar to each other. Our method detects part in difference in advance and so reduces time to discriminate the similar objects. It is confirmed by an evaluation.     

A decentralized convergence detection algorithm for asynchronous parallel iterative algorithms

We introduce a theoretical algorithm and its practical version to perform a decentralized detection of the global convergence of parallel asynchronous iterative algorithms. We prove that, even if the algorithm is completely decentralized, the detection of global convergence is achieved on one processor under the classical conditions. The proposed algorithm is very useful in the context of grid computing in which the processors are distributed and in which detecting the convergence on a master processor may be penalizing or even impossible as in peer to peer computation frameworks. Finally, the efficiency of the practical algorithm is illustrated in a typical experiment.     

JACK: an asynchronous communication kernel library for iterative algorithms

This article presents a new communication library developed to ease the implementation of both asynchronous and synchronous iterative methods. A mathematical and algorithmic framework about fixed-point methods is described to introduce this class of parallel iterative algorithms, although this library can be used for a larger class of parallel algorithms. After an overview of the main features, we describe detailed implementation aspects arising from the asynchronous context. While the library is mainly based on top of Message Passing Interface library, it has been designed to be easily extended to other types of communication middleware. Finally, some numerical experiments validate this new library, used for implementing both a classical parallel scheme and a sub-structuring approach of the Jacobi iterative method.     

Distributed disk-based algorithms for model checking very large Markov chains

In this paper we present data structures and distributed algorithms for CSL model checking-based performance and dependability evaluation. We show that all the necessary computations are composed of series or sums of matrix-vector products. We discuss sparse storage structures for the required matrices and present efficient sequential and distributed disk-based algorithms for performing these matrix-vector products. We illustrate the effectivity of our approach in a number of case studies in which continuous-time Markov chains (generated in a distributed way from stochastic Petri net specifications) with several hundreds of millions of states are solved on a workstation cluster with 26 dual-processor nodes. We show details about the memory consumption, the solution times, and the speedup. The distributed message-passing algorithms have been implemented in a tool called PARSECS, that also takes care of the distributed Markov chain generation and that can also be used for distributed CTL model checking of Petri nets.     

Dynamic load balancing and efficient load estimators for asynchronous iterative algorithms

In a previous paper, we have shown the very high power of asynchronism for parallel iterative algorithms in a global context of grid computing. In this article, we study the interest of coupling load balancing with asynchronism in such algorithms. After proposing a noncentralized version of dynamic load balancing which is best suited to asynchronism, we verify its efficiency by some experiments on a general partial differential equation (PDE) problem. Finally, we give some general conditions for the use of load balancing to obtain good results with this kind of algorithm and discuss the choice of the residual as an efficient load estimator.     

Revisiting the efficacy of weak consistencies:a study of forward checking

Dear editor, Arc consistency(AC)[1]is currently the most popular lo-cal consistency for solving constraint satisfaction problems(CSP).To solve CSPs more efficie...     

A decentralized and fault tolerant convergence detection algorithm for asynchronous iterative algorithms

This article presents an algorithm that performs a decentralized detection of the global convergence of parallel asynchronous iterative applications. This algorithm is fault tolerant. It runs a decentralized saving procedure which enables this algorithm, after a node’s crash, to replace the dead node by a new one which will continue the computing task from the last check point. Combined with the advantages of the asynchronous iteration model, this method allows us to compute very large scale problems using highly volatile parallel architectures like Peer-to-Peer and distributed clusters architectures. We also present the implementation of this algorithm in the JaceP2P platform which is dedicated to designing and executing parallel asynchronous iterative applications in volatile environments. Numerous experiments show the robustness and the efficiency of our algorithm.