The design of distributed algorithms is easier if we assume that the underlying network is synchronous rather than asynchronous. A prime example is that of computing a breadth-first search (BFS) tree in a network. In this chapter, we assume that the network has *N* nodes, *E* edges, and its diameter is *D*. Assume that we are given a distinguished node *v* and our job is to build a breadth-first search tree rooted at *v*. A synchronous algorithm for this task is quite simple. We build the tree level by level. The node *v* is initially at level 0. A node at level *i* is required to send messages to its neighbors at pulse *i*. A process that receives one or more of these messages, and does not have a level number assigned yet, chooses the source of one of these messages as its parent and assigns itself level number *i* + 1. It is clear that if the graph is connected, then every node will have its level number assigned in at most *D* pulses assuming that any message sent at pulse *i* is received at pulse *i* + 1.

What if the underlying network is not synchronous? The corresponding problem on an asynchronous network is more difficult. This motivates methods by which a synchronous network can be simulated by an asynchronous network. We show that, in the absence of failures, this is indeed possible using a mechanism called a *synchronizer*. To simulate the synchronous algorithm on an asynchronous network, all we need is to use one of the synchronizers discussed in this ...

Start Free Trial

No credit card required