3 ms·

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 s

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-consistency-without-concurrency-control.html 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-legends-scaled-chat-to-70-million-players-it-t.html http://highscalability.com/blog/2014/10/13/how-league-of-leg... How Riak uses them: http://aphyr.com/posts/285-call-me-maybe-riak http://aphyr.com/posts/285-call-me-maybe-riak

seanmcdirmid 12y ago
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 http://research.microsoft.com/pubs/211297/onward14.pdf