On Sat, 06 Feb 2010 12:03:39 -0500, Jim Starkey <jstarkey@...>
wrote:

> For god's sakes, Paul, I waded into that swamp at your insistence. Here

> is a review of the bidding:
>
> Me (Jim):
>
> The information required for the two mechanisms is radically

different.

> > A commit sequences needs to know the full read and write sets, so
> > if a transaction counted a million records, the commit sequencer
> > needs
> > to know not only which million records but which records weren't
> > read
> > (e.g. hadn't arrived at that node yet).
>
>
> You (Paul):
>
> Have you actually read and pondered the paper?? A one million record
> update would first occur locally, a single, short commit request

would

> be
> sent out and when it is received back again a local commit is
> attempted. If
> it fails, we're done. If it commits, a second commit confirmed

message

> would go out to the other nodes, where we can be certain it will
> succeed.
> Sending write sets as data is an optimisation for simple updates;
> complex
> updates are sent as the (compiled) statement. So it is 1..2 short
> messages
> per write transaction.
>
>
> No, I hadn't read and ponder the paper. I was responding to what it
> would take to implement a Kemme scheme that was serializable.
>
> So, I read and the pondered the paper. It doesn't work and it isn't
> serializable. It's just wrong. Actually, shallow and wrong.

Nor in my reply above, nor in the paper do I see this link to
"serializable". In the paper the word appears three times, all three times
to distinguish it from previous work. It does not claim to be serializable,
and in fact points out in two places that it isn't, for the very same
reason that snapshot isolation isn't.

I've thought for a day where this confusion might come from. Perhaps it is
because of the word "ordering"; perhaps whereever ordering is mentioned,
serializabilty is assumed. Perhaps we need to be more precise with words.

There is "serializable" as in the SQL standard isolation level. This is
defined by the ability to find a serial sequence of all transactions that
would lead to the same observed result as concurrent execution -- I'm not
telling anybody news here.

Then there is Ann's definition of "serializable" for a distributed system:
same state on each node after quiescing. This is a different serializable
from the above, and we should perhaps find a different word for it.

Next there is order. In the context of a single system this usually refers
to the sequence of transactions. In a distributed system, it also referes
to the allowable differences in sequence accross nodes. In this latter
context we get into Lamport's work.

We also need to be careful to say/understand what gets ordered. A system
that conforms to rule 2. and 4. of "SCOA" :^) de facto imposes a total
order on conflicting write transactions, regardless of the algorithm used
to get there. On other transactions no order is imposed by the 4 rules.

Last there is a difference between ordering of messages and the ordering
of transactions. It is possible for transactions to be less ordered then
messages.

That all being said, I think we have reached to limits of the discussion
in this thread at this point in time. If I'll find the time, I'll try to
redo Kemme's proof-of-concept (using spread/sqlite I think), so that we all
have some code to look at. If anybody is interested in working on this
stuff, let me know.