O'Reilly logo

Distributed Algorithms by Nancy A. Lynch

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required