title: Travelling Salesman and Map/Reduce: Abandon Channel
body: <p>This is an academic rather than practical question.  In the Traveling Salesman Problem, or any other which involves finding a minimum optimization ... if one were using a map/reduce approach it seems like there would be some value to having some means for the current minimum result to be broadcast to all of the computational nodes in some manner that allows them to abandon computations which exceed that.</p>
  
  <p>In other words if we map the problem out we'd like each node to know when to give up on a given partial result before it's complete but when it's already exceeded some other solution.</p>
  
  <p>One approach that comes immediately to mind would be if the reducer had a means to provide feedback to the mapper.  Consider if we had 100 nodes, and millions of paths being fed to them by the mapper.  If the reducer feeds the best result to the mapper than that value could be including as an argument along with each new path (problem subset).  In this approach the granularity is fairly rough ... the 100 nodes will each keep grinding away on their partition of the problem to completion and only get the new minimum with their next request from the mapper.  (For a small number of nodes and a huge number of problem partitions/subsets to work across this granularity would be inconsequential; also it's likely that one could apply heuristics to the sequence in which the possible routes or problem subsets are fed to the nodes to get a rapid convergence towards the optimum and thus minimize the amount of "wasted" computation performed by the nodes).</p>
  
  <p>Another approach that comes to mind would be for the nodes to be actively subscribed to some sort of channel, or multicast or even broadcast from which they could glean new minimums from their computational loop.  In that case they could immediately abandon a bad computation when notified of a better solution (by one of their peers).</p>
  
  <p>So, my questions are:</p>
  
  <ul>
  <li>Is this concept covered by any terms of art in relation to existing map/reduce discussions</li>
  <li>Do any of the current map/reduce frameworks provide features to support this sort of dynamic feedback?</li>
  <li>Is there some flaw with this idea ... some reason why it's stupid?</li>
  </ul>