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.

1. What happens to this algorithm if we run it in an asynchronous system using the alpha synchronizer?
2. 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))

1. Modify the Scan procedure to work with this Update procedure and argue that it works with a single scanner.

2. Does your modified Scan procedure produce linearizable snapshots with multiple scanners? Why or why not?