Chapter 10 Synchronization

So far, we have mainly studied synchronous algorithms. Generally, asynchronous algorithms are more difficult to obtain. Also it is substantially harder to reason about asynchronous algorithms than about synchronous ones. For instance, computing a BFS tree (Chapter 3) 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 algorith