I've been reading Herlihy and Wing's paper Linearizability: A Correctness Condition for Concurrent Objects (ACM Transactions on Programming Languages and Systems, 12(3):463–492, 1990; PDF) and there's one piece of the paper that is a fairly small detail, but on which I'm stuck anyway. They define a sequential history as one satisfying two conditions:
- First event of $H$ is an invocation
- Each invocation, except possibly the last, is immediately followed by a matching response. Each response is immediately followed by a matching invocation.
Question 1 Since an invocation and response match iff they have the same object and process, does "each response is immediately followed by a matching invocation" imply that all events in a sequential history share the same object and process (since each event matches the prior event)?
Question 2 Later in section 2, they offer the following as an example of a sequential history, even though it involves multiple processes:
q Enc(x) A
q Ok() A
q Enq(y) B
q Ok() B
q Deq() B
q Ok(x) B
q Deq() A
q Ok(y) A
q Enq(z) A
q Ok() A
I suspect that the definition of sequential history actually doesn't include the constraint "each response is immediately followed by a matching invocation" but maybe it does and I'm just misreading it. In either case, thanks for any enlightenment anyone can provide!