Controlled constraint sharing in parallel problem solvers is described. In embodiments, constraint sharing in a problem solver is controlled by comparing a total number of shared constraints obtained in a time interval to a target, and regulating the subsequent number of shared constraints obtained from other problem solvers accordingly. Embodiments describe how the regulation of the subsequent number of shared constraints can be achieved by controlling the size of constraints shared by other problem solvers. Embodiments describe how an additive increase/multiplicative decrease algorithm can be used to determine the size of constraints to be exchanged. Embodiments also describe how the utility of the shared constraints can be determined, and used to control the size of constraints shared by other problem solvers. In embodiments, the problem solver is a Boolean satisfiability problem solver.