Input : ϒ(S,dmin,HD(S)), Tmax and K
Output: A closest string to S with its maximum Hamming distance to S
for 0 ≤ t ≤ Tmax do Runϒ(S,dmin,HD(S)) in Minion if Solved?(ϒ(S,dmin,HD(S))) **then**
Return CS and d, and halt all computation else d*high* ← the best d found so far ϒ(S,dmin,HD(S)) ← ϒ(S,dmin,d*high*) plus constraints ruling out search already performed end end do in parallel for dmin ≤ dlow < d*high* do DistSolve(ϒ
∗(S,dmin,dlow), Tmax, K)
if Solved?(ϒ
∗(S,dmin,dlow)) **then**
Return CS and d = dlow, and halt all computation else Update all (sub-)instances with new lower bound dlow +1 end end for 2 ≤ k ≤ K +1 do DistSolve(ϒk(S,dmin,dlow), Tmax, K)
if Solved?(ϒk(S,dmin,dhigh)) with dnew < d*high* **then**
if dnew = d*high* −1 **then** Return CS and d = dnew, and halt all computation else Update all (sub-)instances with upper bound dhigh = dnew end end end if not Solved?( ϒk(S,dmin,dhigh) ∀ k) ∧ not Solved?(any fixed dlow *instance*) **then**
Return current d*high* as d, and the string found that achieved distance d*high* as CS
end Algorithm 2: Solve the CSP ϒ(S,dmin,HD(S)) by distributing search for high and low distances heuristic as a single process. Our empirical evaluation in Section 2.2 indicates that nearly always this process will highly efficiently lower the upper bound for the problem. Once we have a reasonable upper bound, we start searching for the optimal distance both above and below. From above, we carry on optimising as before, but we use the recursive DistSolve algorithm to distribute. From below we create instances each having a fixed distance, the idea being to exhaustively rule out any closest strings at these distances. These instances are run on the computational nodes at the same time as the optimisation subproblems. If at any stage we obtain a candidate closest string at a distance for which all lower distances have been ruled out, then this is our solution. This can happen both from above and below.

As mentioned in Section 3.1.1, we expect a super-linear speedup by performing a root node consistency check for each sub-instance. By keeping track of the best distance obtained so far during search from above, and of any lower distances for which no solution has been found, we expect to obtain a further super-linear speedup in the majority of instances. A large part of the search tree is pruned by updating all instances (either waiting for input to a node, or currently being processed by a node) with improved distance bounds as they become available.