{"ID":2880041,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.14319","arxiv_id":"2508.14319","title":"SSSP-Del: Fully Dynamic Distributed Algorithm for Single-Source Shortest Path","abstract":"Modern graphs are both large and dynamic, presenting significant challenges for fundamental queries, such as the Single-Source Shortest Path (SSSP) problem. Naively recomputing the SSSP tree after each topology change is prohibitively expensive, causing on-demand computation to suffer from high latency. Existing dynamic SSSP algorithms often cannot simultaneously handle both edge additions and deletions, operate in distributed memory, and provide low-latency query results. To address these challenges, this paper presents SSSP-Del, a new vertex-centric, asynchronous, and fully distributed algorithm for dynamic SSSP. Operating in a shared-nothing architecture, our algorithm processes streams of both edge insertions and deletions. We conduct a comprehensive evaluation on large real-world and synthetic graphs with millions of vertices, and provide a thorough analysis by evaluating result latency, solution stability, and throughput.","short_abstract":"Modern graphs are both large and dynamic, presenting significant challenges for fundamental queries, such as the Single-Source Shortest Path (SSSP) problem. Naively recomputing the SSSP tree after each topology change is prohibitively expensive, causing on-demand computation to suffer from high latency. Existing dynami...","url_abs":"https://arxiv.org/abs/2508.14319","url_pdf":"https://arxiv.org/pdf/2508.14319v2","authors":"[\"Parshan Javanrood\",\"Matei Ripeanu\"]","published":"2025-08-20T00:07:30Z","proceeding":"cs.DC","tasks":"[\"cs.DC\"]","methods":"[]","has_code":false}