1. Round-robin mutual exclusion
Consider the following algorithm for mutual exclusion in a synchronous message-passing system with n processes, communicating via an arbitrary (but connected) network. Group the synchronous rounds into phases of 2n rounds 0..2n-1, and have each process i=0..n-1 enter its critical section at the start of round 2i and leave at the start of round 2i+1 within each phase. Clearly no two processes are ever in the critical section at the same time.
- What happens to this algorithm if we run it in an asynchronous system using the alpha synchronizer?
- What happens to this algorithm if we run it in an asynchronous system using the beta synchronizer?
2. Atomic snapshots with enormous registers
Suppose that we modify the single-scanner snapshot of Riany et al. (see AtomicSnapshots) so that each updater, instead of storing high and low fields in each memory cell, stores a list of all (seq, value) pairs it has ever written. So the new Update procedure would look like this:
procedure Update(value): seq ← curr_seq memory[i].high ← append(memory[i].high, (value, seq))
Modify the Scan procedure to work with this Update procedure and argue that it works with a single scanner.
Does your modified Scan procedure produce linearizable snapshots with multiple scanners? Why or why not?