Room for Wandering Logic and hengxin

4:48 AM

@WanderingLogic To me, "instantaneously" means something more than just "grouped together and not interleaved with any other instructions". In my understanding, Linearizability for transactions requires each transaction to appear to take effect instantaneously at some moment between its start event and commit event. This is, it enforces the "real-time" partial order between transactions.

In contrast, Serializability does not enforce such "real-time" order. It only enforces the basic program order between transactions issued by each individual process. In this sense, Linearizability is stronger than Serializability, since "real-time" order implies program order.

Wandering Logic

12:24 PM

I've never understood what "real time" means.

hengxin

@WanderingLogic By "real-time" order, I mean: If transaction T1 commits before another transaction T2 starts, then T1 is called to precede before T2. Such "precedes" relation defines the "real-time" partial order between transactions.

Wandering Logic

I can't think of an example where that produces a different result than strict serializability.

Also, linearizability was defined for objects, not transactions.

And I gave the quote from the paper that connects linearizability (of objects) and strict serializability (of transactions).

hengxin

12:39 PM

"linearizability was defined for objects, not transactions.", I agree. However, I think many papers have also used the term linearizability for transactions. When used for transactions, it is strict serializability.

Wandering Logic

Herlihy and Wing, page 473

> Linearizability can be viewed as a special case of strict serializability where
transactions are restricted to consist of a single operation applied to a single
object.

hengxin

So do we have the same understanding now: I used linearizability for transactions and you used strict serializability? Maybe strict serializability is earlier and more classic than linearizability, when used for transactions.

Wandering Logic

I was trying to use the definitions in Herlihy and Wing. I don't have (and have never read) Herlihy and Shavit, and they may use different definitions?

But I still don't understand.

Does the "real time" property add something on top of strict serializability?

Because strict serializability is not a "local" property.

For transactions or for objects.

(I think).

hengxin

@WanderingLogic Yes. I have just checked (just Ctrl + F) the "Software Transactional Memory" paper (by Nir Shavit and Dan Touitou). They use the term "linearizability".

@WanderingLogic I think for transactions linearizability is equivalent to strict serializability.

@WanderingLogic I don't know whether they are local properties for transactions (I am not aware of how to define "local" when referring to transactions). Do you have references for strict serializability for objects?

Wandering Logic

12:58 PM

I'm super confused about "local". I'm re-reading the section of Herlihy and Wing comparing linearizability to strict serializability and I just don't get their example.

On page 473, again, they say:

> One important formal difference between linearizability and serializability is
that neither serializability nor strict serializability is a local property. For
example, in history Hs shown above, if we interpret A and B as transactions
instead of processes, then it is easily seen that both Hs ] p and Hs ] q are strictly
serializable but He is not. (Because A and B overlap at each object, they are
unrelated by transaction precedence in either subhistory.) Moreover, since A and
B each dequeues an item enqueued by the other, H8 is not even serializable.

(That's "history H_8", not "history Hs".)

History H8 looks neither sequentially consistent nor strictly serializable to me.

hengxin

?? The authors also claim that $H_8$ is not even serializable.

when A and B are interpreted as transactions instead of processes.

Wandering Logic

I believe that $H_8$ is not serializable when A and B are interpreted as transactions instead of processes. A enqueues an "x" on p, and an "x" on q, then dequeues from p and gets "y". B enqueues a "y" in p and then a "y" on q, then deques from q and gets "x". There's no way to put all of A before all of B or all of B before all of A.

Hmmm. I actually also think my definition of Strict Serializability is stronger than Herlihy & Wing's definition of Strict Serializability.

hengxin

1:14 PM

Yes, I agree. And the authors also agree (the last sentence of the paragraph quoted). So I am afraid that I don't get your confusion.

Wandering Logic

But is $H_8 | p$ strictly serializable (or sequentially consistent as they claim at bottom of page 472?)

They also say $H_7$ is sequentially consistent, and I'm not seeing that either.

hengxin

@WanderingLogic Now I see. It seems that queues have been treated as stacks (or we have wrong understandings of Linearizability and Serializability).

@WanderingLogic I made a mistake. $H_7$ is actually sequential consistent.

Being sequential consistent, we can put all the the operations issued by B before those issued by A.

In the same way, I think the authors are correct in $H_8$. I will check it now.

Wandering Logic

1:31 PM

I am having trouble seeing how $H_7$ is actually sequentially consistent.

Oh I see now

hengxin

A and B are two different processes. We can put all the operations issued by B before those issued by A. Sequential consistency only requires the individual program order.

Wandering Logic

Yes, I see now that a "History" is not what I thought it was (the globally agreed-upon total order of events under the "happens before" relation).

hengxin

I checked $H_8$ and it is what the authors claimed. So it is probably we now have the right concepts of serializability and linearizability.

Transcript for

Room for Wandering Logic and hengxin