Chapter 10
Graph Algorithms
10.1 Introduction
The topology of a distributed system is represented by a graph where the nodes represent processes and the links represent communication channels. Distributed algorithms for various graph theoretic problems have numerous applications in communication and networking. Here are some motivating examples.
The first example deals with routing in a communication network. When a message is sent from node i to a nonneighboring node j, the intermediate nodes route the message based on the information stored in the local routing table. This is called hop-by-hop or destination-based routing. An important problem is to compute these routing tables and maintain them, so that messages reach their destinations in ...
Get Distributed Systems, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
