Graph Algorithms in Distributed Systems

Classical graph problems, solved with only local information and message passing rather than a global view of the graph. Routing algorithms (distance-vector and link-state — the two paradigms every real routing protocol specializes) compute shortest paths without any node knowing the whole topology; graph traversal algorithms build a spanning tree or MST the same way; and distributed coloring algorithms assign colors using only local coordination, with the planar case admitting a much better bound. This is the same distance-vector/link-state material that underlies Internet and mesh-network routing, treated here in its abstract algorithmic form.

Outline (TODO — flesh out each)

• Routing algorithms — computing shortest path
• Distance vector routing
• Link-state routing
• Interval routing
• Graph traversal — spanning tree construction, Tarry’s algorithm
• Minimum spanning tree
• Graph coloring — a simple algorithm; planar graph coloring