# 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?

## 1.1. Solution

- In the alpha synchronizer, we may have many processes in their critical section simultaneously. If I am at distance k from you, I can be up to k rounds ahead of you. So by carefully arranging the process ids in a high-diameter network (e.g. on a line), we can have a constant fraction of the processes enter the critical section at once.
- In the beta synchronizer, synchronization is global: no process can enter round i+1 until ever process has signaled it is done with round i. So in this case we still get mutual exclusion.

# 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?

## 2.1. Solution

Here is the revised `Scan` procedure:

procedure Scan(): curr_seq ← curr_seq + 1 for j ← 0 to n-1: h ← memory[j] view[j] ← value in h with largest seq < curr_seq

With a single scanner, this is equivalent to the original RST algorithm. The argument is that the original RST algorithm satisfies an invariant that the `(seq, value)` pair with the largest `seq` less than `curr_seq` is always found in either `memory[j].high` or `memory[j].low` (proof: first show that in RST, `memory[j].low` is always ≤ `memory[j].high`, then show that `memory[j].high` is copied to `memory[j].low` only if `memory[j].high.seq < curr_seq`, implying that the new `memory[j].low` now has the largest `seq` less than `curr_seq`). So taking the most recent value less than `seq` in memory[j] in the revised algorithm is equivalent to taking the most recent value less than `seq` in RST, and the new algorithm works using the same proof that RST works.

With multiple scanners, the new algorithm fails because a slow scanner could read an old value of `curr_seq`, add 1 to it, sleep for a long time, and wipe out much more recent sequence numbers, messing up the histories.