implicit at each node, and

2. Minion is searching 250,000 - 300,000 nodes per second in addition to the work involved in identifying search sub-trees that need not be explored.

## 3 Distributed And Hybrid Computing Strategies

Input : A CSP ϒ, a cutoff period Tmax and a branching factor K
Output: Either the first solution, or a guarantee that there are no solutions while not Solved?(ϒ) do Send ϒ to a node Run solver with input ϒ for 0 ≤ t ≤ Tmax if Solved?(ϒ) **then**
Return solution else ϒ ← ϒ with new constraints ruling out search already performed Split ϒ into K subproblems ϒ1,ϒ2*,...,*ϒK
do in parallel

![0_image_0.png](0_image_0.png)

Algorithm 1: A recursive distributed algorithm to solve any CSP

## 3.1 Distributed Csp

Given the inherently exponential increase in search effort involved in providing a certificate for an optimal closest string distance by ruling out any closest strings with with lower distance, the exact solution of large-scale problems is not expected to be tractable using purely sequential search. In this Section we describe algorithms that distribute search across multiple compute nodes. These algorithms will solve closest string problems either on a cluster (a local group of homogeneous nodes), a grid (a more loosely coupled, heterogeneous and geographically dispersed set of nodes), or a cloud (a set of an unknown number of nodes in unknown locations, each having unknown architecture and resource). Generally speaking, a cluster is more controllable but smaller than a cloud, with a grid being either the best or worst of both worlds, depending on one's point of view. For our purposes we do not require any communication across nodes (although computational efficiencies could be obtained if that were the case),
and can therefore treat the three distributed paradigms as a single approach. The only disadvantage to using a cloud is that empirical evaluation is often impossible since the times reported in virtual machines are not reliable. This is because clocks of virtual machines can be slowed down or sped up by the VM management software. We therefore prototype our computational methodology on a cluster, and, when satisfied that it is efficient, deploy using a cloud to take advantage of the very large number of nodes available.

Algorithm 1 gives the basic structure of our distributed search. The predicate Solved? returns true whenever the input CSP finds the first solution or finishes searching the entire tree without finding a