Internet-based TSP computation with Javelin++

Javelin++ is a Java-based infrastructure for Internet computing. This paper presents an extension of Javelin++ to solve the traveling salesman problem (TSP), which is a computationally complex combinatorial problem. Javelin++´s piecework computational model is extended to support a branch-and-bound model that is applied to the TSP computation. This extension implements the pipelined RAM model of cache consistency. Like Javelin++´s piecework computational model, the underlying architecture of this branch-and bound model is based on clients and hosts coordinated by brokers. The paper presents: a branch-and-bound computational model, the implementation of a scalable task scheduler using distributed work-stealing, the design and implementation of fault tolerance and load balancing via eager scheduling, and the results of performance experiments which appear promising. The paper focuses on a scalable implementation of branch-and-bound (especially the “bound” part) on internetworked computers. Javelin++´s seamless integration of distributed work-stealing, bound propagation, and lazy, lightweight, eager scheduling is the principle contribution of this paper