USING BOINC DESKTOP GRID TO SOLVE LARGE SCALE SAT PROBLEMS

Mikhail Posypkin; Alexander Semenov; Oleg Zaikin

doi:10.7494/csci.2012.13.1.25

Authors

Mikhail Posypkin Institute for Systems Analysis of RAS, Moscow
Alexander Semenov Institute for System Dynamics and Control Theory of SB RAS, Irkutsk
Oleg Zaikin Institute for System Dynamics and Control Theory of SB RAS, Irkutsk

DOI:

https://doi.org/10.7494/csci.2012.13.1.25

Keywords:

desktop grid, Boolean satisfiability problem (SAT), volunteer computing, BOINC

Abstract

Many practically important combinatorial problems can be efficiently reduced
to a problem of Boolean satisfiability (SAT). Therefore, the implementation of
distributed algorithms for solving SAT problems is of great importance. In this
article we describe a technology for organizing desktop grid, which is meant
for solving SAT problems. This technology was implemented in the form of
a volunteer computing project SAT@home based on a popular BOINC platform.

Downloads

Download data is not yet available.

Author Biography

Mikhail Posypkin, Institute for Systems Analysis of RAS, Moscow

Many practically important combinatorial problems can be efficiently reduced
to a problem of Boolean satisfiability (SAT). Therefore, the implementation of
distributed algorithms for solving SAT problems is of great importance. In this
article we describe a technology for organizing desktop grid, which is meant
for solving SAT problems. This technology was implemented in the form of
a volunteer computing project SAT@home based on a popular BOINC platform.