Distributed Algorithms

Chapter 15 Basic Asynchronous Network Algorithms

In this chapter, we describe a collection of algorithms for solving some basic problems—leader election, constructing an arbitrary spanning tree, broadcast and convergecast, breadth-first search, finding shortest paths, and constructing a minimum spanning tree—in the asynchronous network model with reliable FIFO send/receive channels. The problems are, for the most part, the same ones considered in the synchronous network model in Chapter 4. As before, these problems are motivated by the need to select a process to take charge of a network computation and by the need to build structures suitable for supporting efficient communication. We do not consider faults in this chapter.

All the algorithms ...