9.11

(a) An operation of a data type is called an accessor if, informally speaking, it does not change the "state" of the object. Make a formal definition of accessor using the notion of legal sequences of operations.

(b) Consider a shared object (data type) specification that satisfies the follow- ing property. There exists a sequence p of operations, two operations aop and aop that are both of type dop, an accessor, and there exists an operation op such that (1) p aop and p op aop are legal, but (2) p aop and p op aop are not legal. Suppose at least two processors can perform operations of type aop and a third can perform op. Prove that in any linearizable implementation of this data type, taop

(c) What does this result imply about the worst-case time for linearizable implementations of read/write registers and of augmented stacks and queues? (An augmented stack or queue provides an additional peek operation that returns the value at the top of the stack or head of the queue but does not change the data structure.)