Chapter 10 Synchronization

So far, we have mainly studied synchronous algorithms. Generally, asynchro-nous algorithms are more difficult to obtain. Also it is substantially harder to reason about asynchronous algorithms than about synchronous ones. For in-stance, computing a BFS tree (Chapter 2) efficiently requires much more work in an asynchronous system. However, many real systems are not synchronous, and we therefore have to design asynchronous algorithms. In this chapter, we will look at general simulation techniques, called synchronizers, that allow running synchronous algorithms in asynchronous environments. 10.1 Basics A synchronizer generates sequences of clock pulses at each node of the network satisfying the condition given by the following definition. Definition 10.1 (valid clock pulse). We call a clock pulse generated at a node v valid if it is generated after v received all the messages of the synchronous algorithm sent to v by its neighbors in the previous pulses. Given a mechanism that generates the clock pulses, a synchronous algorithm is turned into an asynchronous algorithm in an obvious way: As soon as the ith clock pulse is generated at node v, v performs all the actions (local computations and sending of messages) of round i of the synchronous algorithm. Theorem 10.2. If all generated clock pulses are valid according to Definition 10.1, the above method provides an asynchronous algorithm that behaves exactly the same way as the given synchronous algorithm. Proof. When the ith pulse is generated at a node v, v has sent and received exactly the same messages and performed the same local computations as in the first i − 1 rounds of the synchronous algorithm. The main problem when generating the clock pulses at a node v is that v can-not know what messages its neighbors are sending to it in a given synchronous round. Because there are no bounds on link delays, v cannot simply wait “long enough ” before generating the next pulse. In order satisfy Definition 10.1, nodes have to send additional messages for the purpose of synchronization. The tota