Distributed Algorithms

Chapter 10 Mutual Exclusion

In this chapter, we begin the study of asynchronous algorithms. Asynchronous algorithms are generally quite different from synchronous algorithms, since they must cope with the uncertainty imposed by asynchrony as well as the uncertainty caused by distribution. In asynchronous networks, for example, process steps and message deliveries do not necessarily take place in lock-step synchrony; rather, they may happen in an arbitrary order.

Instead of moving immediately to the study of asynchronous network algorithms, we first study algorithms in the asynchronous shared memory setting. The main reason we do this is that the setting is somewhat simpler. But also, as you will see in Chapter 17, there are close connections ...