From a high-level point of view a constraint solver takes a constraint space, generates a tree of narrowings of the space and runs some search algorithm on the tree. Core.logic complects the generation of this tree and the search algorithm by representing the search space as a lazy stream of the leaves of the tree. By explicitly representing the search tree we get new search algorithms, optional fair conjunction and parallel search via fork-join.
More detail: http://scattered-thoughts.net/blog/2012/12/19/search-trees-and-core-dot-logic/
Github fork: https://github.com/clojure/core.logic/pull/13
Attached is a cleaned-up patch against d68e3400472c5f745e4c13d64433459e11ba4871