Abstract

The computation of Single-Source Shortest Paths (SSSP) is a fundamental problem in distributed
networks. This thesis explores efficient SSSP solutions within the synchronous CONGEST
model, where communication occurs in rounds in which each node can send O(log n) information to
each of its neighbors, where n is the size of the network. We focus on Elkin’s algorithm, notable for
being the first algorithm to achieve sub-linear round complexity for the problem. This work makes
several contributions: we clarify many details in the implementation of Elkin’s algorithm, enhance
its performance using pipelining techniques, and introduce two novel variants, Elkin-R (probabilistic
virtual node selection) and Elkin-D (distance-based selection). Through extensive simulations on
various network topologies, we compare these algorithms against Bellman-Ford based on the number
of rounds, message count, and clock time. Our findings reveal that specific configurations of
the Elkin variants consistently reduce message overhead compared to Bellman-Ford. Importantly,
for larger or denser graphs, these variants can also surpass Bellman-Ford in round complexity and
overall computation time, demonstrating their potential for practical distributed SSSP computation.