Graphs are powerful mathematical objects that provide the right level of abstraction for modeling and solving many real-world problems. In vertex-centric distributed computing, computation nodes communicate via network links, which can naturally be represented as vertices and edges of a graph. Algorithms can then be designed to run on each computation node, enabling all nodes to collaboratively solve a given problem.

In this talk, I will introduce a line of research in theoretical computer science focused on solving graph problems in distributed networks. A classical example is the packet routing problem, where all computation nodes simultaneously route packets to their desired destinations while avoiding congestion. In particular, I will present an algorithm that solves the packet routing problem on expander graphs — networks that are highly connected yet sufficiently sparse.

This talk is based on joint work with Hsin-Hao Su and Yi-Jun Chang.