Performance Evaluation of Communication-Efficient Techniques for Distributed Graph Algorithms

Abstract

Distributed graph algorithms are essential for processing large-scale networks where graph data and computation are spread over a number of interconnected machines. Distributed Processing offers scalability and parallelism but communication between machines can be a serious performance handicap. This paper investigates communication efficient distributed graph algorithms and explores ways to lower communication overhead while preserving correctness and efficiency of the algorithm. Special emphasis is placed on communication models in which the size of individual messages and the number of rounds for each communication have a direct impact on the performance of the algorithms. The paper summarizes methods that are suitable for communicating efficiently to solve common graph-related tasks such as breadth-first search, shorted paths, and minimum spanning trees, connectivity, and graph analytics. Local computation, message aggregation, selective communication, push–pull communication, graph partitioning, and shortcut methods are among the techniques mentioned. Algorithms are also evaluated by the paper based on communication complexity, round complexity, computational workload, and scalability, as well. Challenges and future research directions are outlined, such as adaptive communication strategies, dynamic graphs, heterogeneous networks and intelligent approaches for avoiding unnecessary data exchange. The study shows that the design of communication-aware algorithms is crucial for scalable and efficient distributed graph processing.