Large Scale Network-Centric Distributed Systems

4

Large-Scale P2P-Inspired Problem-Solving: A Formal and Experimental Study

Mathieu Djamaï, Bilel Derbel, and Nouredine Melab

Contents

4.1 Introduction

4.1.1 Motivations

4.1.2 Contribution and Results

4.1.3 Related Works

4.1.4 Outline

4.2 Background

4.3 A Pure Peer-to-Peer B&B Approach

4.3.1 Preliminaries

4.3.2 Information Sharing and Work Distribution

4.3.2.1 Best Solution Sharing Mechanism

4.3.2.2 Work Sharing

4.3.2.3 Load Balancing

4.3.3 Distributed Termination Detection

4.3.3.1 Basic Observations

4.3.3.2 Technical Details Sketch

4.3.4 Asynchrony Issues

4.4 Complexity Issues

4.5 Experimental Results

4.5.1 Experimental Testbed

4.5.2 Experiments on Large-Scale Networks

4.5.2.1 Parallel Efficiency

4.5.2.2 Network Congestion and Simulation Scenarios

4.5.2.3 Message Overhead

4.5.2.4 Search Space Exploration Speed-Up

4.5.2.5 Combinatorial Speed-Up

4.5.3 Lower Scales' Results

4.6 Conclusion

Acknowledgment

References

4.1 Introduction

4.1.1 Motivations

Today, more and more computational resources are needed to tackle real-life combinatorial optimization problems, for example, in physics, bioinformatics, and graphical simulation. Indeed, these kinds of problems require a huge amount of computational resources to be solved in an optimal way. However, even having huge computational power at hand, it is not straightforward to design efficient large-scale software platforms and algorithms that allow us to fully take advantage of these resources available from both large-scale computational ...