Sequential History in Herlihy and Wing's Linearizability paper

Question

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:

1. First event of $H$ is an invocation
2. 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!

Answer 1

I'm stuck on the same detail and luckily found your post. Agree that the word "matching" in "Each response is immediately followed by a matching invocation" should be omitted. The evidence is that the word is omitted in the paper, Axioms for concurrent objects, by the same authors. Link: http://www.cs.cmu.edu/~wing/publications/HerlihyWing87a.pdf

Answer 2

I've come to the conclusion that the constraint "each response is followed by a matching invocation" should omit the word "matching", and the paper should be read as if it weren't there. My evidence for this is that related literature and conference proceedings seem to omit it, either literally or effectively.

For example, the proceedings Principles of Distributed Systems: 14th International Conference (Google Books) includes a summary of a sequential history and linearizability and omits the second constraint completely:

History $H$ is called Sequential if the first event of $H$ is an invocation, and each invocation, except possibly the last, is immediately followed by a matching response.

Another conference proceedings that I found, Networked Systems: Second International Conference (Google Books) includes the second constraint without the word "matching":

A history is sequential if its first event is an invocation, and then (1) each invocation event, except possibly the last, is immediately followed by the matching response event, and (2) each response event, except possibly the last, is immediately followed by an invocation event.