Distributed Algorithms

Chapter 4 Algorithms in General Synchronous Networks

In Chapter 3, we presented algorithms and lower bounds for the problem of leader election in very simple synchronous networks—unidirectional and bidirectional rings. In this chapter, we consider a larger collection of problems in a larger class of synchronous networks. In particular, we present algorithms for leader election, breadth-first search (BFS), finding shortest paths, finding a minimum spanning tree (MST), and finding a maximal independent set (MIS), in networks based on arbitrary graphs and digraphs.

The problem of leader election arises when a process must be selected to “take charge” of a network computation. The problems of breadth-first search, finding shortest paths, and finding ...