9.10 This exercise asks you to generalize the proof of Theorem 9.8 that twrite

(a) Consider a shared object (data type) specification with the following prop- erty. There exists a sequence p of operations and two operations op and op that are both of type op such that (1) p op op and p op op' are both legal and (2) there exists a sequence of operations such that p op opy is legal but p op op is not. Suppose at least two processors can perform operations of type op and there is a third processor that can perform the operations in p and y. Prove that in any linearizable implementation of this data type, top > .

(b) What does this result imply about the worst-case time for linearizable implementations of stacks and queues?