JA-BE-JA: A Distributed Algorithm for Balanced Graph Partitioning
2013 (English)In: 7th International Conference on Self-Adaptive and Self-Organizing Systems (SASO), 2013 IEEE, IEEE conference proceedings, 2013, 51-60 p.Conference paper (Refereed)
Balanced graph partitioning is a well known NP-complete problem with a wide range of applications. These applications include many large-scale distributed problems including the optimal storage of large sets of graph-structured data over several hosts-A key problem in today's Cloud infrastructure. However, in very large-scale distributed scenarios, state-of-the-Art algorithms are not directly applicable, because they typically involve frequent global operations over the entire graph. In this paper, we propose a fully distributed algorithm, called JA-BE-JA, that uses local search and simulated annealing techniques for graph partitioning. The algorithm is massively parallel: there is no central coordination, each node is processed independently, and only the direct neighbors of the node, and a small subset of random nodes in the graph need to be known locally. Strict synchronization is not required. These features allow JA-BE-JA to be easily adapted to any distributed graph-processing system from data centers to fully distributed networks. We perform a thorough experimental analysis, which shows that the minimal edge-cut value achieved by JA-BE-JA is comparable to state-of-the-Art centralized algorithms such as METIS. In particular, on large social networks JA-BEJA outperforms METIS, which makes JA-BE-JA-A bottom-up, self-organizing algorithm-A highly competitive practical solution for graph partitioning.
Place, publisher, year, edition, pages
IEEE conference proceedings, 2013. 51-60 p.
, International Conference on Self-Adaptive and Self-Organizing Systems, ISSN 1949-3673
distributed algorithm, graph partitioning, load balancing, simulated annealing
Engineering and Technology
IdentifiersURN: urn:nbn:se:kth:diva-134801DOI: 10.1109/SASO.2013.13ISI: 000335222500006ScopusID: 2-s2.0-84893207551ISBN: 978-076955129-6OAI: oai:DiVA.org:kth-134801DiVA: diva2:668109
SASO 2013, Seventh IEEE International Conference on Self-Adaptive and Self-Organizing Systems, Philadelphia, USA; September 9-13, 2013
QC 201312182013-11-282013-11-282014-06-03Bibliographically approved