Re: Lock-free databases

Christopher Browne wrote:
>>"Joachim Pense" <spam-collector_at_pense-online.de> wrote in message
>>news:dkiaao$r43$05$1_at_news.t-online.com...
>>
>>>VC:
>>>
>>>>In MVTSO, a data item in addition to the transaction timestamp
>>>>that created the item has a read timestamp. In this model reads
>>>>always succeed, and writes are rejected and restarted if their
>>>>timestamp is smaller than the data item read timestamp.
>>>
>>>What does "restarted" mean here? Can that mean "automatically", or
>>>does it just mean "rejected and reconsidered by the application if
>>>the write should still be done"?
>>
>>The standard MVTSO model implies automatic restart.

> 
> 
> If a legal update is blocked from proceeding, then that's more than
> close enough to being a "lock" that it surely ought to feel
> uncomfortable to claim "it's a non-locking model."

You can google Herlihy for definitions of "lock-free", "wait-free", etc...

If a transaction gets restarted it's because some other process did make forward progress so you can probably claim lock-free from that. "wait-free" would be the more desirable property especially given that you're likely in a distributed environment. In this case it would probably matter whether where the tranactions are being executed. If they're on the server where forward progress guarantees can be made, you can probably claim "wait-free" or at least a stronger form of "lock-free". On the client, probably not unless the server bumps the client priority or something.

Remember, looping doesn't necessarily imply blocking. It's forward progress that you should be concerned about. If the likelyhood of forward progress increases on each iteration of the loop, it's non-blocking.

-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.