Distributed Algorithms

Chapter 24 Mutual Exclusion with Partial Synchrony

In this chapter, we visit the mutual exclusion problem for the third time, this time in the partially synchronous shared memory setting. We present only very basic results: simple timing-based algorithms and their analysis, and simple impossibility results.

24.1 The Problem

The setting is very much the same as in Chapter 10—a shared memory system with n ports, interacting with users U₁,…, U_n. The external interface, consisting of try_i, crit_i, exit_i, and remi_i actions, is exactly the same as before. This time, however, the users and the shared memory system are modelled as MMT automata, as defined in Section 23.1, rather than as I/O automata. Figure 10.4 can still be used to represent the architecture ...