[dpratt71]

Whether the "merge" implementation is costly or complicated very much depends on exactly what it has to do. The git example is pretty much a worst case example in this regard.

An easier example could be that you have a tree structure that represents a mathematical expression. The evaluation of every node could proceed on its own lightweight thread. The merge strategy would be to simply perform the appropriate operation on the results produced by the threads evaluating the child nodes.

[kubanczyk]

I don't get math expressions example at all. One thread modifies one value, so there is no (mutability) problem to solve.

You have customers' orders to buy items. One last item remains at your store. You accept one order and update HEAD. You accept another order in parallel and follow to merge. "Merge" here means that you need to return money to the customer and send out an apology e-mail.

More cumbersome than locking, isn't it? But possible, yes.

[dpratt71]

Yeah, you're right, I muddied the waters a bit with that example. I was just trying to think of examples of persistent data structures being used in a concurrent context, but you had in mind a situation where multiple agents could be updating the same data structure independently.

Your example is much better. I also was thinking of maintaining an account balance with a log (vs. synchronising updates to a stored amount), but it's not much different from your example.

And of course this "eventually consist" strategy is generally how things happen "at scale", persistent data structures or not.