2011 · 10 citations · 16 references
ComputingComputer ScienceComputer SystemsDistributed SystemsParallel AlgorithmsParallel ComputingDistributed AlgorithmsDistributed ComputingLoad BalancingPeer-to-peer NetworksPeer-to-peer SystemsScalable Algorithm DesignDynamic Load BalancingLoad Balancing AlgorithmsNp-complete ProblemsParallel Branch And BoundPeer-to-peer ArchitecturesPeer-to-peer ComputingPeer-to-peer Network ArchitectureTermination Detection
The state-of-the-art large scale approach for solving NP-hard permutation-based problems using parallel Branch-and-Bound (B&B) techniques is based on a Master-Slave model which is known to be limited in terms of scalability. In this paper, we present a new Peer-to-Peer (P2P) approach that can handle a huge amount of computational resources in a fully distributed way, that is without the need of any centralized coordinator. To achieve that, we propose simple and efficient fully distributed algorithms dealing with major parallel B&B issues such as work sharing, dynamic load balancing and termination detection. We argue that our P2P approach has a scalability which is exponentially better in theory compared to the Master-Slave technique while having a negligible communication overhead in a worst case-scenario, namely poly-logarithmic. The approach has been implemented and experimented using the Grid'5000 nation-wide French grid. Through extensive simulations involving up to 150 000 peers, we show that, compared to the state-of-the-art Master-Slave technique, our P2P approach enables (i) to improve the parallel efficiency up to a ratio of 6 to 1, (ii) to significantly speed up the B&B search process, namely by up to 7 factor in terms of number of solutions explored in the search space and, (iii) to keep the communication overhead relatively low, namely by a factor of at most 11 without penalizing the search process.
16
Benchmarks for basic scheduling problems
Éric D. Taillard · European Journal of Operational Research · 1993 · 2.4K citations
Complexity of network synchronization
Baruch Awerbuch · Journal of the ACM · 1985 · 691 citations · Full text