[concurrency-interest] updating a pure functional tree and CASproblems

David Holmes dcholmes at optusnet.com.au
Wed Mar 11 19:59:17 EDT 2009

Optimistic concurrency control, whether in databases, STMs or algorithmics
is premised on the assumption that conflict is rare and easily recovered
from. If the assumptions no longer hold ... things don't work so well.

As other more prominent concurrency affecionados have said the real goal is
not to provide mechanisms that handle contention well, but to remove
contention in the first place.

David Holmes
  -----Original Message-----
  From: concurrency-interest-bounces at cs.oswego.edu
[mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of jason
  Sent: Thursday, 12 March 2009 9:45 AM
  To: Peter Veentjer
  Cc: concurrency-interest at cs.oswego.edu
  Subject: Re: [concurrency-interest] updating a pure functional tree and

  On Tue, Mar 10, 2009 at 4:07 PM, Peter Veentjer <alarmnummer at gmail.com>

    Hi Guys,

      The problems worsens if the number of things that need to
    be committed increase because it takes more time to build the new
    snapshot. It could even mean that long running transaction never can
    commit because some shorter running transaction take less time and let
    the long transaction try forever.

  You say that like it's a bad thing.  Isn't that the essential complexity
of updating shared state?  The more state you touch, the harder it is for
anybody else to make progress.

  In the database world, as you approach the cliff-face you start throwing
things overboard.  Either you rearrange your code so that the duration of
the change is shorter, or you find a way to split your update into two
partial updates, and then you deal with the intermediate state in the rest
of your data model.

  I have always just accepted that this situation would happen in an STM
environment as well.  Maybe I'm giving up too quickly, but I don't see any
way around the problem.

  - Jason
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20090312/3e322739/attachment.html>

More information about the Concurrency-interest mailing list