The following questions deal with consistency models, and the
relationship between locks and consistency.

We know that acquire/release pairs on a lock are strictly paired and
strictly ordered.  The acquire and release for each pair are always
executed by the same process (or thread, or node).  Between the
acquire and the associated release, we say that process owns or holds
the lock.  Let us call the segment of time between an acquire and the
release an "interval".  Since the acquire/release pairs on any given
lock are strictly ordered, this means means that we can number assign
sequence numbers to the intervals for each lock.

Suppose that we capture the relationship between locks and ordering by
adding a fourth axiom to Lamport's happened-before predicate: if event
e1 is a lock release, and event e2 a subsequent acquire for that lock
(i.e., its interval has a higher sequence number), then e1
happened-before e2.

1. Consider the following two code snippets.  All variables have
initial value zero.

A: {x = 1; r0 = y}
B: {y =1; r1 = x}

Suppose A and B are launched to run, each in different process running
over shared memory/storage.  Is it possible for them to complete with
r0 == 0, r1 == 0?  Prove that this result is not possible under a
sequential consistency model.

2. Show that two transactions can never have a sequentially consistent
execution in which both access the same variable, but the accesses are
concurrent.

(a) Assume that the transactions are "single-shot" transactions as in
the Birrell/Wobber/Jones paper.

(b) What if transactions use locking with multiple locks?