Increasing Parallelism in Forward-backward Distributed Algorithm for Finding Strongly Connected Components of Directed Graphs

• Autorzy: Ryżko Dominik

Identyfikatory

DOI

10.26636/jtit.2024.3.1693

• Języki publikacji: EN

Abstrakty

EN

The paper proposes a modification of the existing distributed forward-backward algorithm for finding strongly connected components in directed graphs. The modification aims at improving the parallelism of the algorithm by increasing the branching factor while dividing the workload. Instead of randomly picking the pivot vertex, a heuristic technique is used which allows more sub-tasks to be generated, on average, for the subsequent step of the algorithm. The work describes suitable algorithm modifications and presents empirical results, proving suitability of the approach in question.

Słowa kluczowe

EN

distributed computation; graph algorithms; strongly connected components

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2024
• Tom: nr 3
• Strony: 30--35
• Opis fizyczny: Bibliogr. 32 poz., rys.

Twórcy

autor

Ryżko Dominik

• Warsaw University of Technology, Warsaw, Poland

• https://orcid.org/0000-0001-5632-0861

Bibliografia

• [1] B. Sandeep and A. Ferreira, "Complexity of Connected Components in Evolving Graphs and the Computation of Multicast Trees in Dynamic Networks", Second International Conference, ADHOC-NOW2003, Montreal, Canada, 2003.
• [2] S. Raghavan, "Twinless Strongly Connected Components", in: Perspectives in Operations Research, pp. 285-304, 2006.
• [3] W. McLendon III, B. Hendrickson, S.J. Plimpton, and L. Rauchwerger, "Finding Strongly Connected Components in Distributed Graphs", Journal of Parallel and Distributed Computing, vol. 65, no. 8, pp. 901-910, 2005.
• [4] H. Garavel, R. Mateescu, and I.M. Smarandache, "Parallel State Space Construction for Model-checking", Proc. of the 8th International SPIN Workshop on Model Checking of Software (SPIN’01), vol. 2057, pp. 200-216, 2001.
• [5] D. Ryzko, "Reasoning in Multi-agent Systems with Random Knowledge Distribution", in: Advances in Databases and Information Systems, pp. 310-317, 2012.
• [6] P. Cholewinski, "Reasoning with Stratified Default Theories", Proc. of Third International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’95), pp. 273-286, 1995.
• [7] V. Batagelj, "Efficient Algorithms for Citation Network Analysis", ArXiv, 2003.
• [8] Y. Kajikawa et al., "Creating an Academic Landscape of Sustainability Science: An Analysis of the Citation Network", Sustainability Science, vol. 2, pp. 221-231, 2007.
• [9] H. Yang et al., "Strongly Connected Components Based Efficient PPR Algorithms", Jisuanji Xuebao/Chinese Journal of Computers, vol. 40, pp. 584-600, 2017.
• [10] N.P. Hummon and P. Doreian, "Computational Methods for Social Network Analysis", Social Networks, vol. 12, no. 4, pp. 273-288, 1990.
• [11] R. Tarjan, "Depth First Search and Linear Graph Algorithms", SIAM Journal on Computing, vol. 1, no. 2, pp. 146-160, 1972.
• [12] H.N. Gabow, "Path-based Depth First Search Strong and Biconnected Components", Information Processing Letters, vol. 74, no. 3-4, pp. 107-114, 2000.
• [13] E. Renault, A. Duret-Lutz, F. Kordon, and D. Poitrenaud, "Parallel Explicit Model Checking for Generalized Buchi Automata", in: Tools and Algorithms for the Construction and Analysis of Systems, pp. 613-627, 2015.
• [14] H. Gazit and G.L. Miller, "An Improved Parallel Algorithm that Computes the BFS Numbering of a Directed Graph", Information Processing Letters, vol. 28, no. 2, pp. 61-65, 1988.
• [15] R. Cole and U. Vishkin, "Faster Optimal Parallel Prefix Sums and List Ranking", Information and Computation, vol. 81, no. 3, pp. 334-352, 1989.
• [16] J. Barnat, J. Chaloupka, and J. van de Pol, "Improved Distributed Algorithms for SCC Decomposition", Electronic Notes in Theoretical Computer Science, vol. 198, no. 1, pp. 63-77, 2008.
• [17] W. Schudy, "Randomized Algorithms for Graph Problems", 2007.
• [18] W. Schudy, "Finding Strongly Connected Components in Parallel Using O(log2n) Reachability Queries", Proceedings of the Twentieth Annual Symposium on Parallelism in Algorithms and Architectures, pp. 146-151, 2008.
• [19] J. Jaiganesh and M. Burtscher, "A High-performance Connected Components Implementation for GPUs", Proceedings of the 27th International Symposium on High-Performance Parallel and Distributed Computing, pp. 92-104, 2018.
• [20] T. Ben-Nun, M. Sutton, S. Pai, and K. Pingali, "Groute: An Asynchronous Multi-GPU Programming Model for Irregular Computations", Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 235-248, 2017.
• [21] L. Fleischer, B. Hendrickson, and A. Pinar, "On Identifying Strongly Connected Components in Parallel", Proceedings of Parallel and Distributed Processing Symposium, pp. 505-511, 2000.
• [22] S. Hong, N.C. Rodia, and K. Olukotun, "On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-world Graphs", Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, 2013.
• [23] J. Barnat and P. Moravec, "Parallel Algorithms for Finding SCCs in Implicitly Given Graphs", in: Formal Methods: Applications and Technology, pp. 316-330, 2007.
• [24] Y. Ji, H. Liu, and H.H. Huang, "iSpan: Parallel Identification of Strongly Connected Components with Spanning Trees", SC18: International Conference for High Performance Computing, Networking, Storage and Analysis, Dallas, USA, 2022.
• [25] D. Niewenhuis and A.L. Varbanescu, "Efficient Trimming for Strongly Connected Components Calculation", Proceedings of the 19th ACM International Conference on Computing Frontiers, pp. 131-140, 2022.
• [26] J. Barnat, J. Chaloupka, and J. van de Pol, "Distributed Algorithms for SCC Decomposition", Journal of Logic and Computation, vol. 21, no. 1, pp. 23-44, 2011.
• [27] S. Orzan, "On Distributed Verification and Verified Distribution", Ph.D. thesis, Free University of Amsterdam, 2004 (https://research.vu.nl/en/publications/on-distributed-verification-and-verified-distribution).
• [28] P. Erdos and A. Renyi, "On Random Graphs I", Publicationes Mathematicae Debrecen, vol. 6, pp. 290-297, 1959
• [29] T. Tobita and H. Kasahara, "A Standard Task Graph Set for Fair Evaluation of Multiprocessor Scheduling Algorithms", Journal of Scheduling, vol. 5, no. 5, pp. 379-394, 2002.
• [30] R.P. Dick, D.L. Rhodes, and W. Wolf, "TGFF: Task Graphs for Free", Proceedings of the 6th International Workshop on Hardware/Software Codesign, pp. 97-101, 1998.
• [31] P. Winkler, "Random Orders", Order, vol. 1, pp. 317-331, 1985.
• [32] Akka, (http://akka.io).