@inbook {IOPORT.05498221,
    author       = {Hyv\"arinen, Antti E.J. and Junttila, Tommi and Niemel\"a, Ilkka},
    title        = {Strategies for solving SAT in grids by randomized search.},
    year         = {2008},
    booktitle    = {Intelligent computer mathematics. 9th international conference, AISC 2008, 15th symposium, Calculemus 2008, 7th international conference, MKM 2008, Birmingham, UK, July 28--August 1, 2008. Proceedings},
    isbn         = {978-3-540-85109-7},
    pages        = {125-140},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/978-3-540-85110-3_11},
    abstract     = {Summary: Grid computing offers a promising approach to solving challenging computational problems in an environment consisting of a large number of easily accessible resources. In this paper we develop strategies for solving collections of hard instances of the propositional satisfiability problem (SAT) with a randomized SAT solver run in a Grid. We study alternative strategies by using a simulation framework which is composed of (i) a grid model capturing the communication and management delays, and (ii) run-time distributions of a randomized solver, obtained by running a state-of-the-art SAT solver on a collection of hard instances. The results are experimentally validated in a production level Grid. When solving a single hard SAT instance, the results show that in practice only a relatively small amount of parallelism can be efficiently used; the speedup obtained by increasing parallelism thereafter is negligible. This observation leads to a novel strategy of using grid to solve collections of hard instances. Instead of solving instances one-by-one, the strategy aims at decreasing the overall solution time by applying an alternating distribution schedule.},
    identifier   = {05498221},
}