Skip to content


Links for 2013-04-03

  • The Patent Protection Racket

    Joel On Software weighs in (via Tony Finch):

    The fastest growing industry in the US right now, even during this time of slow economic growth, is probably the patent troll protection racket industry.

    (tags: joel-on-software patents swpats shakedown extortion us-politics patent-trolls via:fanf)

  • Cap’n Proto

    Cap’n Proto is an insanely fast data interchange format and capability-based RPC system. Think JSON, except binary. Or think Protocol Buffers, except faster. In fact, in benchmarks, Cap’n Proto is INFINITY TIMES faster than Protocol Buffers.
    Basically, marshalling like writing an aligned C struct to the wire, QNX messaging protocol-style. Wasteful on space, but responds to this by suggesting compression (which is a fair point tbh). C++-only for now. I’m not seeing the same kind of support for optional data that protobufs has though. Overall I’m worried there’s some useful features being omitted here…

    (tags: serialization formats protobufs capn-proto protocols coding c++ rpc qnx messaging compression compatibility interoperability i14y)

  • CRDTs – Commutative Replicated Data Types [pdf]

    Shared read-only data is easy to scale by using well-understood replication techniques. However, sharing mutable data at a large scale is a dicult problem, because of the CAP impossibility result [5]. Two approaches dominate in practice. One ensures scalability by giving up consistency guarantees, for instance using the Last-Writer-Wins (LWW) approach [7]. The alternative guarantees consistency by serialising all updates, which does not scale beyond a small cluster [12]. Optimistic replication allows replicas to diverge, eventually resolving conflicts either by LWW-like methods or by serialisation [11]. In some (limited) cases, a radical simplication is possible. If concurrent updates to some datum commute, and all of its replicas execute all updates in causal order, then the replicas converge.1 We call this a Commutative Replicated Data Type (CRDT). The CRDT approach ensures that there are no conflicts, hence, no need for consensus-based concurrency control. CRDTs are not a universal solution, but, perhaps surprisingly, we were able to design highly useful CRDTs. This new research direction is promising as it ensures consistency in the large scale at a low cost, at least for some applications.

    (tags: consistency algorithms concurrency crdts distcomp data)

  • CRDT toolbox

    ‘The CRDT toolbox provides a collection of basic Conflict-free replicated data types as well as a common interface for defining your own CRDTs’. – in Eric Moritz’ github. Also includes some more links to CRDT background reading.

    (tags: crdt github eric-moritz python algorithms)

  • Eventually-Consistent Data Structures [slides]

    implementing CRDTs in Riak and Voldemort

    (tags: crdt algorithms distcomp riak voldemort distributed)

Comments closed