𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Parallel propositional satisfiability checking with distributed dynamic learning

✍ Scribed by Wolfgang Blochinger; Carsten Sinz; Wolfgang Küchlin

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
897 KB
Volume
29
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

✦ Synopsis

We address the parallelization and distributed execution of an algorithm from the area of symbolic computation: propositional satisfiability (SAT) checking with dynamic learning. Our parallel programming models are strict multithreading for the core SAT checking procedure, complemented by mobile agents realizing a distributed dynamic learning process. Individual threads treat dynamically created subproblems, while mobile agents collect and distribute pertinent knowledge obtained during the learning process. The parallel algorithm runs on top of our parallel system platform Distributed Object-Oriented Threads System, which provides support for our parallel programming models in highly heterogeneous distributed systems. We present performance measurements evaluating the performance gains by our approach in different application domains with practical significance.

📜 SIMILAR VOLUMES

Model checking propositional dynamic log
Model checking propositional dynamic logic with all extras
✍ Martin Lange 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 116 KB

This paper presents a model checking algorithm for Propositional Dynamic Logic (PDL) with looping, repeat, test, intersection, converse, program complementation as well as context-free programs. The algorithm shows that the model checking problem for PDL remains PTIME-complete in the presence of all

Parallel Satisfiability Test with Synchr
Parallel Satisfiability Test with Synchronous Simulated Annealing on Distributed-Memory Multiprocessor
✍ Andrew Sohn 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 440 KB

Solving the hard Satisfiability Problem is time consuming even for modest-sized problem instances. Solving the Random L-SAT Problem is especially difficult due to the ratio of clauses to variables. This report presents a practical approach to solving the Random L-SAT Problem on a large-scale distrib