Is there any parallel algorithms or approximation algorithms for 3SAT?
There are some approaches to distributed constraint satisfaction problems. Check out this paper.
Majority of them are embarrassingly parallel, where each node chooses a starting point, implements a serial solver etc. The smart bit comes in, in communicating dead end paths to other nodes.