Project meeting T0+24, 22-23 November 2012, Nantes, France

This meeting is joint with the ANR Streams M24 meeting.

More information is also available on STREAMS website.

Persons present:

  • Carlos Baquero, U. Minho (invited);
  • Valter Balegas, UNL, Concordant;
  • Annette Bieniusa, Uni Kaiserslautern (invited);
  • Russell Brown, Basho (invited speaker);
  • Alexey Gotsman, IMDEA (invited speaker);
  • Luis Ibáñez, U. Nantes, Streams;
  • Stéphane Martin, U. Rennes, Streams;
  • Pascal Molli, U. Nantes, Streams (organiser);
  • Achour Mostefaoui, U. Nantes, Streams;
  • Mahsa Najafzadeh, INRIA, Concordant;
  • David Navalho, UNL, Concordant;
  • Brice Nedelec, U. Nantes, Streams;
  • Gérald Oster, LORIA, Streams (co-chair);
  • Nuno Preguiça, UNL, Concordant (by video);
  • Rodrigo Rodrigues, UNL, Concordant (by video);
  • Hala Skaf-Molli, U. Nantes, Streams;
  • Marc Shapiro, INRIA, Concordant and Streams (co-chair);
  • Pascal Urso, LORIA, Concordant and Streams;
  • Marek Zawirski, INRIA, Concordant and Streams;

Talks and discussion sessions

Semantics of eventual consistency (Alexey Gotsman)


  • Interesting formalisation. Clean separation of concerns.
  • Concordant authors wish to revisit the "Semantics of concurrent sets" paper with Alexey.
  • Liveness: no modal logic; consider infinite histories. Expressed in the same logic, but proof techniques will differ.
  • You don't mention semi-lattice properties, why? Hidden in the data type semantics.

SwiftCloud: It's Time to Move the Data to the Edge (Annette Bieniusa)


  • Contrast to Riak? Riak state-based, oriented towards replication within data centre and DC geo-replication.

CRDT transactions in a scalable way with SwiftCloud (Marek Zawirski)


  • How does SwiftCloud scale to large numbers of DCs, clients? Epidemic propagation + quorum reads in DCs. No vector clocks entriesfor clients.
  • Why is it hard? Partial replication, dynamic topology, pruning.

SwiftFS: A CRDT Filesystem (Annette Bieniusa)


  • What are the correctness conditions for composing CRDTs? See Carlos' presentation later in the workshop.

Making Geo-Replicated Systems Fast as Possible Consistent when Necessary (Nuno Preguiça)


  • Red-Blue distinction not sufficient: operations that commute with one another but not with strong ones.
  • Total order of red ops? Implemented with ~atomic broadcast.
  • How does escrow fit in?

Limitations of SwiftCloud approach (Valter Balegas)


  • Referential integrity: is it an issue of CRDTs or just a DB issue? Both: DB, but harder with CRDTs and SI.

Titan: CRDT-based computations for Participatory Sensing applications (David Navalho)


  • Do you leverage commutativity? Yes (and associativity and compensation).

Benchmarking collaborative editing CRDTs (Pascal Urso)

Support for CRDTs on riak_core (Russell Brown)


  • Do Riak customers require transactions? No, just basic CRDTs are a massive improvement for them. SwiftCloud is way ahead.
  • Small replica count (3--5) but vector clocks grow. Consensus required to clean vectors.
  • Read-repair only so far.

Quasi-Causal Delivery (Achour Mostefaoui)


  • Collision detection: no false negatives, but false positives possible.
  • How to recover from collisions? Dependent on data semantics.

Composition and Fragmenting of CRDTs (Carlos Baquero)


  • Composition is not just juxtaposition: need more rules. For instance: graph = composition of sets + rule about add-edge(v,v') || remove-vertex(v). Extra layer of abstraction map that hides some internal states that do not make sense.
  • Decomposition: Consistency between fragments? Need more mechanism???
  • Hand-off counters: monotonic protocol for moving private state from secondary replica to primary replica.

CF-seq: a Context-Free and Conflict-Free Replicated Data Type for sequences (Brice Nedelec)

Live Linked Data (Luis Ibáñez)


  • Implemented in Corese, W3C reference implementation.
  • To be submitted to W3C as a standard.

Programming CRDTs on SwiftCloud (Marek Zawirski)


  • Why must CRDTs be both state- and op-based? This is an optimization. State-based allows more efficient representation after pruning. We are not sure if the state-based part needs to mergeable (something to discuss).
  • Why two different abstractions (versioned + transactional) for a single object type? The transactional abstraction is simpler, isolated.

Designing new CRDT types using layers (Stéphane Martin)


  • Link with Carlos' talk on composition + extra abstraction map.


Next steps:

  • Deliverables:
    • D3.3 replaced by SwiftCloud paper + tech report on 1-phase handoff (to
    be published)
    • D5.2: delayed to M36
    • D6.2+6.3: delayed to M36
  • M30 Concordant workshop: Porto or Braga. Organisers: Nuno and Carlos.
  • Final workshop:
    • Organise as a follow-up to Dagstuhl workshop on consistency in distributed systems (Feb. 2013).
    • Target date: between November 2013 and April 2014.
    • Find a convenient location. Co-locate with some conference?
    • Set up a PC: Marc (chair), Alexey, Ahmed, DB and systems people, mostly from Europe.

New ANR proposals:

  • ANR Blanc International with Germany: Kaiserslautern, Rostock, INRIA, LORIA. In charge: Annette. Deadline: 17 January.
  • ANR Infra: In charge: Pascal U. Deadline: 7 February.
    • Interested parties include INRIA, LORIA, Nantes, Grenoble, Eurecom, LIAFA, PlayAdz, Technicolor.
    • Use cases to be defined by industrial partners.
    • Possible application area: games at the edge (geographical locality of players at a same server; disconnected operation; latency and QoS constraints).
    • Stream computation using CRDTs.
    • Placement of data and computation.
    • Byzantine fault tolerance, security.
    • Tools for analysis, test, debugging of conflict-free programs.