13 - Modelling and analysis of Fischer's algorithm

Summary

Introduction

Mutual exclusion algorithms, like those we discussed in Chapter 7, have an abstract behaviour described by the following pseudocode:

1. while true do

2. begin

1. remainder region

2. trying region

3. critical section

4. exit region

1. end

It is supposed that such algorithms satisfy the following two properties.

• Mutual exclusion No two processes are in their critical sections at the same time.

• Deadlock freedom If some process is in its trying region then eventually some process is in its critical section. (Note that the process in the critical section might be different from the one initially in its trying region.) Moreover, if a process is in its exit region then that process will eventually enter its remainder region.

As stated in Lynch and Shavit (1992), the known asynchronous mutual exclusion algorithms for n processes require O(n) read and write registers and O(n) operations to access the critical section. These bounds make them rather impractical for large-scale applications, where the number of processes could be very large. This raises the question whether it is possible to achieve mutual exclusion in asynchronous systems consisting of n processes by using a smaller number of shared registers and/or fewer than O(n) operations to access the critical section. Unfortunately, this is impossible for ‘classic reactive systems’ in an asynchronous setting. In fact, Burns and Lynch (1980, 1993) showed the following theorem.