Home

Concurrent Revisions

Concurrent Revisions is a Microsoft Research project doing interesting work in making concurrent programming scalable and easier to reason about. These papers work have been mentioned a number of times here on LtU, but none of them seem to have been officially posted as stories.

Concurrent Revisions are a distributed version control-like abstraction [1] for concurrently mutable state that requires clients to specify merge functions that make fork-join deterministic, and so make concurrent programs inherently composable. The library provide default merge behaviour for various familiar objects like numbers and lists, and it seems somewhat straightforward to provide a merge function for many other object types.

They've also extended the work to seamlessly integrate incremental and parallel computation [2] in a fairly intuitive fashion, in my opinion.

Their latest work [3] extends these concurrent revisions to distributed scenarios with disconnected operations, which operate much like distributed version control works with source code, with guarantees of eventual consistency.

All in all, a very promising approach, and deserving of wider coverage.

[1] Sebastian Burckhardt and Daan Leijen, Semantics of Concurrent Revisions, in European Symposium on Programming (ESOP'11), Springer Verlag, Saarbrucken, Germany, March 2011
[2] Sebastian Burckhardt, Daan Leijen, Caitlin Sadowski, Jaeheon Yi, and Thomas Ball, Two for the Price of One: A Model for Parallel and Incremental Computation, in Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA'11), ACM SIGPLAN, Portland, Oregon, 22 October 2011
[3] Sebastian Burckhardt, Manuel Fahndrich, Daan Leijen, and Benjamin P. Wood, Cloud Types for Eventual Consistency, in Proceedings of the 26th European Conference on Object-Oriented Programming (ECOOP), Springer, 15 June 2012

By naasking at 2013-03-18 13:29 | Implementation | OOP | Parallel/Distributed | other blogs | 21788 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Operational transformations and Virtual time

This sort of reasoning reminds me of STM, operational transformation, and virtual time. How does this system differ from these, and why is it better?

Semantics of Concurrent Revisions cites snapshot isolation in STM, but I would have liked to see a direct comparison.

They discuss OT in Cloud Types for Eventual Consistency:

Prior work on operational transformations [15] can be understood as a specialized form of eventual consistency where updates are applied to different replicas in di erent orders, and modified in such a way as to guarantee convergence. This specialized formulation can provide highly ecient broadcast-based real-time collaboration, but poses signi cant implementation challenges [7].

If OT is a special case and hard to implement, wouldn't the general case be harder to implement?

And no mention of virtual time, as far as I can tell. Maybe Brian Beckman should be working with them.

By kms at Mon, 2013-03-18 16:24 | login or register to post comments

How does this system differ

How does this system differ from these, and why is it better?

It's optimistic and deterministic. STM is still non-deterministic, even the recently published non-deterministic implementation.

If OT is a special case and hard to implement, wouldn't the general case be harder to implement?

The opposite is sometimes the case in math. The more general, simpler abstractions end up clarifying the corner cases that seem intractable in the specific cases.

Regardless, I don't think that's what's being said here. There is more than one way to achieve eventual consistency beyond concurrent revisions, and operational transformations end up being one of them in specific domains. No claim is made about the relative efficiency of the various models, so there could different timing and space use characteristics, for instance.

By naasking at Mon, 2013-03-18 19:57 | login or register to post comments

Not to mention recent work

Not to mention recent work like Eve. There seems to be a huge firewall between systems and PL these days.

By Sean McDirmid at Mon, 2013-03-18 23:19 | login or register to post comments

Could you post a link to

Could you post a link to Eve? Google is inundated with other Eves.

By kms at Tue, 2013-03-19 01:01 | login or register to post comments

Sure, it was published in

Sure, it was published in OSDI last year. Here is the link. Working on a systems team, I get exposed to a lot of this work even if my research area is in PL.

By Sean McDirmid at Tue, 2013-03-19 01:11 | login or register to post comments

One more interesting one

Thanks for the interest in this line of work. At this point, we are looking more and more in applying this 'memory model' to data that is shared in the cloud. in particular, we have a working implementation of the could data types inside the 'TouchDevelop' project.

Anyway, I wanted to mention one more publication that is a bit on the technical side but it gives a formal definition of what 'eventual consistency' means, and we show that a concurrent revision model is a one possible model that satisfies eventual consistency. As such, it gives less guarantees than, say, full transactions but its guarantees seem strong enough for effective reasoning and useful for many programming situations, while allowing real scalability in the implementation.

Sebastian Burckhardt, Manuel Fahndrich, Daan Leijen, and Mooly Sagiv, Eventually Consistent Transactions, in Proceedings of the 22n European Symposium on Programming (ESOP), Springer, 24 March 2012

By Daan at Mon, 2013-03-18 19:53 | login or register to post comments

Write skew

Revisions seem to enjoy the snapshot isolation property, but - like snapshot isolation - may suffer from write skew. I don't see write skew mentioned in any of the papers, however.

Write skew could be alleviated by specialised merging functions, that resolve conflicts (or constraint violations) between isolated sets of versioned objects. Such merging functions go beyond merging functions that only consider single versioned objects.

By Robbert van Dalen at Wed, 2013-03-20 20:15 | login or register to post comments

This is interesting work. It

This is interesting work. It could easily be adapted to functional programming by making the ambient revision explicit. Give fork an explicit revision to fork from, and let join take two revisions and return a joined one. So this:

r1 = fork { ... }
r2 = fork { ... }
join r1;
join r2;

would become:

r1 = fork r0 { ... }
r2 = fork r0 { ... }
r3 = join(r1,r2)

where r0 is the initial ambient revision.

I wonder if there is a way to incorporate observable but controlled non determinism? Say you have an integer i that is continuously displayed in a GUI, and a button that increments i, and another button that makes a network request and increments i by the number n returned by the network request. Is there a way to extend concurrent revisions that allows you to implement something like this? Possibly with a joinInAnyOrder(r1,r2). What if the actions are not commutative, for example if you click the button that makes the network request it sets the i to n instead of incrementing i by n. Concurrent revisions could be an interesting way to specify precisely which interleavings/behaviors are allowed, rather than the currently practiced solution of writing each event handler separately and then adding the necessary synchronization constructs. So the difference is in specifying what behaviors are allowed, vs allowing all interleavings by default and then restricting which behaviors are not allowed.

By Jules Jacobs at Tue, 2013-03-19 20:42 | login or register to post comments

Not sure what you mean by

Not sure what you mean by ambient revisions, as revisions are first-class values. As you indicate in your code samples, you must explicitly specify which revision you wish to join with.

Re: non-determinism, you can in principle use all the mutable state you want since concurrent revisions is written as a library. One of their earlier papers covered a game they ported to concurrent revisions. The game loop forked to save the current game state and only joined on that revision when a shared variable was updated indicating completion.

I also like concurrent revisions because it also naturally models the semantics of web interactions, ie. each form display is a fork on the revision referenced in the URL. A final commit point is simply a join that may invalidate some other forks, and the required invalidations are well-defined by the allowed revision nesting rules. These commit points aren't as clearly modelled by other abstractions that permit backtracking, like continuations.

By naasking at Tue, 2013-03-19 21:30 | login or register to post comments

With ambient revisions I

With ambient revisions I mean the current revision. If you fork you implicitly fork some revision: the ambient/current revision. If you join something, you implicitly join that something to the ambient/current revision. I just meant to say that you can make that revision explicit in a variable, and then it has a functional feel rather than imperative.

The game loop is a good example but I'm not sure how to generalize that to a general GUI program that consists of multiple independent UI elements and event handlers. What I was thinking is along these lines: around each event handler there is an implicit fork. When you return from the event handler the GUI library will join the forked revision back to the main one. This would keep the GUI always responsive, even if there is a long running event handler, but may lead to undesirable behavior because event handlers could get joined in a different order than they were invoked. So you need some mechanism to control the concurrency.

By Jules Jacobs at Wed, 2013-03-20 00:01 | login or register to post comments

I just meant to say that you

I just meant to say that you can make that revision explicit in a variable, and then it has a functional feel rather than imperative.

What's the advantage of this? I'm having trouble seeing the upside.

This would keep the GUI always responsive, even if there is a long running event handler, but may lead to undesirable behavior because event handlers could get joined in a different order than they were invoked. So you need some mechanism to control the concurrency.

That's shouldn't be a problem. There are only two specific fork-join patterns that are not supported: two forks that join with each other, and a fork (F1) of a fork (F0) that merges before its parent (F0). All other join patterns are well-defined and deterministic, modulo appropriately defined merge functions.

The ability to merge the results is key, so that alone will rule out certain types of event interleaving.

By naasking at Wed, 2013-03-20 02:07 | login or register to post comments

No particular advantage, I

No particular advantage, I just found it a bit easier to conceptually understand if you separate the implicit scoping of the current revision from the revision operations themselves. It does give you the ability to work with multiple independent sets of revisions, though I'm not sure if that is useful in practice.

That's shouldn't be a problem. There are only two specific fork-join patterns that are not supported:

I'm not saying that it allows too few fork-join patterns, quite the opposite, it may allow too many in some cases.

The ability to merge the results is key, so that alone will rule out certain types of event interleaving.

OK, but how? For example how do you handle the scenario that I mentioned above? There are two competing concerns: responsiveness and consistency. If you handle each event in sequence you have consistency, but now your GUI becomes unresponsive while you are handling an event. If you allow different order you can continue to handle new events even if an old event is still being processed, but you lose consistency. Maybe defining merging in the right way can allow you to express different trade-offs between those two concerns, but I'm not sure how.

By Jules Jacobs at Wed, 2013-03-20 19:30 | login or register to post comments

Concurrent revisions are

Concurrent revisions are eventually deterministic. I.e. once you've seen all the events up to time T, you can construct the state at time T. Of course, by the time we receive all those events, we might be milliseconds, seconds, hours, or even days past time T (depending on the system). In many realistic systems, we may need to make observable decisions based on a state that is not deterministic. An interesting feature is that concurrent revisions (and similar models, such as Time Warp) can often orthogonally be combined with some real-time guarantees - e.g. that by time T we'll have processed all the events for time T-60ms. Such guarantees allow us to achieve a powerful balance of consistency, responsiveness, and concurrency. But we lose automatic partitioning tolerance.

When faced with partitioning, we'll need to make some explicit choices. E.g. we can achieve determinism (up to time of disruption), but only if we assign formal 'ownership' of the resource to a particular partition. Or we can allow replicated instances to diverge, then restore them if (and when) communication is re-established, accepting that interim real-time decisions based on the data are not globally consistent. The right choice will depend on the application.

The need to make an explicit choice, however, is valuable. Global determinism is unrealistic. But awareness and control of non-determinism is realistic and worthy.

By dmbarbour at Wed, 2013-03-20 22:37 | login or register to post comments