Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
The Scalable Commutativity Rule (muratbuffalo.blogspot.com)
40 points by mad44 on Nov 3, 2014 | hide | past | favorite | 5 comments


This sort of thing has been cropping up in distributed systems quite a bit recently, in the form of CRDTs: commutative replicated data-types. Essentially data structures whose operations commute. This offers a lot of powerful guarantees when it comes to dealing with consistency in a distributed system.

They're an interesting concept, and I'd highly recommend reading more about them.

The original paper: http://highscalability.com/blog/2010/12/23/paper-crdts-consi...

Their use in League of Legends: http://highscalability.com/blog/2014/10/13/how-league-of-leg...

How Riak uses them: http://aphyr.com/posts/285-call-me-maybe-riak


Glitch [1] is based on this to achieve eventual consistency through dependency tracking and replay. Its not exactly the same though: many operations commute (e.g. accumulation), but certain operations like cell assignment will never commute, so we have to dynamically disallow re-assignment. Another trick is to pair commutative operation order with transactional style rollback, which allows the repair of arbitrary executions (since you can rollback executions and redo them in any order!).

[1] http://research.microsoft.com/pubs/211297/onward14.pdf


Occam were heavy on this. In Occam you explicitly stated which parts of your program were sequential and which were parallel (i.e. commutative), sequentialism not assumed. Sadly, Occam is a dead language now; it was too far ahead of its time.



The video presentation of this session is available by clicking through the ToC, or Source Materials http://dl.acm.org/citation.cfm?doid=2517349.2522712




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: